解題區►解題區 - UVa

UVa 1404 - Prime k-tuple

Problem

查找區間內，相鄰 k 個質數中，滿足最大減最小恰好為 s 的情況有多少個。

Sample Input

1
2
1
100 200 4 8

Sample Output

1
2

Solution

a, b 大小簡直不可思議，就算能做到全搜索，建表時間是線性，也必須跑上 20 億乘上 20。

先做一次 sieve，接著對 [a, b] 進行 local sieve，題目雖然沒說明 b - a 的大小，實際看來是非常小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
#define maxL (50000>>5)+1
#define MAXN (2000000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
#define GET2(x) (mark2[x>>5]>>(x&31)&1)
#define SET2(x) (mark2[x>>5] |= 1<<(x&31))
int mark[maxL], mark2[MAXN];
int P[5500], Pt = 0;
void sieve() {
	register int i, j, k;
	SET(1);
	int n = 50000;
	for(i = 2; i <= n; i++) {
			if(!GET(i)) {
			for (k = n/i, j = i*k; k >= i; k--, j -= i)
				SET(j);
			P[Pt++] = i;
		}
	}
}
int local_sieve(int a, int b, int k, int s) {	
	int sqr = sqrt(b), gap = b - a;
	memset(mark2, 0, ((gap>>5) + 1) * 4);
	
	for (int i = 0; i < Pt && P[i] <= sqr; i++) {
		int p = P[i], base = a / p * p;
		while (base <= p)	base += p;
		for (int j = base; j <= b; j += p)
			SET2(j - a);
	}
	if (a == 1)	SET2(0);
	queue<int> Q;
	int ret = 0;
	for (int i = 0; i <= gap; i++) {
		if (!GET2(i)) {
			if (Q.size() == k - 1) {
				if (k == 0)
					ret += s == 0;
				else if ((a + i) - Q.front() == s)
					ret++;
			}
			Q.push(a + i);
			while (Q.size() >= k)	Q.pop();
		}
	}
	return ret;
}
int main() {
	sieve();
	
	int testcase;
	int a, b, k, s;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d %d %d", &a, &b, &k, &s);
		printf("%d\n", local_sieve(a, b, k, s));
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1291 - Dance Dance Revolution

Problem

跳舞機共有四個方向，兩隻腳必須在某一個時刻按到該按鈕。

1
2
3
#1#
204
#3#

一開始雙腳站立於 0 的位置，每一個時刻只能移動一隻腳。

每一次移動的花費，0 到任何位置都是消耗體力 2、其餘數字移動到相鄰格子消耗體力 3、其餘數字移動到相面格子消耗體力 4，腳不動消耗體力 1。

過程中雙腳不能站立於同一個格子。

Sample Input

1
2
3
1 2 2 4 0 
1 2 3 4 1 2 3 3 4 2 0 
0

Sample Output

1
2
8 
22

Solution

dp[i][j][k] 分別記錄時刻 i，左腳所在位置 j，右腳所在位置 k。分別進行轉移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int A[32767];
int cg[5][5] = {
    {0, 2, 2, 2, 2},
    {INF, 1, 3, 4, 3},
    {INF, 3, 1, 3, 4},
    {INF, 4, 3, 1, 3},
    {INF, 3, 4, 3, 1}
};
int main() {
    while (scanf("%d", &A[0]) == 1 && A[0]) {
        int n = 1;
        for (; scanf("%d", &A[n]) && A[n]; n++);
        int dp[2][5][5]; // [][left][right]
        memset(dp, 0x3f, sizeof(dp));
        int p = 0, q = 1;
        dp[p][0][0] = 0;
        for (int i = 0; i < n; i++) {
            p = !p, q = !q;
            memset(dp[p], 0x3f, sizeof(dp[p]));
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    int l = A[i];
                    if (j != l) {
                        dp[p][j][l] = min(dp[p][j][l], dp[q][j][k] + cg[k][l]);
                    }
                    if (k != l) {
                        dp[p][l][k] = min(dp[p][l][k], dp[q][j][k] + cg[j][l]);
                    }
                    if (j == l || k == l) {
                        dp[p][j][k] = min(dp[p][j][k], dp[q][j][k] + 1);
                    }
                }
            }
        }
        
        int ret = INF;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                ret = min(ret, dp[p][i][j]);
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}
/*
 1 2 2 4 0
 1 2 3 4 1 2 3 3 4 2 0
 0
 */
