UVa 10185 - Phylogenetic Trees Inherited

Problem

給 n 個化合物,每個化合物長度 m。其中 n 為 2 的冪次。

建造一個分類的關係樹,每一個節點上會有分類依據長度依舊為 m,而每一個化合物按照輸入順序成為完滿樹的葉節點。

目標這個樹的花費越少越好,樹花費的計算為相鄰兩個節點之間的漢明碼距離總和。也就是與子節點所表示的字串之間有多少不同的字符。

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
31
32
33
34
35
36
4 3
AAG
AAA
GGA
AGA
4 3
AAG
AGA
AAA
GGA
4 3
AAG
GGA
AAA
AGA
4 1
A
R
A
R
2 1
W
W
2 1
W
Y
1 1
Q
0 0

Sample Output

1
2
3
4
5
6
7
AGA 3
AGA 4
AGA 4
R 2
W 0
Y 1
Q 0

Solution

事實上,我們可以分開考慮 m 位的結果,彼此之間的花費最小化即可。

當只考慮要填什麼的時候,如果兩個子樹填法有所交集,則表示選擇其中一個,與其子節點都不需要花費,如果是空集,則必然選擇其中一個子樹結果來補足,花費多 1。

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
#include <stdio.h>
char acid[1024][1024], ret[2048];
int main() {
int n, m;
while (scanf("%d %d", &n, &m) == 2 && n) {
for (int i = 0; i < n; i++)
scanf("%s", acid[i]);
ret[m] = '\0';
int diff = 0, N = 2 * n;
for (int i = 0; i < m; i++) {
int dp[2048] = {};
for (int j = n; j < N; j++)
dp[j] = 1<<(acid[j - n][i] - 'A');
for (int j = n-1; j > 0; j--) {
dp[j] = dp[j<<1]&dp[j<<1|1];
if (dp[j] == 0) { // choose one branch, cost 1
diff++;
dp[j] = dp[j<<1]|dp[j<<1|1];
}
}
for (int j = 0; j < 26; j++) {
if ((dp[1]>>j)&1) {
ret[i] = j + 'A';
break;
}
}
}
printf("%s %d\n", ret, diff);
}
return 0;
}
Read More +

UVa 10184 - Equidistance

Problem

在地球上,給定許多地點的經緯度,兩個人必須在中立領域中見面,兩個人分別在球面上的兩個點,中立領域則是兩點連線的中點,垂直拉出的一個大圓 (球體上的一圈)。

它們現在位於地球上某點,請問到大圓的最短距離為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Ulm 48.700 10.500
Freiburg 47.700 9.500
Philadelphia 39.883 -75.250
SanJose 37.366 -121.933
Atlanta 33 -84
Eindhoven 52 6
Orlando 28 -82
Vancouver 49 -123
Honolulu 22 -157
NorthPole 90 0
SouthPole -90 0
#
Ulm Freiburg Philadelphia
SanJose Atlanta Eindhoven
Orlando Vancouver Honolulu
NorthPole SouthPole NorthPole
Ulm SanDiego Orlando
NorthPole SouthPole SouthPole
Ulm Honolulu SouthPole
#

Sample Output

1
2
3
4
5
6
7
Philadelphia is 690 km off Ulm/Freiburg equidistance.
Eindhoven is 3117 km off SanJose/Atlanta equidistance.
Honolulu is 4251 km off Orlando/Vancouver equidistance.
NorthPole is 10019 km off NorthPole/SouthPole equidistance.
Orlando is ? km off Ulm/SanDiego equidistance.
SouthPole is 10019 km off NorthPole/SouthPole equidistance.
SouthPole is 1494 km off Ulm/Honolulu equidistance.

Solution

特別小心,詢問的兩點相同,導致整個球體都是中立領域。

對於球體找到圓的最短距離,找出夾角即可。

首先拉出 AB 線,將其移動至眼前水平放置 (O A B 同一水平面),又 OM 會於 AB 中點拉出來的大圓夾角 theta (直接 AB 和 OM 內積得角度),此時的大圓應該是垂直 90 度,藉此得到最短距離。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <map>
using namespace std;
struct Point {
double x, y, z;
Point(double a=0, double b=0, double c=0):
x(a), y(b), z(c) {}
Point operator-(const Point &a) const {
return Point(x - a.x, y - a.y, z - a.z);
}
double len() {
return sqrt(x * x + y * y + z * z);
}
};
int main() {
const double pi = acos(-1);
const double earth_r = 6378;
char s[1024], s2[1024], s3[1024];
double lat, lon; // latitude, longitude
map<string, Point> R;
while (scanf("%s", s) == 1) {
if (!strcmp(s, "#"))
break;
scanf("%lf %lf", &lat, &lon);
lat = lat * pi / 180.0;
lon = lon * pi / 180.0;
double x, y, z;
x = earth_r * cos(lat) * cos(lon);
y = earth_r * cos(lat) * sin(lon);
z = earth_r * sin(lat);
R[s] = Point(x, y, z);
}
while (scanf("%s", s) == 1) {
if (!strcmp(s, "#"))
break;
scanf("%s %s", s2, s3);
if (R.find(s) == R.end() || R.find(s2) == R.end() || R.find(s3) == R.end()) {
printf("%s is ? km off %s/%s equidistance.\n", s3, s, s2);
} else {
Point A = R[s], B = R[s2], M = R[s3];
Point AB = A - B, OM = M;
double dot = AB.x * OM.x + AB.y * OM.y + AB.z * OM.z;
double theta = acos(fabs(dot) / AB.len() / OM.len());
double ret = (pi /2 - theta) * earth_r;
#define eps 1e-6
if (fabs(AB.x) < eps && fabs(AB.y) < eps && fabs(AB.z) < eps)
ret = 0;
printf("%s is %.0lf km off %s/%s equidistance.\n", s3, ret, s, s2);
}
}
return 0;
}
Read More +

