解題區►解題區 - UVa

UVa 12052 - Cyber cafe

Problem

給一張圖有 N 個節點、M 條邊，其中要放置 S 台新主機於其中 S 個節點，而沒放置的節點繼續使用舊主機，為了服務舊主機的網咖，每個舊節點旁邊最多只能有一個新主機網咖。

請問有多少種放置方法。

Sample Input

1
2
3
4
5
6
7
8
9
10
Dhaka
6 2 7
AB BC CD DE EF FA AD
Chittagong
4 3 4
AB AC AD BC
Sylhet
3 2 3
AB BC CA
TheEnd

Sample Output

1
2
3
4
5
6
7
Dhaka
9
Chittagong
1
Sylhet
0
TheEnd

Solution

對於每一個節點的連接方式用一個 32-bit 壓縮，接著窮舉所有可能放置方法 state，對於沒有放置的節點，直接壓縮結果與 state 做 AND 運算，算 bits 數是否都小於 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
	char ss[1024];
	int n, s, p;
	while (scanf("%s", &ss) == 1) {
		printf("%s\n", ss);
		if (!strcmp(ss, "TheEnd"))
			break;
		scanf("%d %d %d", &n, &s, &p);
		int g[26][26] = {};
		for (int i = 0; i < p; i++) {
			scanf("%s", ss);
			int x = ss[0] - 'A', y = ss[1] - 'A';
			g[x][y] = g[y][x] = 1;
		}
		int mask[26] = {};
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				mask[i] |= g[i][j]<<j;
		int ret = 0;
		for (int i = (1<<n)-1; i >= 0; i--) {
			if (__builtin_popcount(i) == s) {
				int ok = 1;
				for (int j = 0; j < n && ok; j++) {
					if ((i>>j)&1)	continue;
					if (__builtin_popcount(mask[j]&i) >= 2)
						ok = 0;
				}
				ret += ok;
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12051 - Mazes in Higher Dimensions

Problem

好比 2D 方格，從左下角到右上角的方法數。而這一題是在三維空間，一樣的方式要越來越靠近右上方的頂點，但是部分點會有障礙物，會造成無法通行。

題目給定的維度事實上是終點座標，而非該維度數，用 row major 的時候要計算 dim[i]+1。

Sample Input

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

Sample Output

1
2
Case 1: 756756
Case 2: 6318655200

Solution

特地用懶標記完成 dp 計算，但是忘了有可能無法抵達終點，忘了補上最對於終點的懶標記操作，直接輸出 dp[ret] 結果一直噴 WA。

懶標記檢查 if (used[ret] != testcase) dp[ret] = 0;。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXN 3000005
long long dp[MAXN] = {};
int used[MAXN] = {}, ob[MAXN] = {}; // obstacle
int main() {
	memset(dp, 0, sizeof(dp));
	memset(ob, 0, sizeof(ob));
	memset(used, 0, sizeof(used));
	int n, m, dim[16], row[16], v[16];
	int testcase = 0, cases = 0;
	while (scanf("%d %d", &n, &m) == 2 && n+m) {
		for (int i = 0; i < n; i++) {
			scanf("%d", &dim[i]);
			dim[i]++;
		}
		testcase++;
		row[n - 1] = 1;
		for (int i = n - 2; i >= 0; i--)
			row[i] = row[i+1] * dim[i+1];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++)
				scanf("%d", &v[j]);
			int x = 0;
			for (int j = 0; j < n; j++)
				x += v[j] * row[j];
			ob[x] = testcase;
		}
		if(ob[0] == testcase){
            printf("Case %d: 0\n", ++cases);
            continue;
        }
		int ret = 0;
		for (int i = 0; i < n; i++)
			ret += (dim[i] - 1) * row[i];
		queue<int> Q;
		Q.push(0), used[0] = testcase;
		dp[0] = 1;
		while (!Q.empty()) {
			int x = Q.front();
			Q.pop();
			long long ways = dp[x];
			for (int i = 0; i < n; i++)
				v[i] = x / row[i], x %= row[i];
			for (int i = 0; i < n; i++) {
				v[i]++;
				if (v[i] < dim[i]) {
					x = 0;
					for (int j = 0; j < n; j++)
						x += v[j] * row[j];
					if (ob[x] != testcase) {
						if (used[x] != testcase)
							dp[x] = 0;
						dp[x] += ways;
						if (used[x] != testcase)
							Q.push(x), used[x] = testcase;
					}
				}
				v[i]--;
			}
		}
		if (used[ret] != testcase)	dp[ret] = 0;
		printf("Case %d: %lld\n", ++cases, dp[ret]);
	}
	return 0;
}
/*
3 0 
5 5 5
 
3 1 
9 8 7
1 1 1
3 2
9 8 7
1 1 1
5 6 6
3 2
9 8 7
2 3 4
9 8 7
3 2
9 8 7
2 3 4
9 8 7
0 0
*/
Read More +
解題區►解題區 - UVa

UVa 10381 - The Rock

Problem

給定一個 N x M 地圖，已知有部分的牆壁和一個透明的牆壁，每一個障礙物都佔據一個方格，而透明牆壁一開始不知道位於何處，直到碰壁的時候才發現，找一條最慘情況下的最短路徑。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
 
3 4
..X.
.##.
.E..

Sample Output

1
2
15
11

Solution

最小化最大值，首先窮舉任何一個透明牆壁可能出現的地方，對於透明牆壁的鄰近四格建立再碰壁方向下，抵達終點的最短路徑。

接著，使用最短路的方式進行更新，在這裡使用 dijkstra 的方式，對於每一個點的狀態為 (走到這裡第幾步) = 從起點走到這，最慘的偏移路徑最小化 為何。

概念上理解，設計一條路徑，路徑畫好後，對於每一點賭下一個點就是透明牆壁，偏移路徑長最長為何就會是該路徑的花費。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <assert.h>
#include <algorithm>
using namespace std;
char g[64][64];
int dist[64][64], walldist[64][64][4];
int n, m;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
struct State {
	int x, y;
	int g, h;
	State(int a=0, int b=0, int c=0, int d=0):
		x(a), y(b), g(c), h(d) {}
	bool operator<(const State &a) const {
		return h > a.h;
	}
};
int dp[40][40][40 * 40];
int search(int sx, int sy, int ex, int ey) {
	priority_queue<State> pQ;
	State u, v;
	int tx, ty, h;
	pQ.push(State(sx, sy, 0, 0));
	memset(dp, 63, sizeof(dp));
	while (!pQ.empty()) {
		u = pQ.top(), pQ.pop();
		if (u.h > dp[u.x][u.y][u.g])
			continue;
		if (u.x == ex && u.y == ey)
			return u.h;
		for (int i = 0; i < 4; i++) {
			tx = u.x + dx[i], ty = u.y + dy[i];
			if (tx < 0 || ty < 0 || tx >= n || ty >= m)
				continue;
			if (g[tx][ty] == '#' || g[tx][ty] == 'E')
				continue;
			if (g[tx][ty] == '.') 
				h = max(u.h, u.g + walldist[u.x][u.y][i]);
			else if (g[tx][ty] == 'X')
				h = max(u.h, u.g);
			assert(u.g + 1 < 40 * 40);
			if (dp[tx][ty][u.g + 1] > h) {
				dp[tx][ty][u.g + 1] = h;
				pQ.push(State(tx, ty, u.g + 1, h));
			}
		}
	}
	return 0;
}
void bfs(int sx, int sy) {
	memset(dist, 63, sizeof(dist));
	queue<int> X, Y;
	int tx, ty;
	X.push(sx), Y.push(sy);
	dist[sx][sy] = 0;
	while (!X.empty()) {
		sx = X.front(), X.pop();
		sy = Y.front(), Y.pop();
		for (int i = 0; i < 4; i++) {
			tx = sx + dx[i], ty = sy + dy[i];
			if (tx < 0 || ty < 0 || tx >= n || ty >= m)
				continue;
			if (g[tx][ty] == '#' || dist[tx][ty] <= dist[sx][sy] + 1)
				continue;
			dist[tx][ty] = dist[sx][sy] + 1;
			X.push(tx), Y.push(ty);
		}
	}
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++)
			scanf("%s", g[i]);
		int sx, sy, ex, ey, tx, ty;
		
		memset(walldist, 0, sizeof(walldist));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (g[i][j] == 'E')	sx = i, sy = j;
				if (g[i][j] == 'X')	ex = i, ey = j;				
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (g[i][j] != '.')
					continue;
				g[i][j] = '#';
				bfs(ex, ey);
				for (int k = 0; k < 4; k++) {
					tx = i + dx[k], ty = j + dy[k];
					if (tx < 0 || ty < 0 || tx >= n || ty >= m)
						continue;
					if (g[tx][ty] == '#')
						continue;
					walldist[tx][ty][(k+2)%4] = dist[tx][ty];
				}
				g[i][j] = '.';
			}
		}
		int ret = search(sx, sy, ex, ey);
		printf("%d\n", ret);
	}
	return 0;
}
/*
2
8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
 
3 4
..X.
.##.
.E..
*/
Read More +
解題區►解題區 - UVa

