解題區►解題區 - UVa

UVa 298 - Race Tracks

Problem

給定一個 N * M 的地圖，接著將會從起點出發抵達終點，一開始的速度為 (0, 0)，在下一個時刻，每一個維度的速度可以調整 -3, -2, -1, 0, 1, 2, 3 (也就是加速度)，但是速度的絕對值必須小於等於 3，同時給定這張地圖的矩形障礙物，移動的過程中不用考慮會不會遇到障礙物，只需要考慮跳躍落下的地點是否有障礙物。

Sample input

1
2
3
4
5
6
7
8
9
10
2
5 5
4 0 4 4
1
1 4 2 3
3 3
0 0 2 2
2
1 1 0 2
0 2 1 1

Sample output

1
2
Optimal solution takes 7 hops.
No solution.

Solution

bfs 廣度搜索

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
#include <stdio.h> 
#include <queue>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int g[64][64];
int testcase, N, M, P;
int sx, sy, ex, ey;
void bfs() {
	int dp[64][64][8][8] = {};
	queue<int> X, Y, VX, VY;
	int x, y, vx, vy, tx, ty, dx, dy;
	dp[sx][sy][0+3][0+3] = 1;
	X.push(sx), Y.push(sy), VX.push(0), VY.push(0);
	while(!X.empty()) {
		x = X.front(), X.pop();
		y = Y.front(), Y.pop();
		vx = VX.front(), VX.pop();
		vy = VY.front(), VY.pop();
		if(x == ex && y == ey) {
			printf("Optimal solution takes %d hops.\n", dp[x][y][vx+3][vy+3]-1);
			return;
		}
		for(int i = -1; i <= 1; i++) {
			for(int j = -1; j <= 1; j++) {
				dx = vx + i, dy = vy + j;
				if(abs(dx) <= 3 && abs(dy) <= 3) {
					tx = x + dx, ty = y + dy;
					if(tx < 0 || tx >= N || ty < 0 || ty >= M || dp[tx][ty][dx+3][dy+3])
						continue;
					if(g[tx][ty])
						continue;
					dp[tx][ty][dx+3][dy+3] = dp[x][y][vx+3][vy+3] + 1;
					X.push(tx), Y.push(ty);
					VX.push(dx), VY.push(dy);
				} 
			}
		}
	}
	puts("No solution.");
}
int main() {
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d", &N, &M);
		scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
		scanf("%d", &P);
		memset(g, 0, sizeof(g));
		for(int i = 0; i < P; i++) {
			int lx, ly, rx, ry;
			scanf("%d %d %d %d", &lx, &rx, &ly, &ry);
			for(int p = lx; p <= rx; p++)
				for(int q = ly; q <= ry; q++)
					g[p][q] = 1;
		}
		bfs();
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 268 - Double Trouble

Problem

在一個 B 進制數中，找到一個最小的數字 X，使得 2 * X 的結果恰好是 X 循環右移一位的結果 (意即最末位的數字推到首位，其餘往右推一位)。

例如範例給的

1
2
 X = 421052631578947368 
2X = 842105263157894736

末尾的 8 移動到首位，其餘往右推一位。

Sample Input

1
2
3
2
10
35

Sample Output

1
2
3
4
5
6
For base 2 the double-trouble number is
0 1
For base 10 the double-trouble number is
0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1
For base 35 the double-trouble number is
11 23

Solution

假設末位數字是 M，且 M 的數值一定介於 $ 0 <= M < B $，最後根據公式推

$$2*(NM) = MN, 0 \le M < B \\ 2(N * B + M) = N + B^{(k-1)} * M \\ N = M * \frac{(B^{(k-1)} - 2)}{(2 * B - 1)}$$

從位數少開始窮舉，再依序從 M 小的開始窮舉，找到可以整除的整數 N 值，做一次小整數的大數乘除法即可，並不會太難。

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>
/* 
2*(NM) = MN, 0 <= M < B
2(N * B + M) = N + B^(k-1) * M
N = M * (B^(k-1) - 2)/(2 * B - 1)
*/
int main() {
	int B;
	while(scanf("%d", &B) == 1) {
		printf("For base %d the double-trouble number is\n", B);
		
		int d, product = 1, M;
		for(int k = 1; k < 1024; k++) {
			int ok = 0;
			for(M = 1; M < B; M++) {
				if((M * (product - 2))%(2 * B - 1) == 0) {
					ok = 1, d = k;
					break;
				}
			}
			if(ok)	break;
			product = (product * B)%(2 * B - 1);
		}
		
		int N[1024] = {};
		N[d - 1] = 1;
		for(int i = 0, carry = -2; i <= d; i++) {
			N[i] += carry;
			if(N[i] < 0) {
				N[i] += B, carry = -1;
			} else {
				break;
			}
		}
		
		for(int i = 0; i <= d; i++)
			N[i] *= M;
		for(int i = 0; i <= d; i++)
			N[i+1] += N[i]/B, N[i] %= B;
		for(int i = d, j = 0; i >= 0; i--) {
			j = j * B + N[i];
			N[i] = j / (2 * B - 1), j %= (2 * B - 1);
		}
		for(int i = d-2; i >= 0; i--)
			printf("%d ", N[i]);
		printf("%d \n", M);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 250 - Pattern Matching Prelims

Problem

對於一個 N * M 的灰階矩陣，找一個重心 $(c_{x}, c_{y})$，重心會符合將

$$|column[0, c_{x}-1] - column[c_{x}+1, N-1]| \\ |row[0, c_{y}-1] - row[c_{y}+1, M-1]|$$

最小化, 其中 column, row 表示該列、該行的總和。如果有數個相同，則盡可能輸出最右小角的座標 (座標值越大越好)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 5
0.1 0.2 0.1 0.2 0.1
0.1 0.2 0.3 0.1 0.1
0.2 0.3 0.1 0.1 0.3
0.4 0.1 0.1 0.1 0.2
0.2 0.2 0.3 0.3 0.1
5 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2
0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3
0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.6
0 0

Sample Output

1
2
Case 1: center at (3, 3)
Case 2: center at (4, 6)

Solution

其實會發現 x 軸、y 軸的結果可以分開計算，是不會影響最後的結果，兩別分別取最佳的位置即可。

而為了求這個值，累計每一行、列的總和，使用 O(n) 掃描計算即可。參照代碼。

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
#include <stdio.h>
#include <math.h>
int main() {
#define eps 1e-6
	int n, m, cases = 0;
	while(scanf("%d %d", &n, &m) == 2 && n+m) {
		double row[128] = {}, col[128] = {};
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				double x;
				scanf("%lf", &x);
				row[i] += x, col[j] += x;
			}
		}
		double left = 0, right = 0;
		double diff = 1e+30;
		int cx, cy;
		for(int i = 1; i < n; i++)
			right += row[i];
		for(int i = 0; i < n; i++) {
			if(fabs(right - left) < diff + eps) {
				diff = fabs(right - left);
				cx = i;
			}
			left += row[i], right -= row[i+1];
		}
		left = right = 0;
		diff = 1e+30;
		for(int i = 1; i < m; i++)
			right += col[i];
		for(int i = 0; i < m; i++) {
			if(fabs(right - left) < diff + eps) {
				diff = fabs(right - left);
				cy = i;
			}
			left += col[i], right -= col[i+1];
		}
		printf("Case %d: center at (%d, %d)\n", ++cases, cx+1, cy+1);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 239 - Tempus et mobilius. Time and motion

Problem

有一個神秘的球時鐘，球時鐘會有三個堆疊位置，分別是存放每分鐘、每五分鐘、每一個小時的球球，軌道每一分鐘會將一個球釋出，並且滾入位置，放置的位置優先順序為每分鐘、每五分鐘、每小時。

如果滾入的位置分別滿了 5, 12, 12 個球，則該位置的球將會按照原本進入順序的反順序放入軌道隊列的最晚端。在剛好滿的那個瞬間，那個球將會到次優先的位置去。

假使球有各自的編號，請問在第幾天的同一個時刻後，會回到原本的位置。

Sample Input

1
2
3
30
45
0

Sample Output

1
2
30 balls cycle after 15 days.
45 balls cycle after 378 days.

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
#include <stdio.h> 
#include <stack>
#include <queue>
using namespace std;
long long gcd(long long x, long long y) {
	for(long long t; x%y; t = x, x = y, y = t%y);
	return y;
}
int main() {
	int n;
	while(scanf("%d", &n) == 1 && n) {
		// simulation
		queue<int> Q;
		stack<int> minute, five, hour;
		for(int i = 0; i < n; i++)
			Q.push(i);
		for(int i = 0; i < 24 * 60; i++) {
			int x = Q.front();
			Q.pop();
			if(minute.size() < 4) {
				minute.push(x);
			} else {
				while(!minute.empty())
					Q.push(minute.top()), minute.pop();
				if(five.size() < 11)
					five.push(x);
				else {
					while(!five.empty())
						Q.push(five.top()), five.pop();
					if(hour.size() < 11)
						hour.push(x);
					else {
						while(!hour.empty())
							Q.push(hour.top()), hour.pop();
						Q.push(x);
					}
				}
			}
		}
		
		// permutation group
		int M[8192], visited[8192] = {};
		for(int i = 0; i < n; i++)
			M[i] = Q.front(), Q.pop();
		long long ret = 1;
		for(int i = 0; i < n; i++) {
			if(visited[i] == 0) {
				int j, len = 1;
				visited[i] = 1;
				for(j = M[i]; j != i; j = M[j]) {
					visited[j] = 1, len++;
				}
				ret = ret / gcd(ret, len) * len;
			}
		}
		printf("%d balls cycle after %lld days.\n", n, ret);  
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 221 - Urban Elevations

Problem

給定一個三維空間建築物配置，給予每一個建築物西南方的端點，以及距離的深度，面向的建築物寬度和高度。求從南面往北面看過去，有多少建築物是可以被看到一部分的？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
14
160 0 30 60 30
125 0 32 28 60
95 0 27 28 40
70 35 19 55 90
0 0 60 35 80
0 40 29 20 60
35 40 25 45 80
0 67 25 20 50
0 92 90 20 80
95 38 55 12 50
95 60 60 13 30
95 80 45 25 50
165 65 15 15 25
165 85 10 15 35
0

Sample Output

1
2
For map #1, the visible buildings are numbered as follows:
5 9 4 3 10 2 1 14

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Building {
	int x, y;
	int width, depth, height, label;
	int in() {
		return scanf("%d %d %d %d %d", &x, &y, &width, &depth, &height) == 5;
	}
	bool operator<(const Building &a) const {
		if(make_pair(x, y) != make_pair(a.x, a.y))
			return make_pair(x, y) < make_pair(a.x, a.y);
		return depth < a.depth;
	}
}; 
int coverL(vector< pair<int, int> > interval, int l, int r) {
	sort(interval.begin(), interval.end());
	int y = l;
	for(int i = 0; i < interval.size(); i++) {
		if(interval[i].first <= y)
			y = max(y, interval[i].second);
		else
			return 0;
	}
	return y >= r;
}
void solve(Building D[], int n) {
	sort(D, D+n);
	int f = 0;
	for(int i = 0; i < n; i++) {
		vector< pair<int, int> > interval;
		for(int j = 0; j < n; j++) {
			if(j == i)	continue;
			if(D[i].height > D[j].height || D[i].y <= D[j].y)
				continue;
			int l = max(D[i].x, D[j].x), r = min(D[i].x+D[i].width, D[j].x+D[j].width);
			if(l < r)
				interval.push_back(make_pair(l, r));
		}
		if(!coverL(interval, D[i].x, D[i].x + D[i].width)) {
			if(f++)	putchar(' ');
			printf("%d", D[i].label + 1);
		}
	}
	puts("");
}
int main() {
	int n, cases = 0;
	Building D[128];
	while(scanf("%d", &n) == 1 && n) {
		for(int i = 0; i < n; i++)
			D[i].in(), D[i].label = i;
		if(cases++)	puts("");
		printf("For map #%d, the visible buildings are numbered as follows:\n", cases);
		solve(D, n);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 215 - Spreadsheet Calculator

Problem

給一張 N * M 的試算表，並且給定每一格的值可以倚靠其他欄位的結果。是否存在循環依賴？如果不存在則將每一格的答案計算出，否則將輸出存有循環依賴上的所有格子情形。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0

Sample Output

1
2
3
4
5
6
7
      0     1
A     3     5
B     3    -2
A0: A0
B0: C1
C1: B0+A1

Solution

其實就最簡單就是利用高斯消去找解，但是測資中最討厭的地方在於假使 A0 = A0-A0 這種情況也要算依賴關係，那麼高斯消去仍然找得到所有變數的解。

所以最後還是弄一個 dfs 找是否會抵達環上任何一點。

如果將這些資訊排除，圖就是一個 DAG，不用高斯消去也是相當容易的模擬計算。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
void gaussianElimination(double mtx[][256], int n, double sol[], int nosol[]) {
#define eps 1e-6
    int i, j;		
    for(i = 0; i < n; i++) {
        int k = i;
        for(j = i; j < n; j++)
            if(fabs(mtx[k][i]) < fabs(mtx[j][i]))
                k = j;
        if(fabs(mtx[k][i]) < eps)
            continue;
        if(k != i) {
            for(j = 0; j <= n; j++)
                swap(mtx[k][j], mtx[i][j]);
        }
        for(j = 0; j < n; j++) {
            if(i == j)  continue;
            for(k = n; k >= i; k--) {
                mtx[j][k] -= mtx[j][i]/mtx[i][i]*mtx[i][k];
            }
        }
    }	
//	for(int i = 0; i < n; i++) {
//		for(int j = 0; j <= n; j++)
//			printf("%lf ", mtx[i][j]);
//		puts("");
//	}
    for(int i = 0; i < n; i++)
    	nosol[i] = 0;
    for(i = n-1; i >= 0; i--) {
        if(fabs(mtx[i][i]) < eps)
            nosol[i] = 1;
        else {
            if(fabs(mtx[i][n]) < eps)
                sol[i] = 0;
            else
                sol[i] = mtx[i][n]/mtx[i][i];
        }
        for(j = i+1; j < n; j++)
            if(fabs(mtx[i][j]) > eps && nosol[j])
                nosol[i] = 1;
    }
}
vector<int> depend[512];
int visited[512], in_stk[512];
int dfs(int u, int p) {
	visited[u] = 1, in_stk[u] = 1; 
	for(int i = 0; i < depend[u].size(); i++) {
		int v = depend[u][i];
		if(in_stk[v])	return 1;
		if(visited[v] == 0 && dfs(v, u))
			return 1;
	}
	in_stk[u] = 0;
	return 0;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int N, M;
	char s[1025], exp[32][32][128];
	while(scanf("%d %d", &N, &M) == 2 && N+M) {
		while(getchar() != '\n');
		
		int notsolvable[256];
		double f[256][256] = {}, value[256];
		
		for(int i = 0; i < N * M; i++) {
			depend[i].clear();
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				scanf("%s", s);
				strcpy(exp[i][j], s);
				int sign = 1;
				f[i * M + j][i * M + j] = 1;
				for(int k = 0; s[k]; k++) {
					if(s[k] == '+')			sign = 1;
					else if(s[k] == '-')	sign = -1;
					else if('0' <= s[k] && s[k] <= '9') {
						int num = 0;
						while('0' <= s[k] && s[k] <= '9')
							num = num * 10 + s[k] - '0', k++;
						k--;
						f[i * M + j][N * M] += sign * num;
					} else {
						int rol = s[k] - 'A', num = 0;
						k++;
						while('0' <= s[k] && s[k] <= '9')
							num = num * 10 + s[k] - '0', k++;
						k--;
						f[i * M + j][rol * M + num] -= sign;
						depend[i * M + j].push_back(rol * M + num);
					}
				}
			}
		}
		gaussianElimination(f, N*M, value, notsolvable);
		for(int i = 0; i < N*M; i++) {
			memset(visited, 0, sizeof(visited));
			memset(in_stk, 0, sizeof(in_stk));
			notsolvable[i] |= dfs(i, i);
		}
		int allsol = 1;
		for(int i = 0; i < N*M; i++) {
//			printf("%lf %d\n", value[i], notsolvable[i]);
			allsol &= !notsolvable[i];
		}
		if(allsol) {
			printf(" ");
			for(int i = 0; i < M; i++)
				printf("%6d", i);
			puts("");
			for(int i = 0; i < N; i++) {
				printf("%c", i + 'A');
				for(int j = 0; j < M; j++)
					printf("%6d", (int)value[i * M +j]);
				puts("");
			}
		} else {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(notsolvable[i * M + j]) {
						printf("%c%d: %s\n", i + 'A', j, exp[i][j]);
					}
				}
			}
		}
		puts("");
	} 
	return 0;
}
/*
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0
*/
Read More +
解題區►解題區 - UVa

UVa 11871 - New Land

Problem

題目給定在 n * m 的格子中，以及一些障礙物，求一個最大空白矩形。

Sample Input

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

Sample Output

1
2
Case 1: 12
Case 2: 3

Solution

帶入單調堆。

線性時間 O(NM) 完成。紀錄每一列的向左拓展最寬為何，然後對於每一列(假設它是矩形的最右側的邊上)找到最大矩形。

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
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
#define maxL ((2048*2048)>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
// http://mypaper.pchome.com.tw/zerojudge/post/1326159411
int solve(int n, int h[]) {
    int ret = 0;
    int i, height;
    stack< pair<int, int> > stk;// <height, position>
    pair<int, int> e;
    stk.push(make_pair(-1, 0));
    h[n] = 0;// visual height.
    for(i = 0; i <= n; i++) {
        height = h[i];
        e = make_pair(height, i);
        while(height < stk.top().first) {
            e = stk.top(), stk.pop();
            ret = max(ret, (i - e.second) * e.first);
        }
        if(height > stk.top().first)
            stk.push(make_pair(height, e.second));
    }
    return ret;
}    
int n, m, h[2048];
int main() {
	int k, c, x, cases = 0, testcase;
	ReadInt(&testcase);
    while(testcase--) {
    	ReadInt(&n);
    	ReadInt(&m);
    	memset(mark, 0, sizeof(mark));
    	memset(h, 0, sizeof(h));
        for(int i = 0; i < n; i++) {
        	ReadInt(&k);
        	ReadInt(&c);
        	int pos = 0;
            for(int j = 0; j < k; j++) {
            	ReadInt(&x);
				c = !c;
				if(c) {
            		while(x--)
            			SET(i * 2048 + pos), pos++;
            	} else {
            		pos += x;
            	}
            }
        }
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
            	if(GET(j * 2048 + i))
            		h[j]++;
            	else
            		h[j] = 0;
            }
            ret = max(ret, solve(n, h));
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11870 - Antonyms

Problem

告訴你那些是同義詞，以及誰與誰是反義詞，最後回報是否有矛盾情況。

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 2
big large
small tiny
big small
tiny huge
2 1
xyz abc
abc def
def xyz
1 3
fire flame
fire ice
ice water
water fire

Sample Input

1
2
3
Case 1: YES
Case 2: NO
Case 3: NO

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
#include <stdio.h> 
#include <string.h>
#include <map>
#include <iostream>
using namespace std;
int p[2048], rank[2048];
int findp(int x) {
	return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
	x = findp(x), y = findp(y);
	if(x == y)	return 0;
	if(rank[x] > rank[y])
		p[y] = x, rank[x] += rank[y];
	else
		p[x] = y, rank[y] += rank[x];
	return 1;
}
int main() {
	int testcase, cases = 0, N, M;
	char s[1024];
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d", &N, &M);
		map<string, int> R;
		int size = 0;
		for(int i = 0; i < 2048; i++)
			p[i] = i, rank[i] = 1;
		for(int i = 0; i < N; i++) {
			scanf("%s", s);
			int &x = R[s];
			if(x == 0)	x = ++size;
			scanf("%s", s);
			int &y = R[s];
			if(y == 0)	y = ++size;
			joint(2 * x, 2 * y);
		}
		int ret = 1;
		for(int i = 0; i < M; i++) {
			scanf("%s", s);
			int &x = R[s];
			if(x == 0)	x = ++size;
			scanf("%s", s);
			int &y = R[s];
			if(y == 0)	y = ++size;
			if(findp(2 * x) == findp(2 * y))
				ret = 0;
			joint(2 * x + 1, 2 * y);
			joint(2 * y + 1, 2 * x);
		}
		printf("Case %d: %s\n", ++cases, ret ? "YES" : "NO");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11851 - Celebrity Split

Problem

家產劃分給兩個人，兩個人分配的房子總價值必須相同，剩下無法劃分的房子將換成現金分配給兩個人，求換成現金的總額最小為何？

Sample Input

1
2
3
4
5
6
7
5
6000000
30000000
3000000
11000000
3000000
0

Output for Sample Input

1
41000000

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <functional>
using namespace std;
int n;
long long A[32], suffix[32], ret;
void dfs(int i, long long x, long long y, long long sold) {
	if(sold >= ret || abs(x - y) > suffix[i])	return;
	if(x == y)
		ret = min(ret, sold + suffix[i]);
	if(i == n)
		return;
	if(x == y) {
		dfs(i+1, x + A[i], y, sold);
		dfs(i+1, x, y, sold + A[i]);
	} else {
		dfs(i+1, x + A[i], y, sold);
		if(x)
			dfs(i+1, x, y + A[i], sold);
		dfs(i+1, x, y, sold + A[i]);
	}
}
int main() {
	while(scanf("%d", &n) == 1 && n) {
		for(int i = 0; i < n; i++)
			scanf("%lld", &A[i]);
		sort(A, A+n, greater<long long>());
		suffix[n] = 0;
		for(int i = n-1; i >= 0; i--)
			suffix[i] = suffix[i+1] + A[i];
		ret = 1LL<<60;
		dfs(0, 0, 0, 0);
		printf("%lld\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11848 - Cargo Trains

Problem

在 N 個點的地圖中，有兩家運輸公司 A, B，如果它們都有在 x, y 之間部屬線路，則運輸費用將會根據參數 a 進行調整 a * Ca + (1 - a) * Cb，求從編號 0 到 N-1 的最少花費為何。

Sample input

1
2
3
4
5
6
7
8
9
3 2 2 3
0 1 100
1 2 200
0 1 200
1 2 150
0
1
0.5
-1 -1 -1 -1

Sample Output

1
2
3
350
300
325

Solution

每一次詢問 a 的時候，就做一次 spfa。似乎沒有別的方法可以預處理訊息。

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
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
int gA[128][128], gB[128][128];
int spfa(int st, int ed, int n, double p) {
	double dist[128];
	int inq[128] = {}, u, v;
	queue<int> Q;
	for(int i = 0; i < n; i++)
		dist[i] = 1e+10;
	dist[st] = 0, Q.push(st);
	while(!Q.empty()) {
		u = Q.front(), Q.pop();
		inq[u] = 0;
		for(int i = 0; i < n; i++) {
			int wa = gA[u][i], wb = gB[u][i];
			double cost = 0;
			if(wa < 0 && wb < 0)	continue;
			if(wa >= 0 && wb >= 0)
				cost = wa * p + wb * (1-p);
			else
				cost = wa >= 0 ? wa : wb;
			if(dist[i] > dist[u] + cost) {
				dist[i] = dist[u] + cost;
				if(!inq[i])
					inq[i] = 1, Q.push(i);
			}
		}
	}
	return (int)dist[ed];
}
int main() {
	int N, Na, Nb, Q;
	int x, y, v;
	double p;
	while(scanf("%d %d %d %d", &N, &Na, &Nb, &Q) == 4 && N >= 0) {
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				gA[i][j] = gB[i][j] = -1;
		for(int i = 0; i < Na; i++) {
			scanf("%d %d %d", &x, &y, &v);
			if(gA[x][y] != -1)
				gA[x][y] = gA[y][x] = min(gA[x][y], v);
			else
				gA[x][y] = gA[y][x] = v;
		}
		for(int i = 0; i < Nb; i++) {
			scanf("%d %d %d", &x, &y, &v);
			if(gB[x][y] != -1)
				gB[x][y] = gB[y][x] = min(gB[x][y], v);
			else
				gB[x][y] = gB[y][x] = v;
		}
		for(int i = 0; i < Q; i++) {
			scanf("%lf", &p);
			printf("%d\n", spfa(0, N-1, N, p));
		}
	}
	return 0;
}
Read More +