UVa 1031 - Insecure in Prague

Problem

給一段密文,輸出最長的明文,如果最長明文有多個,則輸出 Codeword not unique

加密的工序為

  • 決定四個參數 s, t, i, j
  • 類似殺人遊戲般,一開始有 m 個空位,初始位置於 s 開始數,每 i 個空位就填入明文的下一個字符。
  • 然後重複動作填入第二次明文,但是起始位置 t,每 j 個空位填入。
  • 剩餘位置隨機填入字符。

Sample Input

1
2
3
4
APPURAAURGEGEWE
ABABABAB
THEACMPROGRAMMINGCONTEST
X

Sample Output

1
2
3
Code 1: PRAGUE
Code 2: Codeword not unique
Code 3: Codeword not unique

Solution

題目中有一段

Starting with the first empty slot in or after position t in string …

看起來 t 一點也不重要。也就是不用特定對 t 窮舉參數,將每個可以填入的位置都嘗試過當初始位置。

窮舉的順序,窮舉 s, n, i 可以在第一次填入工序中,得到明文結果。然後在第二步處理中,檢查是否明文填入時時候對應到原本的密文。

在窮舉前,可以事先計算殺人遊戲的殺戮順序,好在窮舉時得到明文結果。在第二步窮舉時,由於已經將部分明文填入好,剩餘的空格少了快一半,必須將其壓縮再一起,重新使用殺人遊戲的填入方式。

這一題很卡常數,很優化就優化,寫到眼神崩盤。

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
#include <stdio.h>
#include <string.h>
#include <set>
#include <iostream>
#include <vector>
using namespace std;
vector<int> putOrder[51][51]; // [m][i]
int main() {
for (int m = 2; m < 50; m++) {
for (int i = 0; i < m; i++) {
int visited[50] = {}, pos = 0, skip = 0;
putOrder[m][i].push_back(pos), visited[pos] = 1;
for (int p = 1; p < m; p++) {
skip = i % (m - p);
while (skip >= 0) {
pos++;
if (pos >= m) pos = 0;
if (!visited[pos])
skip--;
}
visited[pos] = 1;
putOrder[m][i].push_back(pos);
}
}
}
// for (int i = 0; i < putOrder[15][6].size(); i++) // example
// printf("%d\n", (putOrder[15][6][i] + 1)%15);
char text[64];
int cases = 0;
while (gets(text)) {
if (!strcmp("X", text)) break;
int m = strlen(text);
int appear[128] = {};
for (int i = 0; text[i]; i++)
appear[text[i]]++;
int mxlen = 1, remainUsed[64];
set<string> ret[64];
for (int s = m-1; s >= 0; s--) {
if (appear[text[s]] < 2) // must not start alphabet
continue;
for (int n = m/2; n >= mxlen; n--) {
if (ret[n].size() > 1) continue;
char plain[128];
for (int i = 0; i < m; i++) {
if (ret[n].size() > 1) continue;
int cnt[128] = {}, used[64] = {};
int ok = 1;
for (int p = 0; p < putOrder[m][i].size() && p < n; p++)
plain[p] = text[(putOrder[m][i][p] + s)%m], used[(putOrder[m][i][p] + s)%m] = 1;
plain[n] = '\0';
for (int p = 0; p < n; p++) {
cnt[plain[p]]++;
if (cnt[plain[p]] * 2 > appear[plain[p]])
ok = 0;
}
if (!ok) continue;
if (ret[n].find(plain) != ret[n].end())
continue;
int mm = 0;
for (int p = 0; p < m; p++) {
if (!used[p])
remainUsed[mm++] = p;
}
for (int t = 0; t < mm; t++) {
if (plain[0] != text[remainUsed[t]])
continue;
if (ret[n].size() > 1) continue;
for (int j = i + 1; j < m; j++) {
if (ret[n].size() > 1) continue;
int visited[50] = {};
int pos = t, skip = 0, ok2 = 1;
visited[pos] = 1;
for (int p = 1; p < n; p++) {
skip = j % (mm - p);
while (skip >= 0) {
pos++;
if (pos >= mm) pos = 0;
if (!visited[pos])
skip--;
}
if (plain[p] != text[remainUsed[pos]]) {
ok2 = 0;
break;
}
visited[pos] = 1;
}
if (ok2) {
if (n > mxlen)
mxlen = n;
ret[n].insert(plain);
}
}
}
}
}
}
printf("Code %d: ", ++cases);
for (int i = m/2; i >= 0; i--) {
if (ret[i].size()) {
if (ret[i].size() == 1)
printf("%s\n", ret[i].begin()->c_str());
else
puts("Codeword not unique");
break;
}
}
}
return 0;
}
/*
APPURAAURGEGEWE
ABABABAB
THEACMPROGRAMMINGCONTEST
X
*/
Read More +

