解題區/解題區 - UVa

UVa 11052 - Economic phone calls

Problem

給一台手機的通話紀錄，通話紀錄分成兩類，其中一類標記為 + 表示重要訊息，另一類標記為 - 表示不重要訊息。手機中的歷史紀錄時間不會紀錄年份，靠著有順序的嚴格遞增表示同一年。

假使現在只想要知道 + 的所有電話紀錄發現在哪一年份，可以忽略部分的 - 來推估每一通電話的年份，請問最少要保留幾份紀錄。

每一組的最後一筆測資表示現在年份。

Sample Input

1
2
3
4
5
6
7
8
9
7
12:31:23:59 0123456789012345 +
07:21:19:00 1337 -
01:01:00:00 0987654321 -
07:21:14:00 1337 -
11:11:11:11 11111111111 +
01:01:00:00 0123456789 +
01:01:00:00 0987654321 -
0

Sample Output

1
6

Solution

可以推測，從現在到最早期的 + 紀錄之間的每一年至少需要一通電話。

首先將輸入的每一通電話算出年份，然後找到需要回溯的最早期電話，在這更之前的電話紀錄就可以無視，推算時間與更早期的紀錄無關。

定義 dp[i] 表示第 i 筆電話紀錄後，能夠使得 [i, n] 之間 + 紀錄回溯年代的最少紀錄筆數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int n;
    int time[1024];
    char mark[1024][4];
    while (scanf("%d", &n) == 1 && n) {
        int mm, dd, HH, MM;
        for (int i = 0; i < n; i++) {
            scanf("%d:%d:%d:%d %*s %s", &mm, &dd, &HH, &MM, mark[i]);
            time[i] = ((mm * 31 + dd) * 24 + HH) * 60 + MM;
        }
        int year[1024] = {}, cur_year;
        for (int i = 1; i < n; i++) {
            if (time[i] <= time[i-1])
                year[i] = year[i-1] + 1;
            else
                year[i] = year[i-1];
            cur_year = year[i];
        }
        int dp[1024] = {}, last = -1, trace = -1;
        // dp[i] : record i satisfy that all `+` record can trace in year[i]~cur_year
        for (int i = n - 1; i >= 0; i--) {
            if (last == -1 && year[i] == cur_year)
                dp[i] = 1; 		// record now time.
            else
                dp[i] = n - i; 	// record all after this. (init value)
            if (last == -1 && (mark[i][0] == '+' || year[i] != cur_year))
                last = i;
            if (mark[i][0] == '+')
                trace = i;
        }
        for (int i = last; i >= trace; i--) {
            for (int j = i + 1; j < n; j++) {
                if (year[i] == year[j])
                    dp[i] = min(dp[i], dp[j] + 1);
                else if (time[i] >= time[j] && year[j] - year[i] == 1)
                    dp[i] = min(dp[i], dp[j] + 1);
                else
                    break;
                if (mark[j][0] == '+')	break;
            }
        }
//		for (int i = 0; i < n; i++)
//			printf("[%d] y %d dp %d\n", i, year[i], dp[i]);
//		printf("%d %d\n", last, trace);
        printf("%d\n", dp[trace]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10841 - Lift Hopping in the Real World

Problem

在一棟高樓中有 N 台電梯，每個電梯停靠的樓層有所限制，同時每一台電梯在相鄰樓層移動的所需時間也不同。轉換電梯 (出電梯) 需要 5 秒的時間，然後可以轉搭其他電梯。並不曉得一開始電梯停靠在那一個樓層，即使下了電梯也要等待電梯移動到該層。

請問從 0 樓到 K 樓的最少時間為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30
2 30
10 1
0 5 10 12 14 20 25 30
2 4 6 8 10 12 14 22 25 28 29
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50
1 1
2
0 2 4 6 8 10

Sample Output

1
2
3
4
1295
600
8505
IMPOSSIBLE

Solution

很明顯地，把每一個樓層當節點，可以根據電梯的移動建造邊，邊與邊之間的轉換必須多 5 花費以及電梯在最慘情況下移動到該層的花費。

電梯在最慘情況下移動到該層的花費 : 電梯在最高樓層或者是最低樓層停靠，收到指令後移動到該層。

直接對其使用最短路即可。

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 <vector>
#include <queue> 
#include <algorithm>
#include <sstream>
using namespace std;
struct edge {
    int to, v, label;
    edge(int a=0, int b=0, int c=0):
        to(a), v(b), label(c){}
};
vector<edge> g[128];
int mxfloor[128], mnfloor[128], T[128];
int dist[128], inq[128];
void spfa(int N, int K) {
    for (int i = 0; i < 128; i++)
        dist[i] = 0x3f3f3f3f;
    int u, v, w, l;
    queue<int> Q;
    Q.push(0), dist[0] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].to, l = g[u][i].label;
            w = g[u][i].v + T[l] * max(mxfloor[l] - u, u - mnfloor[l]) + 5;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    inq[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
    if (dist[K] == 0x3f3f3f3f)
        puts("IMPOSSIBLE");
    else
        printf("%d\n", K == 0 ? 0 : (dist[K] - 5));
}
int main() {
    int N, K, f[128];
    char s[1024];
    while (scanf("%d %d", &N, &K) == 2) {
        for (int i = 0; i < N; i++)
            scanf("%d", &T[i]);
        for (int i = 0; i < 128; i++)
            g[i].clear();
        while (getchar() != '\n');
        for (int i = 0; i < N; i++) {
            gets(s);
            stringstream sin(s);
            int n = 0;
            while (sin >> f[n])
                n++;
            mxfloor[i] = -1, mnfloor[i] = 0x3f3f3f3f;
            for (int j = 0; j < n; j++) {
                mxfloor[i] = max(mxfloor[i], f[j]);
                mnfloor[i] = min(mnfloor[i], f[j]);
                for (int k = 0; k < n; k++) {
                    if (j == k)	continue;
                    g[f[j]].push_back(edge(f[k], abs(f[k] - f[j]) * T[i], i));
                }
            }
        }
        spfa(N, K);
    }
    return 0;
}
/*
2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30
2 30
10 1
0 5 10 12 14 20 25 30
2 4 6 8 10 12 14 22 25 28 29
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50
1 1
2
0 2 4 6 8 10
*/
Read More +
解題區/解題區 - UVa

UVa 10704 - Traffic!

Problem

一個華容道盤面，求最少步數。

水平的棋子只能水平移動、垂直的旗子只能垂直移動，移動一次的定義為按照可執行的方向移動數步，也就是說水平移動兩步、三步也只算一次移動。

Sample Input

1
2
3
4
5
6
1
2 1
1 4 0
3 1 0 1 3 0 5
2 0 0 4 4
1 5 2

Sample Output

1
The minimal number of moves to solve puzzle 1 is 8.

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
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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define hash_mod 1000003
struct state {
    char g[6][6];
    unsigned int hash() {
        unsigned int a = 63689, b = 378551;
        unsigned int value = 0;
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                value = value * a + g[i][j];
                a *= b;
            }
        }
        return value % hash_mod;
    }
    bool operator<(const state &a) const {
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                if (g[i][j] != a.g[i][j])
                    return g[i][j] < a.g[i][j];
            }
        }
        return false;
    }
    void print() {
        for (int i = 0; i < 6; i++, puts(""))
            for (int j = 0; j < 6; j++)
                printf("%c", g[i][j]);
        puts("--");
    }
};
void color(state &s, int x, int y, int w, int h, char c) {
    for (int i = x; i < x + w; i++)
        for (int j = y; j < y + h; j++)
            s.g[i][j] = c;
}
map<state, int> hash[hash_mod];
state shiftup(state &u, int x, int y) {
    state v = u;
    char c = v.g[x][y];
    for (int i = 0; x+i < 6 && v.g[x+i][y] == c; i++)
        swap(v.g[x+i-1][y], v.g[x+i][y]);
    return v;
}
state shiftdown(state &u, int x, int y) {
    state v = u;
    char c = v.g[x][y];
    for (int i = 0; x+i >= 0 && v.g[x+i][y] == c; i--)
        swap(v.g[x+i+1][y], v.g[x+i][y]);
    return v;
}
state shiftleft(state &u, int x, int y) {
    state v = u;
    char c = v.g[x][y];
    for (int i = 0; y+i < 6 && v.g[x][y+i] == c; i++)
        swap(v.g[x][y+i-1], v.g[x][y+i]);
    return v;
}
state shiftright(state &u, int x, int y) {
    state v = u;
    char c = v.g[x][y];
    for (int i = 0; y+i >= 0 && v.g[x][y+i] == c; i--)
        swap(v.g[x][y+i+1], v.g[x][y+i]);
    return v;
}
int bfs(state init) {
    for (int i = 0; i < hash_mod; i++)
        hash[i].clear();
    int h = init.hash(), ti, tj;
    state u, v;
    queue<state> Q;
    Q.push(init), hash[h][init] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        h = u.hash();
        int step = hash[h][u];
        if (u.g[2][4] == 'w' && u.g[2][5] == 'w') {
//			u.print();
            return step;
        }
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                if (u.g[i][j] < 'a' || u.g[i][j] > 'z')
                    continue;
                ti = i, tj = j;
                v = u;
                while (ti-1 >= 0 && v.g[ti-1][tj] == ' ' && ti+1 < 6 && v.g[ti][tj] == v.g[ti+1][tj]) { // shift up
                    v = shiftup(v, ti, tj);
                    ti--;
                    h = v.hash();
                    if (hash[h].find(v) == hash[h].end()) {
                        hash[h][v] = step+1;
                        Q.push(v);
                    }
//					v.print();
                }
                ti = i, tj = j;
                v = u;
                while (ti-1 >= 0 && v.g[ti-1][tj] == v.g[ti][tj] && ti+1 < 6 && v.g[ti+1][tj] == ' ') { // shift down
                    v = shiftdown(v, ti, tj);
                    ti++;
                    h = v.hash();
                    if (hash[h].find(v) == hash[h].end()) {
                        hash[h][v] = step+1;
                        Q.push(v);
                    }
//					v.print();
                }
                ti = i, tj = j;
                v = u;
                while (tj-1 >= 0 && v.g[ti][tj-1] == ' ' && tj+1 < 6 && v.g[ti][tj] == v.g[ti][tj+1]) { // shift left
                    v = shiftleft(v, ti, tj);
                    tj--;
                    h = v.hash();
                    if (hash[h].find(v) == hash[h].end()) {
                        hash[h][v] = step+1;
                        Q.push(v);
                    }
//					v.print();
                }
                ti = i, tj = j;
                v = u;
                while (tj-1 >= 0 && v.g[ti][tj-1] == v.g[ti][tj] && tj+1 < 6 && v.g[ti][tj+1] == ' ') { // shift right
                    v = shiftright(v, ti, tj);
                    tj++;
                    h = v.hash();
                    if (hash[h].find(v) == hash[h].end()) {
                        hash[h][v] = step+1;
                        Q.push(v);
                    }
//					v.print();
                }
            }
        }
    }
    return -1;
}
int main() {
    int testcase, cases = 0;
    int wx, wy, n, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        state init;
        char label = 'a';
        memset(init.g, ' ', sizeof(init.g));
        scanf("%d %d", &wx, &wy);
        color(init, wx, wy, 1, 2, 'w');
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            color(init, x, y, 2, 1, label);
            label++;
        }
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            color(init, x, y, 3, 1, label);
            label++;
        }
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            color(init, x, y, 1, 2, label);
            label++;
        }
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            color(init, x, y, 1, 3, label);
            label++;
        }
        int ret = bfs(init);
        printf("The minimal number of moves to solve puzzle %d is %d.\n", ++cases, ret);
    }
    return 0;
}
/*
1
2 1
1 4 0
3 1 0 1 3 0 5
2 0 0 4 4
1 5 2
99999
2 0
0
0
0
0
2 1
1 4 0
4 1 0 1 3 0 5 1 4
3 0 0 4 4 3 4
1 5 2
2 1
2 0 2 4 1
4 1 0 1 3 0 5 1 4
2 0 0 4 4
1 5 2
*/
Read More +
解題區/解題區 - UVa