UVa 12853 - The Pony Cart Problem

Problem

現在有一台馬車繞行一個圓，馬車內側輪胎畫出小圓、外側畫出大圓，現在知道馬車內側與外側輪胎之間的距離 D，同時知道內側輪胎每滾一圈，外側輪胎會滾 N 圈，請問外側輪胎畫出來的圓周長為何？

Sample Input

1
2
3
4
3
5.00 2.00
4.20 1.44
8.03 2.01

Sample Output

1
2
3
Case 1: 62.832
Case 2: 86.365
Case 3: 100.40

Solution

感謝峻維兄熱心翻譯

假設內側輪胎畫出小圓半徑為 A，兩個輪胎的半徑 B

$$\frac{ \frac{ 2 \pi A}{2 \pi B} }{ \frac{2 \pi (A + D)}{2 \pi A} } = N \\ \Rightarrow A = \frac{D}{N-1}$$

所求為 $2 \pi (A+D)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <math.h>
int main() {
	int testcase, cases = 0;
	const double pi = acos(-1);
	double D, N, A; 
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%lf %lf", &D, &N);
		A = D / (N - 1);
		double ret = 2 * pi * (A + D);
		printf("Case %d: %.3lf\n", ++cases, ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12849 - Mother's Jam Puzzle

Problem

有大中小三種類型的果醬瓶在三層的架子上，每一層有不同個數的果醬瓶。但是知道每一層的總果醬體積，反求大中小果醬瓶的容積。

Sample Input

1
2
3
4
5
6
7
2
3 3 1 20.00
6 0 2 20.00
6 4 0 20.00
3 0 1 6.00
0 2 2 10.00
1 3 1 10.00

Sample Output

1
2
Case 1: 1.11 3.33 6.67
Case 2: 1.00 2.00 3.00

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
void gaussianElimination(double mtx[][16], 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++)
		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;
	}
}
int main() {
	int testcase, cases = 0;
	double f[16][16], ret[16];
	int sol[16];
	scanf("%d", &testcase);
	while (testcase--) {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 4; j++)
				scanf("%lf", &f[i][j]);
		}
		gaussianElimination(f, 3, ret, sol);
		printf("Case %d: %.2lf %.2lf %.2lf\n", ++cases, ret[0], ret[1], ret[2]);
	}
	return 0;
}
/*
2
3 3 1 20.00
6 0 2 20.00
6 4 0 20.00
3 0 1 6.00
0 2 2 10.00
1 3 1 10.00
*/
Read More +
解題區►解題區 - UVa