UVa 1029 - Heliport

Problem

逆時針順序給定一個正交多邊形,請問內接最大圓為何?

Sample Input

1
2
3
4
5
4
2 R 2 U 2 L 2 D
10
10 R 10 U 10 L 10 U 10 R 5 U 30 L 20 D 20 R 5 D
0

Sample Output

1
2
3
Case Number 1 radius is: 1.00
Case Number 2 radius is: 10.00

Solution

首先,這題不能模擬退火,至少我的技巧退火沒結果。

於是二分最大圓半徑,接著窮舉所有可能匹配的圓,針對圓檢查是否包含於正交多邊形內部。

決定半徑之後,圓心存在於幾種可能

  • 通過圓上的兩點,可以決定兩個圓心。
  • 兩條線相切於圓,可以決定四個圓心。
  • 交一點、切一線,可以決定兩個圓心。

首先必須檢測圓心是否在正交多邊形中,用了射線法莫名其妙 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
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define eps 1e-6
struct Pt {
double x, y;
Pt(double a = 0, double b = 0):
x(a), y(b) {}
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;
}
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);
}
void read() {
scanf("%lf %lf", &x, &y);
}
};
struct Seg {
Pt s, e;
Seg(Pt a = Pt(), Pt b = Pt()):
s(a), e(b) {}
};
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 cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
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);
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
cross(at, as, bs) * cross(at, as, bt) < 0 &&
cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
cross(bt, bs, as) * cross(bt, bs, at) < 0)
return 1;
return 0;
}
double distProjection(Pt as, Pt at, Pt s) {
int a, b, c;
a = at.y - as.y;
b = as.x - at.x;
c = - (a * as.x + b * as.y);
return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double ptToSeg(Seg seg, Pt p) {
double c = 1e+30;
if(between(seg.s, seg.e, p))
c = min(c, distProjection(seg.s, seg.e, p));
else
c = min(c, min(dist(seg.s, p), dist(seg.e, p)));
return c;
}
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(q, p[i], p[j]))
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;
}
// this problem
Pt D[1024];
int N;
int checkCircle(double x, double y, double r) {
int cnt = 0;
for (int i = 0; i < N; i++) {
if (D[i].x > x && (D[i].y > y != D[i+1].y > y))
cnt++;
}
if (cnt%2 == 0) return 0;
for (int i = 0; i < N; i++) {
if ((D[i].x - x) * (D[i].x - x) + (D[i].y - y) * (D[i].y - y) < (r - eps)* (r - eps))
return 0;
if (D[i].x == D[i + 1].x && (D[i].y > y != D[i+1].y > y) && fabs(D[i].x - x) < r - eps)
return 0;
if (D[i].y == D[i + 1].y && (D[i].x > x != D[i+1].x > x) && fabs(D[i].y - y) < r - eps)
return 0;
}
return 1;
}
int checkRadius(double r) {
for (int i = 0; i < N; i++) {
if (D[i].x == D[i+1].x)
for (int j = 0; j < N; j++) {
if (D[j].y == D[j+1].y) {
if (checkCircle(D[i].x + r, D[j].y + r, r))
return 1;
if (checkCircle(D[i].x + r, D[j].y - r, r))
return 1;
if (checkCircle(D[i].x - r, D[j].y + r, r))
return 1;
if (checkCircle(D[i].x - r, D[j].y - r, r))
return 1;
}
}
}
double d, dd, dx, dy, x, y;
for (int i = 0; i < N; i++) { // (line, point) => circle
for (int j = 0; j < N; j++) {
if (D[i].x == D[i+1].x) {
d = fabs(D[j].x - (D[i].x + r));
if (d < r) {
dy = sqrt(r*r - d*d);
if (checkCircle(D[i].x + r, D[j].y + dy, r))
return 1;
if (checkCircle(D[i].x + r, D[j].y - dy, r))
return 1;
}
d = fabs(D[j].x - (D[i].x - r));
if (d < r) {
dy = sqrt(r*r - d*d);
if (checkCircle(D[i].x - r, D[j].y + dy, r))
return 1;
if (checkCircle(D[i].x - r, D[j].y - dy, r))
return 1;
}
} else {
d = fabs(D[j].y - (D[i].y + r));
if (d < r) {
dx = sqrt(r*r - d*d);
if (checkCircle(D[j].x + dx, D[i].y + r, r))
return 1;
if (checkCircle(D[j].x - dx, D[i].y + r, r))
return 1;
}
d = fabs(D[j].y - (D[i].y - r));
if (d < r) {
dx = sqrt(r*r - d*d);
if (checkCircle(D[j].x + dx, D[i].y - r, r))
return 1;
if (checkCircle(D[j].x - dx, D[i].y - r, r))
return 1;
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
x = (D[i].x + D[j].x)/2;
y = (D[i].y + D[j].y)/2;
d = hypot(x - D[i].x, y - D[i].y);
if (d < r) {
dd = sqrt(r*r - d*d);
dx = (y - D[i].y)/d * dd;
dy = (D[i].x - x)/d * dd;
if (checkCircle(x + dx, y + dy, r))
return 1;
if (checkCircle(x - dx, y - dy, r))
return 1;
}
}
}
return 0;
}
int main() {
int n, x, cases = 0;
char cmd[1024];
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int R[128];
R['R'] = 0, R['U'] = 1, R['L'] = 2, R['D'] = 3;
while(scanf("%d", &n) == 1 && n) {
D[0] = Pt(0, 0), N = n;
for (int i = 1; i <= n; i++) {
scanf("%d %s", &x, cmd);
D[i].x = D[i-1].x + x * dx[R[cmd[0]]];
D[i].y = D[i-1].y + x * dy[R[cmd[0]]];
}
double l = 0, r = 1000, ret, mid;
while (fabs(l - r) > eps) {
mid = (l + r)/2;
if (checkRadius(mid))
l = mid, ret = mid;
else
r = mid;
}
if (cases) puts("");
printf("Case Number %d radius is: %.2lf\n", ++cases, ret);
}
return 0;
}
/*
4
2 R 2 U 2 L 2 D
10
10 R 10 U 10 L 10 U 10 R 5 U 30 L 20 D 20 R 5 D
12
1 R 1 U 1 R 1 U 1 L 1 U
1 L 1 D 1 L 1 D 1 R 1 D
*/
Read More +

UVa 1008 - A Vexing Problem

Problem

給予一個 Vexed! 遊戲,這遊戲類似於消球遊戲,可以左右拖動特定元素使其掉落,在一個瞬間中可以讓相鄰兩個相同元素同時消失。在下一個瞬間,仍在盤面上的元素會根據重力往下墜落,如果又發現存有相同元素相鄰,則會不斷地迭代消去。

請問如何在最少步數下把所有元素消去。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4 5 SAMPLE-01
#A--#
##-B#
#AB##
#####
6 7 SAMPLE-02
#--Y--#
#-ZX-X#
#-##-##
#-XZ--#
####YZ#
#######
0 0 END

Sample Output

1
2
3
4
5
6
SAMPLE-01: Minimum solution length = 2
(B,1,3,L) (A,0,1,R)
SAMPLE-02: Minimum solution length = 9
(Y,0,3,R) (Z,4,5,L) (X,1,3,R) (Z,1,2,R)
(Z,1,3,R) (X,3,4,R) (X,3,2,R) (X,4,5,L)
(X,1,5,L)

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
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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define hash_mod 1000003
int n, m, visited[16][16], cases = 0;
struct State {
char g[10][10];
int label;
bool operator<(const State &x) const {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] != x.g[i][j])
return g[i][j] < x.g[i][j];
return false;
}
unsigned int hash() {
unsigned int a = 63689, b = 378551;
unsigned int value = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
value = value * a + g[i][j];
a *= b;
}
}
return value % hash_mod;
}
int dfs(int x, int y, char c) {
if (x < 0 || y < 0 || x >= n || y >= m)
return 0;
if (g[x][y] != c || visited[x][y] == cases)
return 0;
visited[x][y] = cases;
int ret = 0;
ret += dfs(x+1, y, c);
ret += dfs(x, y+1, c);
ret += dfs(x-1, y, c);
ret += dfs(x, y-1, c);
return 1 + ret;
}
void erase(int x, int y, int c) {
if (x < 0 || y < 0 || x >= n || y >= m)
return ;
if (g[x][y] != c || visited[x][y] != cases)
return ;
g[x][y] = '-';
erase(x+1, y, c);
erase(x, y+1, c);
erase(x-1, y, c);
erase(x, y-1, c);
}
void fall() {
for (int i = n-1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (g[i][j] >= 'A' && g[i][j] <= 'Z') {
int k = i+1;
while (k < n && g[k][j] == '-') {
g[k][j] = g[k-1][j];
g[k-1][j] = '-';
k++;
}
}
}
}
}
void refresh() {
int update = 0, cnt;
do {
fall();
update = 0;
memset(visited, 0, sizeof(visited));
cases = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == 0 && g[i][j] >= 'A' && g[i][j] <= 'Z') {
cases++;
cnt = dfs(i, j, g[i][j]);
if (cnt > 1)
erase(i, j, g[i][j]), update = 1;
}
}
}
} while (update);
}
int isCompleted() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
if (g[i][j] >= 'A' && g[i][j] <= 'Z')
return 0;
}
return 1;
}
};
struct Info {
int x, y, dir, prev;
char c;
Info(int s1 = 0, int s2 = 0, int s3 = 0, int s4 = 0, char s = 0):
x(s1), y(s2), dir(s3), prev(s4), c(s) {
}
};
map<State, int> R[hash_mod];
vector<Info> history;
int main() {
char casesName[105];
State st, next;
int h, step;
while (scanf("%d %d %s", &n, &m, casesName) == 3 && n) {
for (int i = 0; i < n; i++)
scanf("%s", &st.g[i]);
history.resize(1);
for (int i = 0; i < hash_mod; i++)
R[i].clear();
int labelCnt = 0, label;
queue<State> Q;
st.refresh(), st.label = 0;
h = st.hash();
R[h][st] = 0, Q.push(st);
while (!Q.empty()) {
st = Q.front(), Q.pop();
h = st.hash(), label = st.label;
step = R[h][st];
if (st.isCompleted())
break;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (st.g[i][j] >= 'A' && st.g[i][j] <= 'Z') {
if (j+1 < m && st.g[i][j+1] == '-') {
next = st;
swap(next.g[i][j], next.g[i][j+1]);
next.refresh();
h = next.hash();
if (R[h].find(next) == R[h].end()) {
next.label = ++labelCnt;
history.push_back(Info(i, j, 1, label, st.g[i][j]));
R[h][next] = step + 1;
Q.push(next);
}
}
if (j-1 >= 0 && st.g[i][j-1] == '-') {
next = st;
swap(next.g[i][j], next.g[i][j-1]);
next.refresh();
h = next.hash();
if (R[h].find(next) == R[h].end()) {
next.label = ++labelCnt;
history.push_back(Info(i, j, 0, label, st.g[i][j]));
R[h][next] = step + 1;
Q.push(next);
}
}
}
}
}
}
printf("%s: Minimum solution length = %d\n", casesName, step);
int idx = st.label;
vector<Info> ret;
while (idx) {
ret.push_back(history[idx]);
idx = history[idx].prev;
}
for (int i = ret.size() - 1, j = 0; i >= 0; i--, j++) {
if (j%4) putchar(' ');
printf("(%c,%d,%d,%c)", ret[i].c, ret[i].x, ret[i].y, ret[i].dir ? 'R' : 'L');
if (j%4 == 3) puts("");
}
if (ret.size()%4) puts("");
}
return 0;
}
Read More +