Read More +
解題區►解題區 - UVa

UVa 1267 - Network

Problem

有一個 N 節點的樹，要架設服務的 server，必須滿足所有葉節點到最近的 server 距離小於等於 M。一開始會給定一個架好的 server。

求最少的放置個數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2 14 
12 2 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11 
14 
3 4 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11

Sample Output

1
2
1 
0

Solution

針對加好的 server，將這個 server 當作 root，將 tree 轉換成 rooted tree，接著使用貪心。

盡可能放置越遠越好，根據 dfs 搜索的順序，查看內部節點 u，其子樹最遠的葉節點深度為何，以及子樹內部距離最近的 server 所在。

共計三種可能

  • 節點 u 逼不得已情況下放置 server
  • 節點 u 無須 server，其子樹的葉節點都已經符合標準
  • 節點 u 無須 server，其子樹的葉節點必須靠另外一個子樹的最近 server 服務。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int n, m, s, x, y;
int ret = 0;
int dfs(int u, int p, int dep, int &place) {
	int leaf = 0, pp = 0x3f3f3f3f;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == p)
			continue;
		int p;
		int tmp = dfs(v, u, dep + 1, p);
		pp = min(p, pp);
		leaf = max(leaf, tmp);
	}
	place = pp;
	if (leaf - dep + pp - dep <= m)
		leaf = 0;
	if (leaf == dep + m) {
		place = dep;
		ret += (u != s), leaf = 0/*, printf("place %d, %d\n", u, place)*/;
	}
	if (g[u].size() == 1)
		return dep;
	else
		return leaf;
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d %d", &n, &s, &m);
		for (int i = 0; i <= n; i++)
			g[i].clear();
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			g[x].push_back(y);
			g[y].push_back(x);
		}
		
		ret = 0;
		int foo;
		dfs(s, -1, 0, foo);
		printf("%d\n", ret);
	}
	return 0;
}
/*
2 
14 12 2 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11 
14 3 4 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11
*/
Read More +
解題區►解題區 - UVa

UVa 1125 - Sherlock Holmes

Problem

有 N 個箱子，每個箱子都有 M 顆球，每一個箱子的黑、白球分配的個數不同，希望分成兩堆，每一堆必須有 N/2 個箱子，並且要符合黑球、或白球必須在兩堆佔有多數 (> 50%) 的情況。

假設佔有的比例分別為 m1, m2，最大化 min(m1, m2)。

Sample Input

1
2
3
4
5
6
4 
30 
17 13
12 18
20 10
14 16

Sample Output

1
W 51.67

Solution

N 很大，M 也很大。一開始就目測需要 random 的隨機交換法，這樣湊出答案的機率是挺高的。

當然這有點不靠譜，使用 dp 背包問題，由於狀態數量太多，必須使用 set 壓縮。

dp[i][j] 表示放置前 i 個箱子，存在 j 個數的球。