UVa 932 - Checking the N-Queens Problem

Problem

給定一個 N * N 的棋盤，檢查 N 個皇后是否衝突，如果存有衝突，嘗試移動一個皇后 (根據他所在的位置進行移動)，如果可以有解則輸出，反之輸出找不到。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5
00X00
X0000
000X0
0X000
0000X
5
0X000
X0000
000X0
0X000
0000X

Sample Output

1
2
3
4
5
6
7
8
9
YES
NO
YES
00X00
X0000
000X0
0X000
0000X

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int check(int qx[], int qy[], int n) {
    static int used[32] = {}, testcase = 0;
    testcase++;
    for (int i = 0; i < n; i++) {
        if (used[qx[i]] == testcase) return 0;
        used[qx[i]] = testcase;
    }
    testcase++;
    for (int i = 0; i < n; i++) {
        if (used[qy[i]] == testcase) return 0;
        used[qy[i]] = testcase;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (abs(qx[i] - qx[j]) == abs(qy[i] - qy[j]))
                return 0;
        }
    }
    return 1;
}
int main() {
    int n, cases = 0, tx, ty;
    char g[32][32];
    const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
    const int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
    while (scanf("%d", &n) == 1) {
        if (cases++)	puts("");
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int qx[32], qy[32], m = 0;
        for (int i = 0; i < n;i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 'X')
                    qx[m] = i, qy[m] = j, m++;
            }
        }
        if (check(qx, qy, m))
            puts("YES");
        else {
            puts("NO");
            int ok = 0;
            for (int i = 0; i < m && !ok; i++) {
                for (int j = 0; j < 8 && !ok; j++) {
                    tx = qx[i] + dx[j], ty = qy[i] + dy[j];
                    while (true) {
                        if (tx < 0 || ty < 0 || tx >= n || ty >= n)
                            break;
                        if (g[tx][ty] == '0') {
                            swap(tx, qx[i]), swap(ty, qy[i]);
                            if (check(qx, qy, m)) {
                                puts("YES");
                                ok = 1;
                                swap(g[qx[i]][qy[i]], g[tx][ty]);
                                for (int i = 0; i < n; i++)
                                    puts(g[i]);
                                break;
                            }
                            swap(tx, qx[i]), swap(ty, qy[i]);
                        }
                        tx += dx[j], ty += dy[j];
                    }
                }
            }
            if (!ok)
                puts("NO");
        }
    }
    return 0;
}
/*
5
00X00
X0000
000X0
0X000
0000X
5
0X000
X0000
000X0
0X000
0000X
*/
Read More +
解題區/解題區 - UVa