UVa 12844 - Outwitting the Weighing Machine

Problem

有五個人要測體重，倆倆上去秤得到體重總和為何，現在反推每個人的體重為多少。

Sample Input

1
2
3
4
3
114 116 118 120 121 122 123 124 125 129
110 111 114 115 118 118 119 122 123 126
180 190 190 196 196 206 216 216 226 232

Sample Output

1
2
3
Case 1: 56 58 60 64 65
Case 2: 53 57 58 61 65
Case 3: 90 90 100 106 126

Solution

這題跟 10202 - Pairsumonious Numbers 一樣。

如果將體重、總和排序後 A[]、SUM[]，保證最小的 A[0] + A[1] = SUM[0]，和 A[0] + A[2] = SUM[1] 但是不曉得 A[0] + A[3] 和 A[1] + A[2] 哪個小，因此窮舉 A[1] + A[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
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
// same 10202 - Pairsumonious Numbers
int main() {
    int n, m, A[50], sum[50];
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	n = 5;
        m = n*(n-1)/2;
        for(int i = 0; i < m; i++)
            scanf("%d", &sum[i]);
        sort(sum, sum+m);
        
        printf("Case %d:", ++cases);
        multiset<int> oRB;
        for(int i = 2; i < m; i++)
            oRB.insert(sum[i]);
        int idx, flag = 0;
        for(int i = 2; i < m; i++) { // A[1]+A[2] = sum[i]
            if((sum[0]+sum[1]+sum[i])%2)
                continue;
            int tmp = (sum[0]+sum[1]+sum[i])/2;
            A[0] = tmp - sum[i];
            A[1] = tmp - sum[1];
            A[2] = tmp - sum[0];
            multiset<int> RB; // copy
            multiset<int>::iterator it;
            RB = oRB;
            it = RB.find(sum[i]);
            RB.erase(it);
            int pass = 1;
            for(int j = 3; j < n; j++) {
                it = RB.begin();// get min
                A[j] = (*it) - A[0];
                RB.erase(it);
                int ok = 1;
                for(int k = 1; k < j; k++) { // delete A[j]+A[0-(j-1)]
                    int tmp = A[j] + A[k];
                    it = RB.find(tmp);
                    if(it == RB.end()) {
                    	ok = 0;
                    	break;
                    }
                    RB.erase(it);
                }
                if(!ok)	{
                	pass = 0;
					break;
				}
            }
            if(pass) {// output ans
                flag = 1;
                for(int j = 0; j < n; j++)
                    printf(" %d", A[j]);
                puts("");
                break;
            }
        }
        if(!flag)
            puts("Impossible");
    }
    return 0;
}
/*
3
114 116 118 120 121 122 123 124 125 129
110 111 114 115 118 118 119 122 123 126
180 190 190 196 196 206 216 216 226 232
*/
Read More +
解題區►解題區 - UVa