統計兩色的球總個數，個數多的必然是最後佔有多數，決定球顏色後，針對個數進行背包問題的計算，由於每個箱子的球總數一樣，分成兩堆時，分母是固定的，因此可以無視另一個顏色的存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <stdlib.h> 
#include <set>
#include <algorithm>
using namespace std;
int main() {
	int n, m, A[32767];
	while (scanf("%d %d", &n, &m) == 2) {
		int w, b, wsum = 0, bsum = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &w, &b);
			wsum += w, bsum += b;
			A[i] = w;
		}
		if (wsum == bsum || n%2 != 0) {
			puts("No solution");
			continue;
		}
		char major = 'W';
		if (wsum < bsum) {
			major = 'B';
			wsum = bsum;
			for (int i = 0; i < n; i++)
				A[i] = m - A[i];
		}
		set<int> dp[32767];
		set<int>::iterator it;
		dp[0].insert(0);
		for (int i = 0; i < n; i++) {
			int w = A[i];
			for (int j = min(i, n/2 - 1); j >= 0; j--) {
				for (it = dp[j].begin(); it != dp[j].end(); it++)
					dp[j+1].insert((*it) + w);
			}
		}
		
		int ret = -1;
		int half = n/2 * m / 2;
		for (it = dp[n/2].begin(); it != dp[n/2].end(); it++) {
			if (*it <= wsum/2 && *it > half)
				ret = max(ret, *it);
		}
		if (ret < 0) {
			puts("No solution");
		} else {
			printf("%c %.2lf\n", major, ret * 100.0 / (n/2 * m));
		}
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 881 - Points, Polygons and Containers

Problem

有數個不相交的簡單多變形，構成類似等高線的地勢圖，每一個簡單多邊形都有其代碼編號，接著有數個不按照順序的詢問點，請問所在的位置是在哪一塊。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
1
4
3 18 16 1 16 1 1 18 1
1 2 15 2 2 14 2
4 15 2 15 15 3 15
2 10 4 4 10 4 4
4
2 20 4
4 3 11
3 5 6
1 12 11

Sample Output

1
2
3
4
1 4
2 0
3 2
4 1

Solution

首先用射線法，找到所有的簡單多邊形關係，O(n^2) 找到 DAG 圖。

接著將 DAG 圖縮成一個 rooted tree 圖，挑選深度最深的節點，外圍的深度是 0，越靠近裡面深度越高。

接著對於每一組詢問，從 root 開始走訪，直到沒有可以包含住這個點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <iostream>
#include <assert.h>
using namespace std;
#define eps 1e-8
#define MAXN 1024
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
		if (fabs(x - a.x) > eps)
			return x < a.x;
		if (fabs(y - a.y) > eps)
			return y < a.y;
		return false;
	}
	bool operator==(const Pt &a) const {
		return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
	} 
};
double dist(Pt a, Pt b) {
	return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int inPolygon(Pt p[], int n, Pt q) {
	int i, j, cnt = 0;
	for(i = 0, j = n-1; i < n; j = i++) {
		if(onSeg(p[i], p[j], q))
			return 1;
		if(p[i].y > q.y != p[j].y > q.y &&
			q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
			cnt++;
	}
	return cnt&1;
}
const double pi = acos(-1);
Pt polygon[MAXN][512];
int pn[MAXN], parent[MAXN], visited[MAXN], depth[MAXN];
int pid[MAXN];
vector<int> g[MAXN], tree[MAXN];
void dfs(int u) {
	visited[u] = 1, depth[u] = 0, parent[u] = -1;
	int d = -1;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (visited[v] == 0)	dfs(v);
		if (depth[v] > d)
			d = depth[v], parent[u] = v;
	}
	depth[u] = d + 1;
}
int query(int u, Pt q) {
	for (int i = 0; i < tree[u].size(); i++) {
		int v = tree[u][i];
		if (inPolygon(polygon[v], pn[v], q)) {
			return query(v, q);
		}
	}
	return u;
}
int main() {
	int testcase, n, m;
	string line;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		assert(n < MAXN);
		while (getchar() != '\n');
		for (int i = 0; i < n; i++) {
			getline(cin, line);
			stringstream sin(line);
			int m = 0;
			sin >> pid[i];
			while (sin >> polygon[i][m].x >> polygon[i][m].y) {
				m++;
				assert(m < 512);
			}
			pn[i] = m;
		}
		pid[n] = 0;
		for (int i = 0; i <= n; i++)
			g[i].clear(), visited[i] = 0, tree[i].clear();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j)	continue;
				if (inPolygon(polygon[i], pn[i], polygon[j][0]))
					g[j].push_back(i);
			}
		}
		
		for (int i = 0; i < n; i++) {
			if (visited[i] == 0)
				dfs(i);
		}
		for (int i = 0; i < n; i++)
			if (parent[i] == -1)
				tree[n].push_back(i);
			else
				tree[parent[i]].push_back(i);