UVa 10838 - The Pawn Chess

Problem

在縮小版本國際象棋中，兩個人只能操控士兵 (Pawn)，其中白色先手並且位於棋盤下方，操控棋子為大寫 P，黑色後手為小寫 p。

士兵在移動時，只能往敵方軍營前進，只能往前一步走到空的，或者是吃掉對方斜著走。也就是當敵方在斜角時才能往斜角走。

將對方逼得無路可走時 (全滅)，或者是我方棋子抵達對方底線時遊戲宣告結束。請問白色先手最少要幾步才能獲勝？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
 
.ppp
....
.PPP
....
 
...p
...p
pP.P
...P

Sample Output

1
2
white (7)
black (2)

Solution

一種很傳統的博弈問題，一般而言對於劃分狀態最小化即可。但是效率會很差，因為狀態分化的太多，必須走訪所有的狀態才能知道結果。基於這一點，有了 alpha-beta 剪枝，但這種剪枝相當依賴走訪順序，因此也不保證是比較好的搜索，但已經提供相當不錯的思路。

pruning 中文翻譯：修剪

alpha-beta pruning

主要為博弈剪枝用，求最少步數獲勝 (對於是否必勝的判斷在效率上有待考量。)

策略

假設 [999, -999] 作為步數的決策 (用實際數值來假設)

  • 正數表示先手必勝的步數，越大表示需要的步數越少，
  • 負數表示後手必勝的步數，越小表示需要的步數越少。