UVa 12842 - The Courier Problem

Problem

軍隊筆直等速度移動，隊伍長度 L，信使位於隊伍最後面，要傳遞訊息到隊伍前方後跑回隊伍末端。跑回末端時候，隊伍已經前進 L 距離。求信使跑的距離為何？

Sample Input

1
2
1
50

Sample Output

1
Case 1: 120.71

Solution

假設軍隊移動速度 $v$, 信使移動速度 $u$。

看時間

$$\frac{L}{v} = \frac{L}{u-v} + \frac{L}{u+v} \\ u^{2} - v^{2} = 2v, \\ \text{Let u = 1, get } v = \frac{-2 + \sqrt{8} }{2}$$

輸出 $\frac{L}{v} u$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <math.h>
int main() {
	int testcase, cases = 0;
	double L;
	double u = 1, v = (-2 + sqrt(8))/ 2.0;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%lf", &L);
		double time = L / v;
		printf("Case %d: %.2lf\n", ++cases, time * u);
	}
	return 0;
}
/*
army v, courier u
time: 
L / v = L / (u - v) + L / (u + v) => u^2 - v^2 = 2v
result L / v * u, let u = 1 => v = (-2 + sqrt(8))/ 2.0.
*/
Read More +
解題區►解題區 - UVa

UVa 12841 - In Puzzleland (III)

Problem

給定一個無向圖，每一個頂點由大寫字母表示，找到從起點到終點，並且經過所有點 (每一個點最多經過一次) 的路徑，輸出最小字典順序的路徑。

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
3
12 14
A B C D E F U V W X Y Z
A F
A V
B U
B W
C D
C V
D Y
D W
E X
E Z
F U
F Y
U Z
W X
3 2
A B C
A B
A C
4 5
L N I K
L N
I L
I N
K N
K I

Sample Output

1
2
3
Case 1: AVCDYFUBWXEZ
Case 2: impossible
Case 3: LINK

Solution

一開始想說點數最多才 15，根據 D&C 的作法，拆分成兩塊 (分別有 N/2 個點)，其中一塊從起點開始、另一塊以終點結束的路徑。隨後再把兩塊組合在一起，找字典順序最小即可，看來是測資太多，很容易就 TLE，不過這方法是最穩定的，建表最慘需要 O(2^15 * 7!)。

