解題區/解題區 - UVa

UVa 12552 - The Moon of Valencia

Problem

給你一張平面圖, P 個點 M 條邊，每個點給你座標，以及到達該點，如果進去玩的話可以獲得的滿意度，也就是可以只經過該點，但不進去玩，進去一次要15分鐘，進去玩的話可以獲得滿意度，給你一開始的位置以及時間還有終點位置，需要在那個時間前到達，還有一個滿意度標準，要找一條路徑，進去中間某些點，使得這個方案的滿意度跟題目要求的滿意度誤差在 0.1 內。
從一個點到一個點走邊時，滿意度會下降，特別注意終點不能進去，同一個點不能重複經過。

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
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
MAP 19 40
0 0 0 UPV Universitat Politecnica de Valencia
5 5 0 SPV Contest hotel
0 1 35 B01 The Object
1.1 1 42 B02 Opera
0.6 1.7 33 B03 New York
1.3 2 55 B04 Blue Note
1.5 2.5 23 B05 The Popes
2.5 2 13 B06 Petrol
4 3.5 12 B07 King of Kings
1.1 4 14 B08 O Salati
1.2 4.5 13 B09 The Snails
2.5 3.5 34 B10 The Earth
1.5 1.5 55 B11 Cafe Coffee
3 4.5 31 B12 Vermouth house
4.5 2.5 45 B13 Jamon Session
1.3 3.6 24 B14 Let's go to eat
1.5 4 34 B15 I'm hungry
0.6 2.5 53 B16 The Gecko
3.5 2.5 43 B17 The Black Sheep
UPV B01
B01 B02
B01 B03
B01 B16
B02 B03
B02 B11
B16 B08
B16 B14
B16 B03
B03 B04
B03 B11
B04 B11
B04 B16
B04 B05
B05 B14
B08 B09
B08 B15
B08 B14
B11 B06
B14 B15
B05 B06
B05 B16
B05 B10
B15 B09
B15 B10
B09 B12
B06 B10
B06 B17
B10 B07
B10 B17
B10 B12
B10 B14
B12 B15
B12 B07
B12 SPV
B17 B07
B17 B13
B07 B13
B07 SPV
B13 SPV
ARRIVALS
23:00 UPV 03:00 SPV 9.0
23:00 UPV 03:00 SPV 8.0
23:00 UPV 03:00 SPV 7.0
23:00 UPV 03:00 SPV 6.0
23:00 UPV 03:00 SPV 5.0
23:00 UPV 03:00 SPV 4.0
23:00 UPV 03:00 SPV 3.0
23:00 UPV 03:00 SPV 2.0
23:00 UPV 03:00 SPV 1.0
23:00 UPV 03:00 SPV 0.0
23:00 UPV 03:00 SPV -1.0
23:00 UPV 03:00 SPV -2.0
23:00 UPV 03:00 SPV -30.0
23:00 UPV 03:00 SPV -40.0
23:00 B05 03:00 B10 40.0
23:00 B05 03:00 B10 30.0
23:00 B05 03:00 B10 20.0
23:00 B05 03:00 B10 10.0
23:00 B05 03:00 B10 0.0
23:00 B05 03:00 B10 -10.0
23:00 B05 03:00 B10 -20.0
23:00 B05 03:00 B10 -30.0
23:00 B05 03:00 B10 -40.0
MAP 2 1
0 0 0 UPV Universitat Politecnica de Valencia
10 10 0 SPV Hotel Silken Puerta de Valencia
UPV SPV
ARRIVALS
23:00 UPV 1:00 SPV 9.0
23:00 UPV 1:00 SPV 8.0

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
MAP 1
PATH FOUND: 9.002 UPV B01 B16 B04 !B11 B06 !B17 !B13 SPV
PATH FOUND: 7.929 UPV B01 B16 B14 B08 B09 !B12 SPV
PATH FOUND: 6.973 UPV B01 B16 B04 !B11 B06 !B10 !B07 SPV
PATH FOUND: 6.028 UPV B01 B16 B05 B10 !B17 !B07 SPV
PATH FOUND: 4.995 UPV B01 B16 B04 !B05 !B14 !B15 !B10 B07 SPV
PATH FOUND: 4.078 UPV B01 B16 B08 !B15 B12 B07 SPV
PATH FOUND: 3.028 UPV B01 B16 B05 !B10 B12 !B07 SPV
PATH FOUND: 1.929 UPV B01 B16 B14 !B15 B08 B09 !B12 SPV
PATH FOUND: 0.912 UPV B01 B16 B03 !B04 !B05 !B06 B17 !B13 !B07 SPV
PATH FOUND: 0.028 UPV B01 B16 B05 !B10 B17 !B13 !B07 SPV
PATH FOUND: -0.986 UPV B01 B16 B08 !B09 !B15 B12 SPV
PATH FOUND: -1.973 UPV B01 B16 B03 !B04 !B05 B10 !B17 !B07 SPV
PATH FOUND: -29.953 UPV B01 B03 !B16 B05 !B10 !B14 B15 !B12 SPV
PATH FOUND: -39.913 UPV B01 B03 !B16 B08 !B09 !B15 B12 !B07 SPV
PATH FOUND: 40.069 B05 B16 B14 !B08 B09 !B15 B10
PATH FOUND: 30.012 B05 B16 B08 !B15 B10
PATH FOUND: 19.979 !B05 B04 !B03 B02 !B01 B16 !B08 !B09 !B15 B10
PATH FOUND: 10.004 B05 B14 B08 !B15 !B09 B12 B10
PATH FOUND: 0.004 !B05 B14 B08 !B15 B09 B12 B10
PATH FOUND: -9.966 B05 !B14 !B15 B12 B10
PATH FOUND: -20.012 B05 !B06 !B17 B07 B12 B15 !B14 B10
PATH FOUND: -30.012 !B05 B06 !B17 B07 B12 B15 !B14 B10
PATH FOUND: -40.018 !B05 !B04 !B16 B14 !B15 B10
MAP 2
Impossible!
Impossible!

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
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
#include <stdio.h> 
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
double x[64], y[64], sat[64];
double g[64][64], dist[64][64];
char str_id[64][64];
char line[1024], sa[64], sb[64];
vector<int> vg[64];
struct State {
    unsigned long long used;
    int now;
    double sat, h, time;
    vector<int> path;
    bool operator<(const State &other) const {
        return h > other.h;
    }
};
int main() {
    int n, m, cases = 0;
    scanf("%*s");
    while (scanf("%d %d", &n, &m) == 2) {
        while (getchar() != '\n');
        map<string, int> R;
        for (int i = 0; i < n; i++) {
            gets(line);
            sscanf(line, "%lf %lf %lf %s", &x[i], &y[i], &sat[i], &str_id[i]);
            R[str_id[i]] = i;
            vg[i].clear();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                g[i][j] = dist[i][j] = 1e+30;
            g[i][i] = dist[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            scanf("%s %s", sa, sb);
            int u = R[sa], v = R[sb];
            g[u][v] = g[v][u] = hypot(x[u]-x[v], y[u]-y[v]);
            vg[u].push_back(v);
            vg[v].push_back(u);
            dist[u][v] = dist[v][u] = g[v][u];
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
        scanf("%*s");
        printf("MAP %d\n", ++cases);
        while (scanf("%s", line) == 1 && line[0] != 'M') {
            int h1, m1, h2, m2;
            double target_sat, time;
            sscanf(line, "%d:%d", &h1, &m1);
            scanf("%s %d:%d %s %lf", sa, &h2, &m2, sb, &target_sat);
            int from = R[sa], to = R[sb];
            if (h1 * 60 + m1 > h2 * 60 + m2)
                h2 += 24;
            time = h2 * 60 + m2 - (h1 * 60 + m1);
            priority_queue< State, vector<State> > pQ;
            State u, ret;
            u.path.resize(1);
            u.path[0] = -(from + 1);
            u.used = 1LL<<from, u.now = from, u.sat = 0, u.time = 0;
            u.h = fabs(target_sat - (u.sat - dist[u.now][to] * 15));
            pQ.push(u);
            u.path[0] = (from + 1);
            u.used = 1LL<<from, u.now = from, u.sat = sat[from], u.time = 15;
            u.h = fabs(target_sat - (u.sat - dist[u.now][to] * 15));
            pQ.push(u);
            int ok = 0;
            while (!pQ.empty() && !ok) {
                u = pQ.top(), pQ.pop();
//				printf("%lf %d %llu\n", u.h, u.now, u.used);
//				getchar();
                if (u.now == to && fabs(target_sat - u.sat) < 0.1) {
                    ret = u, ok = 1;
                    break;
                }
                for (int i = 0; i < vg[u.now].size(); i++) {
                    int next = vg[u.now][i];
                    if ((u.used>>next)&1)	continue;
                    if (u.time + dist[u.now][next] * 15 > time)
                        continue;
                    State v;
//					printf("%lf %lf\n", u.time, g[u.now][next] * 15);
                    if (next == to) {
                        v = u;
                        v.path.push_back(next + 1);
                        v.used |= (1LLU<<next), v.time += dist[u.now][next] * 15;
                        v.sat += -g[u.now][next] * 15, v.now = next;
                        v.h = fabs(target_sat - (v.sat - dist[v.now][to] * 15));
                        if (next == to && fabs(target_sat - v.sat) < 0.1) {
                            ret = v, ok = 1;
                            break;
                        }
                    } else if (u.time + dist[u.now][next] * 15 + dist[next][to] * 15 + 15 <= time) { // enter
                        v = u;
                        v.path.push_back((next + 1));
                        v.used |= (1LLU<<next), v.time += dist[u.now][next] * 15 + 15;
                        v.sat += sat[next] - g[u.now][next] * 15, v.now = next;
                        v.h = fabs(target_sat - (v.sat - dist[v.now][to] * 15));
                        pQ.push(v);
//						printf("enter %d %d\n", u.now, next);
                    }
                    if (next != to && u.time + dist[u.now][next] * 15 + dist[next][to] * 15 <= time) { // pass
                        v = u;
                        v.path.push_back(-(next + 1));
                        v.used |= (1LLU<<next), v.time += dist[u.now][next] * 15;
                        v.sat += -g[u.now][next] * 15, v.now = next;
                        v.h = fabs(target_sat - (v.sat - dist[v.now][to] * 15));
                        if (next == to && fabs(target_sat - v.sat) < 0.1) {
                            ret = v, ok = 1;
                            break;
                        }
                        pQ.push(v);
//						printf("pass %d %d\n", u.now, next);
                    }
                }
            }
            if (ret.path.size() == 0) {
                puts("Impossible!");
            } else {
                printf("PATH FOUND: %.3lf ", ret.sat);
                for (int i = 0; i < ret.path.size(); i++) {
                    if (ret.path[i] < 0)	putchar('!');
                    printf("%s%c", str_id[abs(ret.path[i])-1], i == ret.path.size() - 1 ? '\n' : ' ');
                }
            }
        }
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 12745 - Wishmaster

Problem

有 n 個地點，每個地點要不用高架橋、要不使用地下化道路兩種方式，每個民眾有兩個願望，分別希望哪裡以什麼方式建造，只要滿足每一個民眾的其中一種願望即可。

Sample Input

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

Sample Output

1
2
Case 1: No
Case 2: Yes

Solution

一道樸素的 2-SAT 問題。

建圖，利用 SCC 將點縮起來，形成 DAG 圖。

如果 val 與 !val 被縮在同一個點，即為矛盾。
當關係為 (a or b) and (c or !d) and …

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 <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXN 262144
vector<int> g[MAXN];
int vfind[MAXN], findIdx;
int stk[MAXN], stkIdx;
int in_stk[MAXN], visited[MAXN];
int contract[MAXN];
int scc_cnt;
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(int i = 0; i < g[nd].size(); i++) {
        if(!visited[g[nd][i]])
            mn = min(mn, scc(g[nd][i]));
        if(in_stk[g[nd][i]])
            mn = min(mn, vfind[g[nd][i]]);
    }
    if(mn == vfind[nd]) {
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
        } while(stk[stkIdx--] != nd);
        scc_cnt++;
    }
    return mn;
}
int main() {
    int testcase, n, m, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        n = (n + 1)* 2;
        for(int i = 0; i < n; i++)
            g[i].clear();
        // 2*node: false, 2*node+1: true
        while(m--) {
        	int a, b, x, y;
        	scanf("%d %d", &a, &b);
        	x = abs(a), y = abs(b);
        	x <<= 1, y <<= 1;
        	if (a < 0)	x ^= 1;
        	if (b < 0)	y ^= 1;
        	g[x^1].push_back(y);
        	g[y^1].push_back(x);
        }
        //SCC
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        scc_cnt = 1;
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                stkIdx = 0;
                findIdx = 0;
                scc(i);
            }
        }
        //2-SAT check
        int hasSol = 1;
        for(int i = 0; i < n && hasSol; i+=2)
            if(contract[i] == contract[i^1])
                hasSol = 0;
            
        printf("Case %d: %s\n", ++cases, hasSol ? "Yes" : "No");
    }
    return 0;
}
/*
2
3 5
-1 2
1 3
3 -2
1 -3
-2 -3
4 4
-1 2
1 3
-2 4
-3 -4
*/
Read More +
解題區/解題區 - UVa