UVa 11985 - Prime Independence

Problem

給 N 個數字,找到最大子集滿足任 A, B 數字,A 不為 B 的質數倍。

Sample Input

1
2
3
4
5
6
7
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3

Sample Output

1
2
3
Case 1: 3
Case 2: 3
Case 3: 2

Solution

看起來就是一個二分圖找最大獨立集,但是建造的速度要夠快,少說也要 500 ms,然後在二分匹配上必須採用很快速的最大流,這裡採用 dinic 版本,網路上搜索到這個版本挺不錯的。

為了遇見妳,已經撒了無數 TLE。
求到妳接受的那個瞬間,神啊!謝謝祢的禮物才讓我們相遇。

對於最大流算法,一般而言會經過不斷地溯洄沖減, Dinic 分層圖的方式進行計算,但是可以利用指針對於每個節點進行記錄,在沖減時,對指針結果的下一條邊進行計算,而不對於每一個點的所有邊重頭來過。

接著,分層圖可以利用沖減時,進行計算,即當找到瓶頸時,更新該點的層次。取代一般重新使用 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
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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
int v, cap, flow;
Edge *next, *re;
} Edge;
class MaxFlow {
public:
Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
void Init(int x) {
n = x, e = 0;
for (int i = 0; i < n; ++i) adj[i] = NULL;
}
void Addedge(int x, int y, int flow){
edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
edge[e].re = &edge[e+1], adj[x] = &edge[e++];
edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
edge[e].re = &edge[e-1], adj[y] = &edge[e++];
}
void Bfs(int v){
int front = 0, rear = 0, r = 0, dis = 0;
for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
level[v] = 0, ++lvCnt[0];
Q[rear++] = v;
while (front != rear){
if (front == r) ++dis, r = rear;
v = Q[front++];
for (Edge *i = adj[v]; i != NULL; i = i->next) {
int t = i->v;
if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
}
}
}
int Maxflow(int s, int t){
int ret = 0, i, j;
Bfs(t);
for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
i = s;
while (level[s] < n){
while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow))
arc[i] = arc[i]->next;
if (arc[i]){
j = arc[i]->v;
pre[j] = arc[i];
i = j;
if (i == t){
int update = INF;
for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
if (update > p->flow) update = p->flow;
ret += update;
for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
p->flow -= update, p->re->flow += update;
i = s;
}
}
else{
int depth = n-1;
for (Edge *p = adj[i]; p != NULL; p = p->next)
if (p->flow && depth > level[p->v]) depth = level[p->v];
if (--lvCnt[level[i]] == 0) return ret;
level[i] = depth+1;
++lvCnt[level[i]];
arc[i] = adj[i];
if (i != s) i = pre[i]->re->v;
}
}
return ret;
}
} g;
#define MAXL (500000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
int P[100000], Pt = 0;
vector<int> pfactor[524288];
int A[MAXV], RE[524288], XY[524288];
void sieve() {
register int i, j, k;
SET(1);
int n = 500000;
for(i = 2; i <= n; i++) {
if(!GET(i)) {
XY[i] = 1;
// for(k = n/i, j = i*k; k >= i; k--, j -= i)
// SET(j);
for (j = i+i; j <= n; j += i)
SET(j), XY[j] = XY[j/i] + 1, pfactor[j].push_back(i);
pfactor[i].push_back(i);
P[Pt++] = i;
}
}
}
int main() {
sieve();
int testcase, cases = 0;
int n, x;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
memset(RE, -1, sizeof(RE));
for (int i = 0; i < n; i++) {
scanf("%d", &A[i]);
RE[A[i]] = i;
}
g.Init(n + 2);
int source = n, sink = n + 1;
for (int i = 0; i < n; i++) {
if (XY[A[i]]&1)
g.Addedge(source, i, 1);
else
g.Addedge(i, sink, 1);
for (int j = 0; j < pfactor[A[i]].size(); j++) {
int y = A[i] / pfactor[A[i]][j];
if (RE[y] != -1) {
if (XY[y]&1)
g.Addedge(RE[y], i, 1);
else
g.Addedge(i, RE[y], 1);
}
}
}
printf("Case %d: %d\n", ++cases, n - g.Maxflow(source, sink));
}
return 0;
}
/*
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3
1000
3
7 35 105
*/
Read More +