由於可行狀態太多，也就是好死不死給一張接近完全圖，那上述的算法會超慢，如果要計算方法總數可能才會用到上述解法。而這一題直接 dfs 搜索，並且確保每一步走下去時，剩下的節點會在同一個連通元件上，不會拆分成兩塊。

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector> 
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[26];
char path[32];
int n, m, st, ed, used[26];
int bused[26] = {}, tused = 0;
int bfs(int u, int comp) {
	tused++;
	int cnt = 0, v;
	queue<int> Q;
	Q.push(u), bused[u] = tused;
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		cnt++;
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i];
			if (bused[v] != tused && used[v] == 0) {
				bused[v] = tused;
				Q.push(v);
			}
		}
	}
	return cnt == comp;
}
int dfs(int idx, int u) {
	path[idx] = u + 'A';
	if (idx < n - 1 && used[ed])	return 0;
	if (idx == n-1) {
		path[n] = '\0';
		puts(path);
		return 1;
	}
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (used[v] || !bfs(v, n - idx - 1))	
			continue;
		used[v] = 1;
		if(dfs(idx+1, v))	return 1;
		used[v] = 0;
	}
	return 0;
}
int main() {
	int testcase, cases = 0;
	int x, y;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		char name[26][4], s1[4], s2[4], buf[26];
		int mg[26][26] = {};
		for (int i = 0; i < 26; i++)
			g[i].clear();
		for (int i = 0; i < n; i++)
			scanf("%s", name[i]);
		for (int i = 0; i < m; i++) {
			scanf("%s %s", s1, s2);
			x = s1[0] - 'A', y = s2[0] - 'A';
			mg[x][y] = mg[y][x] = 1;
		}
		st = name[0][0] - 'A', ed = name[n-1][0] - 'A';
		for (int i = 0; i < 26; i++) {
			for (int j = 0; j < 26; j++) {
				if (mg[i][j])
					g[i].push_back(j);
			}
		}
		printf("Case %d: ", ++cases);
		memset(used, 0, sizeof(used));
		used[st] = 1;
		int f = dfs(0, st);
		if (!f)	puts("impossible");
	}
	return 0;
}
/*
3
12 14
A B C D E F U V W X Y Z
A F
A V
B U
B W
C D
C V
D Y
D W
E X
E Z
F U
F Y
U Z
W X
3 2
A B C
A B
A C
50
4 5
L N I K
L N
I L
I N
K N
K I
*/
Read More +
解題區►解題區 - UVa

UVa 12109 - Fairies' Defence

Problem

在三維空間中有 N 位仙女，突然間被攻擊者定住，而攻擊者可能在這三維方體中任何一點出現，出現時會攻擊最鄰近的仙女，請問每名仙女被攻擊的機率為何？

Sample Input

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

Sample Output

1
2
Case 1: 0.500 0.500
Case 2: 0.286 0.714

Solution

很明顯地是一個 3D Voronoi，但是要處理 3D Voronoi 還不太行，根據 DJWS 筆記中寫道，應該使用 O(N N log N) 的做法，窮舉一點與其他點之間拉出來的半平面交，計算半平面交的面積佔有多少。

但這一題是 3D 情況，也就是說半空間交，找到凸殼之後計算其體積，因此沒有單純的半平面交這麼簡單。

如何做到半空間交目前沒有想法，但是利用蒙地卡羅算機率還算可行，每一筆測資限制窮舉次數在 800 萬內即可通過。

由於 N 很小，也想過窮舉一點之後，拉出半空間的所有情況，任三面交一點，若該點在半空間中都符合，則保留於後面處理。得到所有點集，拿來做三維凸包，之後計算體積。關於三維凸包 (凸殼) 計算體積，內部戳一點，對於所有面會形成錐體，把所有錐體體積加總即可。

也許 DJWS 的作法是正確的，但是目前不知道如何做到半空間交。不知道要怎麼繞行算法。