//		for (int i = 0; i < n; i++)
//			printf("%d: %d\n", pid[i], parent[i]);
		scanf("%d", &m);
		assert(m < 32767);
		int out[32767] = {};
		for (int i = 0; i < m; i++) {
			Pt q;
			int id;
			scanf("%d %lf %lf", &id, &q.x, &q.y);
			assert(id <= m);
			out[id] = query(n, q);
		}
		for (int i = 1; i <= m; i++)
			printf("%d %d\n", i, pid[out[i]]);
		if (testcase)
			puts("");
	}
	return 0;
}
/*
5
0 0
50 50
100 0
100 100
0 100
2
49 50
50 51
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
*/
Read More +
解題區►解題區 - UVa

UVa 879 - Circuit Nets

Problem

給定一組電路的連接，請問有多少個電網個數。

Sample Input

1
2
3
4
5
1
14
 1 11 7 11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10

Sample Output

1
3

Solution

單純查找連通子圖的個數，使用并查集完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <sstream>
using namespace std;
int parent[65536], weight[65536];
int findp(int x) {
	return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
	x = findp(x), y = findp(y);
	if (x == y)	return 0;
	if (weight[x] > weight[y])
		parent[y] = x, weight[x] += weight[y];
	else
		parent[x] = y, weight[y] += weight[x];
	return 1;
}
int main() {
	int testcase, n;
	char line[1024];
	scanf("%d", &testcase);
	while (getchar() != '\n');
	while (getchar() != '\n');
	while (testcase--) {
		scanf("%d", &n);
		while (getchar() != '\n');
		for (int i = 0; i < n; i++)
			parent[i] = i, weight[i] = 1;
		int ret = n, x, y;
		while (gets(line) && line[0] != '\0') {
			stringstream sin(line);
			while (sin >> x >> y) {
				x--, y--;
				ret -= joint(x, y);
			}
		}
		printf("%d\n", ret);
		if (testcase)
			puts("");
	}
	return 0;
}
/*
1
14
 1 11 7 11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10 
*/
Read More +
解題區►解題區 - UVa

UVa 844 - Pousse

Problem

模擬一款推硬幣的遊戲，在一個 N x N 的盤面，可以從上下左右四個方向塞入自己的硬幣。

現在有兩個人輪流玩，一開始由 ‘X’ 作為先手，塞入硬幣的過程中，會將同行或同列的硬幣往前推，如果同一個的硬幣個數大於 N，則末端的硬幣將會掉出盤面。

模擬遊戲，直到其中一個玩家的連線個數大於另一名玩家，連線個數只看行、列皆具有相同硬幣的情況。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT

Sample Output