UVa 11759 - IBM Fencing

Problem

給定 N 個凸包,保證凸包之間不會有交點,而依據分層,奇數層使用金屬圍欄,偶數層使用木製圍欄,請問分別為需要多少材料。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
8
8 112 134 73 141 41 119 32 82 54 50 92 43 124 65 132 103
6 119 119 102 119 94 101 102 83 119 83 127 101
8 83 106 62 111 45 99 42 78 54 59 75 55 92 66 96 87
6 70 97 56 97 49 85 56 73 70 73 77 85
8 143 222 110 244 61 238 35 209 39 169 72 147 121 153 147 181
4 115 226 58 226 51 167 132 167
4 113 212 65 212 65 172 113 172
5 99 205 83 206 71 187 91 179 105 189
2
4 0 0 100 0 100 100 0 100
4 1000 1000 1100 1000 1100 1100 1000 1100
0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
Case 1:
Total Number of Communities 2
Total Cost:
Steel Fence: 0.09047417 Million Yuan
Wooden Fence: 0.03190241 Million Yuan
Case 2:
Total Number of Communities 2
Total Cost:
Steel Fence: 0.08000000 Million Yuan
Wooden Fence: 0.00000000 Million Yuan

Solution

這裡需要對 N 個凸包做相互關係判斷,建造出 tree 圖,根據樹圖計算分層。