根據博弈的遞迴寫法，步數從深度 999 往下找，先手要最大化其結果 (最後最少步數用 999 - 結果)，後手要最小化其結果 (最後最少步數用 999 + 結果)。分層討論的話，就是取最大 - 取最小 - 取最大 … 交錯。

我們把已知的兩個結果做討論，定義當前搜索過程中得到的 alpha 是先手最佳化，beta 是後手最佳化。

父節點會將已經找到的部分解傳遞給孩子繼續搜索，假使父親是取最大值，還是則都是要取最小值，如果其中一個孩子的最小值 p 已知，另一個孩子搜索到一半時，發現其中它的孩子回傳 q < p，其實可以放棄搜索，因為這一層還要取最小，隨後回父親要取最大，不可能比 p 還要大。直接放棄 son 的所有分支搜索。

1
2
3
4
5
  parent (first player maximum) alpha = maximum(p, son, ...)
 /     \
p      son (second player minimum) beta = minimum(q, ...)
       /
      q

發現思路其實相當簡單，關鍵在於如何表示最小化、最大化之間對於博弈的定義。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h> 
#include <algorithm>
using namespace std;
struct state {
    char g[4][5];
    int isEnd() {
        int b = 0, w = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++)  {
                if (g[i][j] == 'p')
                    b++;
                if (g[i][j] == 'P')
                    w++;
            }
        }
        if (b == 0 || w == 0)	return 1;
        for (int i = 0; i < 4; i++) {
            if (g[0][i] == 'P')	return 1;
            if (g[3][i] == 'p')	return 1;
        }
        return 0;
    }
};
int alpha_beta(state board, int depth, int alpha, int beta) {
    if (board.isEnd())
        return depth%2 == 0 ? -depth : depth;
    int movable = 0;
    if (depth%2 == 0) { // first player
        for (int i = 1; i < 4; i++)  {
            for (int j = 0; j < 4; j++) {
                if (board.g[i][j] == 'P') {
                    for (int k = j - 1; k <= j + 1; k++) {
                        if (k < 0 || k >= 4)
                            continue;
                        if ((k != j && board.g[i-1][k] == 'p') || (k == j && board.g[i-1][k] == '.')) {
                            state s = board;
                            s.g[i][j] = '.', s.g[i-1][k] = 'P';
                            alpha = max(alpha, alpha_beta(s, depth - 1, alpha, beta));
                            if (beta <= alpha)
                                return alpha;
                            movable = 1;
                        }
                    }
                }
            }
        }
        if (!movable)	return -depth;
        return alpha;
    } else {
        for (int i = 0; i < 3; i++)  {
            for (int j = 0; j < 4; j++) {
                if (board.g[i][j] == 'p') {
                    for (int k = j - 1; k <= j + 1; k++) {
                        if (k < 0 || k >= 4)
                            continue;
                        if ((k != j && board.g[i+1][k] == 'P') || (k == j && board.g[i+1][k] == '.')) {
                            state s = board;
                            s.g[i][j] = '.', s.g[i+1][k] = 'p';
                            beta = min(beta, alpha_beta(s, depth - 1, alpha, beta));
                            if (beta <= alpha)
                                return beta;
                            movable = 1;
                        }
                    }
                }
            }
        }
        if (!movable)	return depth;
        return beta;
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        state init;
        for (int i = 0; i < 4; i++)
            scanf("%s", init.g[i]);
        int ret = alpha_beta(init, 36, -9999, 9999);
        if (ret >= 0)
            printf("white (%d)\n", 36 - ret);
        else
            printf("black (%d)\n", 36 + ret);
    }
    return 0;
}
/*
2
.ppp
....
.PPP
....
...p
...p
pP.P
...P
*/
Read More +
解題區/解題區 - UVa