1
2
3
TIE GAME
X WINS

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h> 
#include <string.h>
char cmd[32767][64];
char g[128][128];
int n;
int isCompleted() {
	int Oline = 0, Xline = 0, cnt;
	char c;
	for (int i = 0; i < n; i++) {
		c = g[i][0], cnt = 0;
		for (int j = 0; g[i][0] == g[i][j] && j < n; cnt++, j++);
		if (cnt == n && c != ' ') {
			Oline += c == 'O';
			Xline += c == 'X';
		}
		c = g[0][i], cnt = 0;
		for (int j = 0; g[0][i] == g[j][i] && j < n; cnt++, j++);
		if (cnt == n && c != ' ') {
			Oline += c == 'O';
			Xline += c == 'X';
		}
	}
	return Oline == Xline ? 0 : (Oline < Xline ? -1 : 1);
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		int m = 0;
		while (scanf("%s", cmd[m]) == 1) {
			if (!strcmp(cmd[m], "QUIT"))
				break;
			m++;
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				g[i][j] = ' ';
		int ret = 0, turn = 0;
		for (int i = 0; i < m; i++, turn = !turn) {
			int x;
			sscanf(cmd[i]+1, "%d", &x);
			x--;
			if (cmd[i][0] == 'L') {
				int idx = 0;
				while (idx < n && g[x][idx] != ' ')	idx++;
				for (int i = idx; i > 0; i--)
					g[x][i] = g[x][i-1];
				g[x][0] = turn ? 'O' : 'X';
			}
			if (cmd[i][0] == 'R') {
				int idx = n-1;
				while (idx > 0 && g[x][idx] != ' ')	idx--;
				for (int i = idx; i < n-1; i++)
					g[x][i] = g[x][i+1];
				g[x][n-1] = turn ? 'O' : 'X';
			}
			if (cmd[i][0] == 'T') {
				int idx = 0;
				while (idx < n && g[idx][x] != ' ')	idx++;
				for (int i = idx; i > 0; i--)
					g[i][x] = g[i-1][x];
				g[0][x] = turn ? 'O' : 'X';
			}			
			if (cmd[i][0] == 'B') {
				int idx = n-1;
				while (idx > 0 && g[idx][x] != ' ')	idx--;
				for (int i = idx; i < n-1; i++)
					g[i][x] = g[i+1][x];
				g[n-1][x] = turn ? 'O' : 'X';
			}
//			for (int i = 0; i < n; i++, puts(""))
//				for (int j = 0; j < n; j++)
//					putchar(g[i][j]);
//			puts("---");
			if (ret = isCompleted())
				break;
		}
		if (ret)
			puts(ret < 0 ? "X WINS" : "O WINS");
		else
			puts("TIE GAME");
		if (testcase)
			puts("");
	}
	return 0;
}
/*
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT
*/
Read More +
解題區►解題區 - UVa

UVa 828 - Deciphering Messages

Problem

給一加密原則，現在要求解密，並且在只有一組文本情況下輸出正解。

一開始給定一字串 L，接著加密時，每一組訊息的 word，由左而右加密。

  • 如果字符 c 存在於 L，使用凱薩加密 shift N 位。
  • 如果字符 c 不存在於 L，輸出三個字浮，分別是 L[m]、c 使用凱薩加密 shift N 位、L[m+1]。每一次使用這一條 m 就 +1，假想 L 是環狀的。

Sample Input

1
2
3
4
5
6
7
8
9
10
1
RSAEIO
2
5
RTSSKAEAGE
GRSCAV
RGSSCAV
RUSIQO
RUSSGAACEV JEGIITOOGR

Sample Output

1
2
3
4
5
RICE
error in encryption
EAT
error in encryption
SEAT HERE

Solution