兩個凸包判定可以在 O(log n) 時間內完成,因此建造會在 O(n^2 log n)

找到多邊形分層圖之間的關係,只會有完全包裹和完全沒交集兩種情況。利用掃描線可以找到兩個相鄰多邊形,要不與其同一層,要不就是上一層。因此可以在 n log n 時間內找到,考慮邊的個數問題,複雜度上提 O(nm log nm) 不如暴力窮舉兩個多邊形做判定 O(n^2 m),在都是凸多邊形的情況 O(n^2 log m)。掃描線掃了一連串結果,還要處理同一多邊形端點相同的線段,利用隨機擾動處理垂直線 … 等,自找苦吃,暴力完勝。

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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
double x, y;
int label;
Pt(double a = 0, double b = 0, int c = 0):
x(a), y(b), label(c) {}
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;
}
Pt operator-(const Pt &a) const {
return Pt(x - a.x, y - a.y);
}
};
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 cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
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);
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
cross(at, as, bs) * cross(at, as, bt) < 0 &&
cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
cross(bt, bs, as) * cross(bt, bs, at) < 0)
return 1;
return 0;
}
// this problem
vector<int> g[512];
struct Polygon { // convex
vector<Pt> p;
int contain(Polygon &a) {
int n = p.size();
if(n < 3) return false;
Pt q = a.p[0];
if(cross(p[0], q, p[1]) > eps) return 0;
if(cross(p[0], q, p[n-1]) < -eps) return 0;
int l = 2, r = n - 1;
int line = -1;
while(l <= r) {
int mid = (l + r)>>1;
if(cross(p[0], q, p[mid]) > -eps) {
line = mid;
r = mid - 1;
} else l = mid + 1;
}
return cross(p[line-1], q, p[line]) < eps;
}
};
Polygon poly[512];
int parent[32767], visited[32767], depth[32767];
void bfs(int u) {
int v;
queue<int> Q;
Q.push(u);
visited[u] = 1, depth[u] = 1;
while (!Q.empty()) {
u = Q.front(), Q.pop();
for (int i = 0; i < g[u].size(); i++) {
v = g[u][i];
if (depth[v] < depth[u] + 1) {
depth[v] = depth[u] + 1;
visited[v] = 1, parent[v] = u;
Q.push(v);
}
}
}
}
int main() {
int N, M, cases = 0;
while(scanf("%d", &N) == 1 && N) {
for(int i = 0; i < N; i++) {
scanf("%d", &M);
poly[i].p.resize(M);
for (int j = 0; j < M; j++)
scanf("%lf %lf", &poly[i].p[j].x, &poly[i].p[j].y);
double mnx = poly[i].p[0].x;
int idx = 0;
for (int j = 0; j < M; j++) {
if (poly[i].p[j].x < mnx)
mnx = poly[i].p[j].x, idx = j;
}
if (cross(poly[i].p[idx], poly[i].p[(idx+1)%M], poly[i].p[(idx-1+M)%M]) < eps)
reverse(poly[i].p.begin(), poly[i].p.end());
}
for (int i = 0; i < N; i++)
g[i].clear();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) continue;
if (poly[i].contain(poly[j]))
g[i].push_back(j);
}
}
for (int i = 0; i < N; i++) {
visited[i] = 0, parent[i] = -1, depth[i] = 0;
}
for (int i = 0; i < N; i++) {
if (visited[i] == 0)
bfs(i);
}
int communities = 0;
double Acost = 0, Bcost = 0;
for (int i = 0; i < N; i++) {
if (parent[i] == -1)
communities++;
double tmp = 0;
for (int j = 0, k = poly[i].p.size() - 1; j < poly[i].p.size(); k = j++)
tmp += dist(poly[i].p[j], poly[i].p[k]);
if (depth[i]&1)
Acost += tmp;
else
Bcost += tmp/2;
}
printf("Case %d:\n", ++cases);
printf("Total Number of Communities %d\n", communities);
printf("Total Cost:\n");
printf("Steel Fence: %.8lf Million Yuan\n", Acost / 10000.0);
printf("Wooden Fence: %.8lf Million Yuan\n", Bcost / 10000.0);
puts("");
}
return 0;
}
/*
8
8 112 134 73 141 41 119 32 82 54 50 92 43 124 65 132 103
6 119 119 102 119 94 101 102 83 119 83 127 101
8 83 106 62 111 45 99 42 78 54 59 75 55 92 66 96 87
6 70 97 56 97 49 85 56 73 70 73 77 85
8 143 222 110 244 61 238 35 209 39 169 72 147 121 153 147 181
4 115 226 58 226 51 167 132 167
4 113 212 65 212 65 172 113 172
5 99 205 83 206 71 187 91 179 105 189
2
4 0 0 100 0 100 100 0 100
4 1000 1000 1100 1000 1100 1100 1000 1100
0
*/
Read More +