UVa 12749 - John's Tree

Problem

目標生成一個有根樹，每個節點的 degree 最多為 V，並且樹深度恰好為 D。

請問最多有幾個節點。

Sample Input

1
2
3
4
3
0 1
1 2
1 5

Sample Output

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

Solution

很明顯是一個等比級數的計算，中間牽涉到除法，利用費馬小定理找到乘法反元素，藉此完成除法。

特別記住，V 只得是 degree 而搜尋樹的分支數，因此 degree 會包含跟父親的連接。特別小心 V = 1 的情況，要不兩個點要不一個點，而 V = 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
#include <stdio.h>
#include <assert.h>
const long long mod = 1000000007LL;
long long mul(long long a, long long b) {
    long long ret = 0;
    for( ; b != 0 ; b>>=1, (a<<=1)%=mod)
        if(b&1)
            (ret += a) %= mod;
    return ret;
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = (ret * x)%mod;
        y >>= 1LL, x = (x * x)%mod;
    }
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    long long D, V;
    scanf("%d", &testcase);
    while (scanf("%lld %lld", &D, &V) == 2) {
        assert(D >= 0 && V > 0 && D <= 2e+9 && V <= 2e+9);
        long long ret = 0;
        if (D == 0)			ret = 1;
        else if (D == 1)	ret = (V + 1)%mod;
        else if (V == 1)	ret = -1;
        else if (V == 2)	ret = (1 + D * 2)%mod;
        else {
            ret = mpow(V - 1, D, mod) - 1 + mod;
            ret = ret * mpow(V - 2, mod - 2, mod) %mod;
            ret = ret * V %mod;
            ret = (ret + 1 + mod)%mod;
            assert(ret >= 0);
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
1000
0 1
1 2
1 5
500 1
0 500
2000000000 2000000000
*/
Read More +
解題區/解題區 - UVa

UVa 10186 - Euro Cup 2000

Problem

給定 N 個隊伍，兩兩隊伍比賽兩次，已知部分比賽結果，勝者得三分，平手各得一分，輸者 零分。請問在剩餘比賽中，每個隊伍的最佳排名與最糟排名。

重點：剩下的比賽最多十場。

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
2
A
B
1
A B 1 0
5
Ger
Tur
Fin
Nor
Mol
14
Fin Mol 3 2
Tur Nor 3 0
Tur Ger 1 0
Nor Fin 1 0
Mol Ger 1 3
Tur Fin 1 3
Nor Mol 2 2
Nor Ger 0 3
Tur Mol 2 0
Ger Fin 2 0
Mol Fin 0 0
Ger Mol 6 1
Fin Tur 2 4
Mol Nor 0 0
0

Sample Output

1
2
3
4
5
6
7
8
9
10
Group #1
A 1-2
B 1-2
Group #2
Ger 1-3
Tur 1-3
Fin 1-4
Nor 1-5
Mol 4-5

Solution

一開始以為題目只給我 10 場資訊，結果一直想不到 P 的解法，只有 10 場就直接窮舉 10 場的結果紀錄即可。

額外閱讀 Matrix67 网络流和棒球赛淘汰问题

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int g[32][32] = {}, score[32], n;
int brank[32], wrank[32];
vector< pair<int, int> > game;
void dfs(int idx) {
    if (idx == game.size()) {
        vector< pair<int, int> > board;
        int r;
        for (int i = 0; i < n; i++)
            board.push_back(make_pair(score[i], i));
        sort(board.begin(), board.end(), greater< pair<int, int> >());
        for (int i = 0; i < n; i++) {
            r = (int)(lower_bound(board.begin(), board.end(), make_pair(score[i], 0x3f3f3f3f), greater< pair<int, int> >()) 
                        - board.begin());
            brank[i] = min(brank[i], r);
            r = (int)(upper_bound(board.begin(), board.end(), make_pair(score[i], -1), greater< pair<int, int> >()) 
                        - board.begin());
            wrank[i] = max(wrank[i], r);
        }
        return ;
    }
    int x = game[idx].first, y = game[idx].second;
    score[x] += 3;
    dfs(idx+1);
    score[x] -= 3;
    
    score[y] += 3;
    dfs(idx+1);
    score[y] -= 3;
    
    score[x]++, score[y]++;
    dfs(idx+1);
    score[x]--, score[y]--;
}
int main() {
    char s[128];
    int cases = 0;
    int m, x, y, a, b;
    string name[128];
    while (scanf("%d", &n) == 1 && n) {
        map<string, int> R;
        memset(g, 0, sizeof(g));
        memset(score, 0, sizeof(score));
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            R[s] = i, name[i] = s;
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%s", s);
            x = R[s];
            scanf("%s", s);
            y = R[s];
            g[x][y]++, g[y][x]++;
            scanf("%d %d", &a, &b);
            if (a < b)		score[y] += 3;
            else if (a > b)	score[x] += 3;
            else			score[x]++, score[y]++;
        }
        
        for (int i = 0; i < n; i++)
            brank[i] = 0x3f3f3f3f, wrank[i] = -1;
        game.clear();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = 0; k < 2 - g[i][j]; k++) {
                    game.push_back(make_pair(i, j));
                }
            }
        }
        dfs(0);
        printf("Group #%d\n", ++cases);
        for (int i = 0; i < n; i++) {
            printf("%s %d-%d\n", name[i].c_str(), brank[i] + 1, wrank[i]);
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

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

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

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

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

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 +
解題區/出題解題

[ACM 題目] 竹馬不敵天降

Problem

「話說，剛剛明明說的是合乎聖誕節的商品。這不是 H-GAME 嗎？哪裡有聖誕元素啊！」
「嗯，真虧你發現這點啊，但還是有點可惜，這是全齡版，沒有工口哦！」
「不管怎麼樣，一點也沒合聖誕節啊。」
「雖然你有好好學習許多東西，但對本質上完全沒有理解。」
「最近開始覺得有點明白了 …」
「那麼就來說明下這個作品吧」
「是一年前發售的大人氣美少女遊戲的續篇吧？」
「是的，那為什麼你沒有察覺到－『一年前』這句話所包含的意義」
「對於期盼著的人那就意味著 … 與戀人時隔一年的再會！」

在 GALGAME 故事發展過程中，竹馬幾乎沒勝過天降，走哪一條線進行發展正是玩 GALGAME 的樂趣。

然而有一款極為糟糕的 GALGAME 的初始方式則是在一開始選定座標下，系統會根據座標找到附近最鄰近少女，並且在隨後的故事情節都會圍繞這名少女。

遊戲的地圖設計很簡單，用一個矩形表示，現在已知 N 名少女的所在地 (都在矩形內部)。一開始選定的座標也必須落在矩形內，請問玩哪每個線路機率分布為何？

Input

輸入有多組測資。

每組第一行會有三個整數 N, A, B，表示在$[0:A] \times [0:B]$ 地圖中有 N 個已知座標。
接下來會有 N 行，每行上會有兩個整數 x, y，表示每名少女所在的座標$(x, y)$ 保證不會有重疊的情況。

$(0 < N \le 100, 0 < A, B \le 1000, 0 \le x \le A, 0 \le y \le B)$

Output

對於每組測資輸出一行，根據輸入順序輸出每一個故事線的機率。

Sample Input

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

Sample Output

1
2
3
Case 1: 0.500 0.500
Case 2: 0.300 0.700
Case 3: 0.292 0.313 0.396

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
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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6 
#define MAXN 32767
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);
    }
    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;
    }
};
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);
}
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;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
};
Pt getIntersect(Seg a, Seg b) {
    double a1, b1, c1, a2, b2, c2;
    double dx, dy, d;
    a1 = a.s.y - a.e.y, b1 = a.e.x - a.s.x;
    c1 = a1 * a.s.x + b1 * a.s.y;
    a2 = b.s.y - b.e.y, b2 = b.e.x - b.s.x;
    c2 = a2 * b.s.x + b2 * b.s.y;
    dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
    d = a1 * b2 - a2 * b1;
    return Pt(dx/d, dy/d);
}
Seg deq[MAXN];
vector<Pt> halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < -eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < -eps)
    	front++;
    	
    vector<Pt> ret;
    for (int i = front; i < rear; i++) {
        Pt p = getIntersect(deq[i], deq[i+1]);
        ret.push_back(p);
    }
    if (rear > front + 1) {
        Pt p = getIntersect(deq[front], deq[rear]);
        ret.push_back(p);
    } 
    return ret;
}
double calc_convexarea(const vector<Pt> &p) {
    double ret = 0;
    int n = p.size();
    for(int i = 0, j = n - 1; i < n; j = i++)
        ret += p[j].x * p[i].y - p[j].y * p[i].x;
    return fabs(ret /2.0);
}
int main() {
    int n, A, B, cases = 0;
    Pt p[128], mid, vij;
    while (scanf("%d %d %d", &n, &A, &B) == 3) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &p[i].x, &p[i].y);
        printf("Case %d:", ++cases);
        for (int i = 0; i < n; i++) {
            int m = 0;
            vector<Seg> segs;
            segs.resize(n - 1 + 4);
            for (int j = 0; j < n; j++) {
                if (i == j)	continue;
                mid.x = (p[i].x + p[j].x) /2.0;
                mid.y = (p[i].y + p[j].y) /2.0;
                vij.x = mid.x - (p[j].y - p[i].y);
                vij.y = mid.y + (p[j].x - p[i].x);
                segs[m] = Seg(mid, vij), m++;
            }
            segs[m++] = Seg(Pt(0, 0), Pt(A, 0));
            segs[m++] = Seg(Pt(A, 0), Pt(A, B));
            segs[m++] = Seg(Pt(A, B), Pt(0, B));
            segs[m++] = Seg(Pt(0, B), Pt(0, 0));
            vector<Pt> convex = halfPlaneIntersect(segs);
//			for (int j = 0; j < convex.size(); j++)
//				printf("%lf %lf\n", convex[j].x, convex[j].y);
//			puts("--");
            printf(" %.3lf", calc_convexarea(convex) / (A * B));
        }
        puts("");
    }
    return 0;
}
/*
2 5 3
1 2
4 2
2 5 3
1 1
2 2
3 5 3
1 1
2 2
4 1
*/
Read More +