關於 2D 的題目，請參考 zerojudge b358. 竹馬不敵天降

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
double mrandom() {
	int r = rand();
	return (double) r / RAND_MAX;
}
int main() {
	int n, a, b, c;
	int cases = 0;
	int x[32], y[32], z[32];
	while (scanf("%d", &n) == 1 && n) {
		scanf("%d %d %d", &a, &b, &c);
		const int runtime = 8000000;
		for (int i = 0; i < n; i++)
			scanf("%d %d %d", &x[i], &y[i], &z[i]);
		int count[32] = {}, guess = runtime / n;
		double tx, ty, tz;
		for (int i = guess - 1; i >= 0; i--) {
			tx = mrandom() * a, ty = mrandom() * b, tz = mrandom() * c;
			double dist = 1e+60, tmp;
			int mn = 0;
			for (int j = 0; j < n; j++) {
				tmp = (tx - x[j]) * (tx - x[j]) + (ty - y[j]) * (ty - y[j]) + 
							(tz - z[j]) * (tz - z[j]);
				if (tmp < dist)
					dist = tmp, mn = j;
			}
			count[mn]++;
		}
		printf("Case %d:", ++cases);
		for (int i = 0; i < n; i++)
			printf(" %.3lf", (double) count[i] / guess);
		puts("");		
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11931 - Maze Escape

Problem

類似倉庫番遊戲，必須將箱子推到指定的按鈕位置，才會開啟逃離門，每一次可以走一步，如果箱子在旁邊，則人與箱子會同時往同一個方向移動。求逃離最少步數。

在還沒有打開門之前，門就相當於障礙物存在，不能經過。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0

Sample Output

1
2
No Way!
20

Solution

反例輸出有誤，把 No Way! 拆成兩行送出結果拿到 WA。

把人的位置和箱子位置記錄成一個狀態，得到 dist[sx][sy][bx][by] 進行 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
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
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int sx, sy, ex, ey, bx, by, cx, cy;
int n, m;
char g[32][32];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int dist[25][25][25][25];
int bfs() {
	memset(dist, 0, sizeof(dist));
	dist[sx][sy][bx][by] = 1;
	queue<int> X, Y, BX, BY;
	int x, y, tx, ty, ttx, tty;
	X.push(sx), Y.push(sy), BX.push(bx), BY.push(by);
	while (!X.empty()) {
		x = X.front(), X.pop();
		y = Y.front(), Y.pop();
		bx = BX.front(), BX.pop();
		by = BY.front(), BY.pop();
		int step = dist[x][y][bx][by];
		for (int i = 0; i < 4; i++) {
			tx = x + dx[i], ty = y + dy[i];
			if (tx < 0 || ty < 0 || tx >= n || ty >= m)
				continue;
			if (g[tx][ty] == 'd' && g[bx][by] == 'b')
				return step;
			if (g[tx][ty] == '#' || g[tx][ty] == 'd')
				continue;
			if (tx == bx && ty == by) { // push it
				ttx = tx + dx[i], tty = ty + dy[i];
				if (ttx < 0 || tty < 0 || ttx >= n || tty >= m)
					continue;
				if (g[ttx][tty] == '#' || g[ttx][tty] == 'd')
					continue;
				if (dist[tx][ty][ttx][tty] == 0) {
					dist[tx][ty][ttx][tty] = step + 1;
					X.push(tx), Y.push(ty), BX.push(ttx), BY.push(tty);
				}
			} else {
				if (dist[tx][ty][bx][by] == 0) {
					dist[tx][ty][bx][by] = step + 1;
					X.push(tx), Y.push(ty), BX.push(bx), BY.push(by);
				}
			}
		}
	}
	return -1;
}
int main() {
	while (scanf("%d %d", &n, &m) == 2 && n) {
		for (int i = 0; i < n; i++)
			scanf("%s", g[i]);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (g[i][j] == '@')
					sx = i, sy = j;
				if (g[i][j] == 'd')
					ex = i, ey = j;
				if (g[i][j] == 'x')
					bx = i, by = j;
				if (g[i][j] == 'b')
					cx = i, cy = j;
			}
		}
		int ret = bfs();
		if (ret < 0)	
			puts("No Way!");
		else
			printf("%d\n", ret);
	}
	return 0;
}
/*
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0
*/
Read More +