UVa 1006 - Fixed Partition Memory Management

Problem

每個程式會有在不同的空間限制下會有不同的運行時間,現在給定 N 個內存池,M 個程式,每個程式只能在一個內存池下運行,並且同一個時間內存池內最多有一個程式。

最平均運行時間最少為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 4
40 60
1 35 4
1 20 3
1 40 10
1 60 7
3 5
10 20 30
2 10 50 12 30
2 10 100 20 25
1 25 19
1 19 41
2 10 18 30 42
0 0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Case 1
Average turnaround time = 7.75
Program 1 runs in region 1 from 0 to 4
Program 2 runs in region 2 from 0 to 3
Program 3 runs in region 1 from 4 to 14
Program 4 runs in region 2 from 3 to 10
Case 2
Average turnaround time = 35.40
Program 1 runs in region 2 from 25 to 55
Program 2 runs in region 2 from 0 to 25
Program 3 runs in region 3 from 0 to 19
Program 4 runs in region 3 from 19 to 60
Program 5 runs in region 1 from 0 to 18

Solution

平均最少時間的計算,就是拿每個程式的運行結束時間加總取平均。

但是必須累計到前一個在內存池運行的程式時間,這一點必須轉換成最少費用流模型。

事實上,換個角度想,假使排定程式 A 運行,而後會有 B, C 程式,那麼 A 的運行時間會累計到三次,而 B 會被累計到兩次。也就是說,內存池每一個程式的時間加總會分配到 1 ~ N 個程式重複計數。

因此模型為 source - program - [memory_pool, count] - sink