搜索，雖然看起來有點可怕，但是條件很多，如果搜索到兩種以上的情況，立即退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
int inL[128] = {}, N, Q, Llen;
char L[128], s[1024];
char text[128];
int sol;
void dfs(int idx, int pl, int m) {
	while (s[idx] == ' ')	text[pl++] = ' ', idx++;
	if (sol >= 2)	return;
	if (s[idx] == '\0') {
		sol++;
		text[pl] = '\0';
		puts(text);
		return;
	}
	
	char a, b, c;
	for (int i = 'A'; i <= 'Z'; i++) {
		if (inL[i]) {
			a = L[m%Llen];
			b = (i-'A'+N)%26 + 'A';
			c = L[(m+1)%Llen];
			text[pl] = i;
			if (a == s[idx] && b == s[idx+1] && c == s[idx+2]) {
				dfs(idx+3, pl+1, m+1);
			}
		} else {
			a = (i-'A'+N)%26 + 'A';
			text[pl] = i;
			if (a == s[idx]) {
				dfs(idx+1, pl+1, m);
			}
		} 
	}
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%s", L);
		scanf("%d %d", &N, &Q);
		memset(inL, 0, sizeof(inL));
		for (int i = 0; L[i]; i++)
			inL[L[i]] = 1;
		Llen = strlen(L);
		while (getchar() != '\n');
		for (int i = 0; i < Q; i++) {
			gets(s);
			sol = 0;
			dfs(0, 0, 0);
			if (sol != 1)
				puts("error in encryption");
		}
		if (testcase)
			puts("");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 818 - Cutting Chains

Problem

有 n 個鐵環，現在已知鐵環之間緊扣在一起，目標要把鐵環串成一鏈，可以選擇將鐵環剪開，隨後再將其串在一起。

找最少剪開的次數。

Sample Input

1
2
3
4
5
6
5 1 2 2 3 4 5 -1 -1
7 1 2 2 3 3 1 4 5 5 6 6 7 7 4 -1 -1
4 1 2 1 3 1 4 -1 -1
3 1 2 2 3 3 1 -1 -1
3 1 2 2 1 -1 -1
0

Sample Output

1
2
3
4
5
Set 1: Minimum links to open is 1
Set 2: Minimum links to open is 2
Set 3: Minimum links to open is 1
Set 4: Minimum links to open is 1
Set 5: Minimum links to open is 1

Solution

n < 15，窮舉哪幾個環需要剪開，接著把這些需要剪開的環先抽出來，查看剩餘的鐵環的情況，必須滿足都是鏈狀，而且連通元件的個數不能大於剪開的個數 + 1，如此一來，在放回剪開的環才能串在一起。

鏈狀的檢查：檢查每一個 node 的 degree 不可大於 2，同時不應該存在環。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int g[16][16], gmask[16];
int visited[16];
int dfs(int u, int p, int open, int n) {
	visited[u] = 1;
	for (int i = 0; i < n; i++) {
		if ((open>>i)&1)
			continue;
		if (g[u][i] == 0 || i == p)
			continue;
		if (visited[i] || dfs(i, u, open, n))
			return 1;
	}
	return 0;
}
int checkChain(int open, int n) {
	for (int i = 0; i < n; i++) {
		if ((open>>i)&1)
			continue;
		int t = gmask[i]^(gmask[i]&open);
		int degree = __builtin_popcount(t);
		if (degree > 2)
			return 0;
	}
	
	int op = __builtin_popcount(open);
	int comp = 0;
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < n; i++) {
		if ((open>>i)&1)	continue;
		if (visited[i] == 0) {
			if (dfs(i, -1, open, n)) // have cycle
				return 0;
			comp++;
		}
	}
	return op >= comp - 1;
}
int main() {
	int cases = 0;
	int n, x, y;
	while (scanf("%d", &n) == 1 && n) {
		memset(g, 0, sizeof(g));
		memset(gmask, 0, sizeof(gmask));
		while (scanf("%d %d", &x, &y) == 2) {
			if (x == -1)	break;
			x--, y--;
			g[x][y] = g[y][x] = 1;
			gmask[x] |= 1<<y, gmask[y] |= 1<<x;
		}
		
		int ret = 0x3f3f3f3f;
		for (int i = 0; i < (1<<n); i++) { // 1: open.
			int op = __builtin_popcount(i);
			if (op >= ret)	continue;
			if (checkChain(i, n))
				ret = min(ret, op); 
		}
		printf("Set %d: Minimum links to open is %d\n", ++cases, ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 814 - The Letter Carrier's Rounds

Problem

模擬郵件發送的協定訊息，給定給一台 mail server 上的使用者名稱，接著發送群組訊息。

每一組發送者，會按照輸入順序的 mail server，將相同的 server 上的使用者統一發送，如果存在不合法的使用者名稱，必須回傳找不到，如果對一個 mail server 中都沒有合法使用者，則忽略此次傳送。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report!  --Fiona
*
*

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Connection between Cairo and MexicoCity
     HELO Cairo
     250
     MAIL FROM:<Hamdy@Cairo>
     250
     RCPT TO:<Conrado@MexicoCity>
     250
     RCPT TO:<Lisa@MexicoCity>
     550
     DATA
     354
     Congratulations on your efforts !!
     --Hamdy
     .
     250
     QUIT
     221
Connection between Cairo and SanFrancisco
     HELO Cairo
     250
     MAIL FROM:<Hamdy@Cairo>
     250
     RCPT TO:<Shariff@SanFrancisco>
     250
     DATA
     354
     Congratulations on your efforts !!
     --Hamdy
     .
     250
     QUIT
     221
Connection between London and HongKong
     HELO London
     250
     MAIL FROM:<Fiona@London>
     250
     RCPT TO:<Chen@HongKong>
     250
     DATA
     354
     Thanks for the report!  --Fiona
     .
     250
     QUIT
     221
Connection between London and Paris
     HELO London
     250
     MAIL FROM:<Fiona@London>
     250
     RCPT TO:<Natasha@Paris>
     550
     QUIT
     221

Solution

一個純模擬的題目，關於此類協定可以在計算機網路中學到。

保證寄信者都是合法的，小心每一行的資訊可能很長，用 char array 很容易 buffer overflow。也因此掛了很多 WA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <vector> 
using namespace std;
set<string> MTA;
int readMTA() {
	string cmd, mta, name;
	int n;
	while (cin >> cmd) {
		if (cmd == "*")	return 1;
		cin >> mta >> n; 
		for (int i = 0; i < n; i++) {
			cin >> name;
			MTA.insert(string(name) + "@" + string(mta));
		}
	}
	return 0;
}
void parse_address(const string& s, string& user, string& mta) {
  int k = s.find('@');
  user = s.substr(0, k);
  mta = s.substr(k+1);
}
int main() {
	string msg;
	readMTA();
	while (cin >> msg) {
		if (msg[0] == '*')	break;	
		vector<string> user, mta, mail;
		set<string> S;
		vector<int>	used;
		string u, m;
		parse_address(msg, u, m);
		user.push_back(u), mta.push_back(m);
		while (cin >> msg && msg[0] != '*') {
			parse_address(msg, u, m);
			if (S.count(u + "@" + m))	continue;
			S.insert(u + "@" + m);
			user.push_back(u), mta.push_back(m);
		}
		while (getchar() != '\n');
		while (getline(cin, msg) && msg[0] != '*')
			mail.push_back(msg);
		used.resize(user.size(), 0);
		for (int i = 1; i < user.size(); i++) {
			if (used[i])	continue;
			printf("Connection between %s and %s\n", mta[0].c_str(), mta[i].c_str());
			printf("     HELO %s\n", mta[0].c_str());
			printf("     250\n");
			printf("     MAIL FROM:<%s@%s>\n", user[0].c_str(), mta[0].c_str());
			printf("     250\n");
			int s = 0;
			for (int j = i; j < user.size(); j++) {
				if (mta[j] == mta[i]) {
					used[j] = 1;
					printf("     RCPT TO:<%s@%s>\n", user[j].c_str(), mta[j].c_str());
					if (MTA.count(user[j] + "@" + mta[j]))
						printf("     250\n"), s++;
					else
						printf("     550\n");
				}
			}
			if (s > 0) {
				printf("     DATA\n");
				printf("     354\n");
				for (int j = 0; j < mail.size(); j++)
					printf("     %s\n", mail[j].c_str());
				printf("     .\n");
				printf("     250\n");
			}
			printf("     QUIT\n");
			printf("     221\n");
		}
	}
	return 0;
}
/*
MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report!  --Fiona
*
*
*/
Read More +