UVa 12120 - Photographic Tour

Problem

每個攝影師必須從起點走到終點，中間搭乘時會消耗車票，並且每個攝影師都要按照主辦單位給定的車票順序使用，而車票的花費要恰好對應到搭乘花費。

請問有多少地點可以是攝影師經過的地方。

Sample Input

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

Sample Output

1
2
Tour 1: 3
Tour 2: 0

Solution

紀錄兩個狀態，分別為起點到中繼點、中繼點到終點的結果。

起點到中繼點時，將記錄 dp1[i][j] 起點到中繼點 i，恰好使用第 j 張票。

終點到中繼點時，將記錄 dp2[i][j] 終點到中繼點 i，恰好使用第 n - j 張票。

隨後合併檢查是否中繼點可以構出一條路從起點到終點。

為了方便操作，將資料反轉丟入函數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector< pair<int, int> > g[1024];
void bfs(int u, int A[], int An, int rg[][128]) {
    int t;
    queue<int> Q, T;
    Q.push(u), T.push(0);
    rg[u][0] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        t = T.front(), T.pop();
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first;
            if (t < An && g[u][i].second == A[t]) {
                if (rg[v][t+1] == 0)  {
                    rg[v][t+1] = 1;
                    Q.push(v), T.push(t+1);
                }
            }
        }
    }
}
int main() {
    int n, m, t, cases = 0;
    int x, y, z, A[128]; 
    int g1[128][128], g2[128][128];
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &z);
            g[x].push_back(make_pair(y, z));
            g[y].push_back(make_pair(x, z));
        }
        scanf("%d", &t);
        for (int i = 0; i < t; i++)
            scanf("%d", &A[i]);
        
        memset(g1, 0, sizeof(g1));
        memset(g2, 0, sizeof(g2));
        bfs(0, A, t, g1);
        reverse(A, A+t);
        bfs(n-1, A, t, g2);
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int ok = 0;
            for (int j = 0; j <= t; j++)
                ok |= g1[i][j] && g2[i][t - j];
            ret += ok;
        }
        printf("Tour %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
3 2
0 1 1
0 2 2
3
1 1 2
3 2
0 1 1
0 2 2
1
1
0 0
*/
Read More +
解題區/解題區 - 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 +