輸出的時候,在內存池被累計越多次的程式應該越早執行。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
struct Node {
int x, y, cap, cost;// x->y, v
int next;
} edge[1000005];
int e, head[600], dis[600], prev[600], record[600], inq[600];
void addEdge(int x, int y, int cap, int cost) {
edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
edge[e].next = head[x], head[x] = e++;
edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
edge[e].next = head[y], head[y] = e++;
}
int mincost(int s, int t) {
int mncost = 0, flow, totflow = 0;
int i, x, y;
while(1) {
memset(dis, 63, sizeof(dis));
int oo = dis[0];
dis[s] = 0;
deque<int> Q;
Q.push_front(s);
while(!Q.empty()) {
x = Q.front(), Q.pop_front();
inq[x] = 0;
for(i = head[x]; i != -1; i = edge[i].next) {
y = edge[i].y;
if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
dis[y] = dis[x] + edge[i].cost;
prev[y] = x, record[y] = i;
if(inq[y] == 0) {
inq[y] = 1;
if(Q.size() && dis[Q.front()] > dis[y])
Q.push_front(y);
else
Q.push_back(y);
}
}
}
}
if(dis[t] == oo)
break;
flow = oo;
for(x = t; x != s; x = prev[x]) {
int ri = record[x];
flow = min(flow, edge[ri].cap);
}
for(x = t; x != s; x = prev[x]) {
int ri = record[x];
edge[ri].cap -= flow;
edge[ri^1].cap += flow;
edge[ri^1].cost = -edge[ri].cost;
}
totflow += flow;
mncost += dis[t] * flow;
}
return mncost;
}
int main() {
int n, m, cases = 0;
int x, y, d, a;
int mem[128], needmem[128][128], runtime[128][128], ch[128];
while(scanf("%d %d", &n, &m) == 2 && n+m) {
for (int i = 0; i < n; i++)
scanf("%d", &mem[i]);
for (int i = 0; i < m; i++) {
scanf("%d", &ch[i]);
for (int j = 0; j < ch[i]; j++)
scanf("%d %d", &needmem[i][j], &runtime[i][j]);
needmem[i][ch[i]] = 0x3f3f3f3f;
}
e = 0;
memset(head, -1, sizeof(head));
int source = n*m + m + 1, sink = n*m + m + 2;
for (int i = 0; i < m; i++) {
addEdge(source, i, 1, 0);
for (int j = 0; j < ch[i]; j++) {
for (int k = 0; k < n; k++) {
if (needmem[i][j] <= mem[k] && mem[k] <= needmem[i][j+1]) {
for (int p = 0; p < m; p++)
addEdge(i, m + k * m + p, 1, runtime[i][j] * (p + 1));
}
}
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
addEdge(m + i * m + j, sink, 1, 0);
double cost = mincost(source, sink);
int prog[128], from[128] = {}, run[128];
vector< pair<int, int> > runtable[128];
for (int i = 0; i < m; i++) {
for (int j = head[i]; j != -1; j = edge[j].next) {
if (edge[j].cap == 0 && edge[j].y >= m && edge[j].y < m + n*m) {
prog[i] = (edge[j].y - m) / m;
run[i] = edge[j].cost / ((edge[j].y - m) % m + 1);
runtable[prog[i]].push_back(make_pair((edge[j].y - m) % m, i));
break;
}
}
}
for (int i = 0; i < n; i++) {
sort(runtable[i].begin(), runtable[i].end(), greater< pair<int, int> >());
for (int j = 1; j < runtable[i].size(); j++)
from[runtable[i][j].second] = from[runtable[i][j-1].second] + run[runtable[i][j-1].second];
}
printf("Case %d\n", ++cases);
printf("Average turnaround time = %.2lf\n", (double) cost / m);
for (int i = 0; i < m; i++) {
printf("Program %d runs in region %d from %d to %d\n", i+1, prog[i]+1, from[i], from[i] + run[i]);
}
puts("");
}
return 0;
}
/*
2 4
40 60
1 35 4
1 20 3
1 40 10
1 60 7
3 5
10 20 30
2 10 50 12 30
2 10 100 20 25
1 25 19
1 19 41
2 10 18 30 42
0 0
*/
Read More +

UVa 1001 - Say Cheese

Problem

在一個三維空間中的乳酪,知道乳酪常會有氣泡般的空洞,假設在空洞中任意位置之間移動不消耗時間,為了抵達目的地,可以啃食乳酪到另外一個空洞,啃食時間與距離 1 : 1 關係,請問最少時間為何。

Sample Input

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

Sample Output

1
2
Cheese 1: Travel time = 100 sec
Cheese 2: Travel time = 20 sec

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 <math.h>
#include <algorithm>
using namespace std;
int main() {
int n, x[128], y[128], z[128], r[128];
int cases = 0;
while (scanf("%d", &n) == 1 && n >= 0) {
for (int i = 0; i < n + 2; i++) {
if (i < n)
scanf("%d %d %d %d", &x[i], &y[i], &z[i], &r[i]);
else
scanf("%d %d %d", &x[i], &y[i], &z[i]), r[i] = 0;
}
n += 2;
double f[128][128];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) f[i][i] = 0;
else {
double dist = sqrt(pow(x[i]-x[j], 2) + pow(y[i]-y[j], 2) + pow(z[i] - z[j], 2));
if (dist <= r[i] + r[j])
f[i][j] = 0;
else
f[i][j] = dist - (r[i] + r[j]);
}
}
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
printf("Cheese %d: Travel time = %.0lf sec\n", ++cases, f[n-1][n-2] * 10);
}
return 0;
}
Read More +

UVa 1000 - Airport Configuration

Problem

機場有一個長形走廊,其中南側是搭機處,北側是下機處。

給予很多城市間旅客的數量,從城市 A 到城市 B 的旅客 X 人會在這個機場上進行轉換。

現在讀入機場的放置口設定 (順序),請問每一種設定所產生的負載為何?

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3
1 2 2 10 3 15
2 1 3 10
3 2 1 12 2 20
1
1 2 3
2 3 1
2
2 3 1
3 2 1
0
2
1 1 2 100
2 1 1 200
1
1 2
1 2
2
1 2
2 1
0
0

Sample Output

1
2
3
4
5
6
Configuration Load
2 119
1 122
Configuration Load
2 300
1 600

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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stdlib.h>
using namespace std;
int main() {
int n;
while (scanf("%d", &n) == 1 && n) {
int A[32][32] = {}, x, city_id, dest, k;
int north[32], south[32];
for (int i = 0; i < n; i++) {
scanf("%d %d", &city_id, &k);
for (int j = 0; j < k; j++) {
scanf("%d %d", &dest, &x);
A[city_id][dest] += x;
}
}
vector< pair<int, int> > ret;
for (; scanf("%d", &city_id) == 1 && city_id;) {
for (int i = 0; i < n; i++)
scanf("%d", &north[i]);
for (int i = 0; i < n; i++)
scanf("%d", &south[i]);
int load = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
load += A[north[i]][south[j]] * (abs(i - j) + 1);
ret.push_back(make_pair(load, city_id));
}
sort(ret.begin(), ret.end());
puts("Configuration Load");
for (int i = 0; i < ret.size(); i++) {
printf("%5d %d\n", ret[i].second, ret[i].first);
}
}
return 0;
}
Read More +