解題區/解題區 - UVa

UVa 1125 - Sherlock Holmes

Problem

有 N 個箱子，每個箱子都有 M 顆球，每一個箱子的黑、白球分配的個數不同，希望分成兩堆，每一堆必須有 N/2 個箱子，並且要符合黑球、或白球必須在兩堆佔有多數 (> 50%) 的情況。

假設佔有的比例分別為 m1, m2，最大化 min(m1, m2)。

Sample Input

1
2
3
4
5
6
4 
30 
17 13
12 18
20 10
14 16

Sample Output

1
W 51.67

Solution

N 很大，M 也很大。一開始就目測需要 random 的隨機交換法，這樣湊出答案的機率是挺高的。

當然這有點不靠譜，使用 dp 背包問題，由於狀態數量太多，必須使用 set 壓縮。

dp[i][j] 表示放置前 i 個箱子，存在 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
#include <stdio.h>
#include <stdlib.h> 
#include <set>
#include <algorithm>
using namespace std;
int main() {
    int n, m, A[32767];
    while (scanf("%d %d", &n, &m) == 2) {
        int w, b, wsum = 0, bsum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &w, &b);
            wsum += w, bsum += b;
            A[i] = w;
        }
        if (wsum == bsum || n%2 != 0) {
            puts("No solution");
            continue;
        }
        char major = 'W';
        if (wsum < bsum) {
            major = 'B';
            wsum = bsum;
            for (int i = 0; i < n; i++)
                A[i] = m - A[i];
        }
        set<int> dp[32767];
        set<int>::iterator it;
        dp[0].insert(0);
        for (int i = 0; i < n; i++) {
            int w = A[i];
            for (int j = min(i, n/2 - 1); j >= 0; j--) {
                for (it = dp[j].begin(); it != dp[j].end(); it++)
                    dp[j+1].insert((*it) + w);
            }
        }
        
        int ret = -1;
        int half = n/2 * m / 2;
        for (it = dp[n/2].begin(); it != dp[n/2].end(); it++) {
            if (*it <= wsum/2 && *it > half)
                ret = max(ret, *it);
        }
        if (ret < 0) {
            puts("No solution");
        } else {
            printf("%c %.2lf\n", major, ret * 100.0 / (n/2 * m));
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 881 - Points, Polygons and Containers

Problem

有數個不相交的簡單多變形，構成類似等高線的地勢圖，每一個簡單多邊形都有其代碼編號，接著有數個不按照順序的詢問點，請問所在的位置是在哪一塊。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
1
4
3 18 16 1 16 1 1 18 1
1 2 15 2 2 14 2
4 15 2 15 15 3 15
2 10 4 4 10 4 4
4
2 20 4
4 3 11
3 5 6
1 12 11

Sample Output

1
2
3
4
1 4
2 0
3 2
4 1

Solution

首先用射線法，找到所有的簡單多邊形關係，O(n^2) 找到 DAG 圖。

接著將 DAG 圖縮成一個 rooted tree 圖，挑選深度最深的節點，外圍的深度是 0，越靠近裡面深度越高。

接著對於每一組詢問，從 root 開始走訪，直到沒有可以包含住這個點。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <iostream>
#include <assert.h>
using namespace std;
#define eps 1e-8
#define MAXN 1024
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);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    } 
};
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 cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.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;
}
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(p[i], p[j], q))
            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;
}
const double pi = acos(-1);
Pt polygon[MAXN][512];
int pn[MAXN], parent[MAXN], visited[MAXN], depth[MAXN];
int pid[MAXN];
vector<int> g[MAXN], tree[MAXN];
void dfs(int u) {
    visited[u] = 1, depth[u] = 0, parent[u] = -1;
    int d = -1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (visited[v] == 0)	dfs(v);
        if (depth[v] > d)
            d = depth[v], parent[u] = v;
    }
    depth[u] = d + 1;
}
int query(int u, Pt q) {
    for (int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i];
        if (inPolygon(polygon[v], pn[v], q)) {
            return query(v, q);
        }
    }
    return u;
}
int main() {
    int testcase, n, m;
    string line;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        assert(n < MAXN);
        while (getchar() != '\n');
        for (int i = 0; i < n; i++) {
            getline(cin, line);
            stringstream sin(line);
            int m = 0;
            sin >> pid[i];
            while (sin >> polygon[i][m].x >> polygon[i][m].y) {
                m++;
                assert(m < 512);
            }
            pn[i] = m;
        }
        pid[n] = 0;
        for (int i = 0; i <= n; i++)
            g[i].clear(), visited[i] = 0, tree[i].clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)	continue;
                if (inPolygon(polygon[i], pn[i], polygon[j][0]))
                    g[j].push_back(i);
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (visited[i] == 0)
                dfs(i);
        }
        for (int i = 0; i < n; i++)
            if (parent[i] == -1)
                tree[n].push_back(i);
            else
                tree[parent[i]].push_back(i);
//		for (int i = 0; i < n; i++)
//			printf("%d: %d\n", pid[i], parent[i]);
        scanf("%d", &m);
        assert(m < 32767);
        int out[32767] = {};
        for (int i = 0; i < m; i++) {
            Pt q;
            int id;
            scanf("%d %lf %lf", &id, &q.x, &q.y);
            assert(id <= m);
            out[id] = query(n, q);
        }
        for (int i = 1; i <= m; i++)
            printf("%d %d\n", i, pid[out[i]]);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
5
0 0
50 50
100 0
100 100
0 100
2
49 50
50 51
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
*/
Read More +
解題區/解題區 - UVa

UVa 879 - Circuit Nets

Problem

給定一組電路的連接，請問有多少個電網個數。

Sample Input

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

Sample Output

1
3

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
#include <stdio.h>
#include <sstream>
using namespace std;
int parent[65536], weight[65536];
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return 0;
    if (weight[x] > weight[y])
        parent[y] = x, weight[x] += weight[y];
    else
        parent[x] = y, weight[y] += weight[x];
    return 1;
}
int main() {
    int testcase, n;
    char line[1024];
    scanf("%d", &testcase);
    while (getchar() != '\n');
    while (getchar() != '\n');
    while (testcase--) {
        scanf("%d", &n);
        while (getchar() != '\n');
        for (int i = 0; i < n; i++)
            parent[i] = i, weight[i] = 1;
        int ret = n, x, y;
        while (gets(line) && line[0] != '\0') {
            stringstream sin(line);
            while (sin >> x >> y) {
                x--, y--;
                ret -= joint(x, y);
            }
        }
        printf("%d\n", ret);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
1
14
 1 11 7 11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10 
*/
Read More +
解題區/解題區 - UVa

UVa 844 - Pousse

Problem

模擬一款推硬幣的遊戲，在一個 N x N 的盤面，可以從上下左右四個方向塞入自己的硬幣。

現在有兩個人輪流玩，一開始由 ‘X’ 作為先手，塞入硬幣的過程中，會將同行或同列的硬幣往前推，如果同一個的硬幣個數大於 N，則末端的硬幣將會掉出盤面。

模擬遊戲，直到其中一個玩家的連線個數大於另一名玩家，連線個數只看行、列皆具有相同硬幣的情況。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT

Sample Output

1
2
3
TIE GAME
X WINS

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
#include <stdio.h> 
#include <string.h>
char cmd[32767][64];
char g[128][128];
int n;
int isCompleted() {
    int Oline = 0, Xline = 0, cnt;
    char c;
    for (int i = 0; i < n; i++) {
        c = g[i][0], cnt = 0;
        for (int j = 0; g[i][0] == g[i][j] && j < n; cnt++, j++);
        if (cnt == n && c != ' ') {
            Oline += c == 'O';
            Xline += c == 'X';
        }
        c = g[0][i], cnt = 0;
        for (int j = 0; g[0][i] == g[j][i] && j < n; cnt++, j++);
        if (cnt == n && c != ' ') {
            Oline += c == 'O';
            Xline += c == 'X';
        }
    }
    return Oline == Xline ? 0 : (Oline < Xline ? -1 : 1);
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        int m = 0;
        while (scanf("%s", cmd[m]) == 1) {
            if (!strcmp(cmd[m], "QUIT"))
                break;
            m++;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = ' ';
        int ret = 0, turn = 0;
        for (int i = 0; i < m; i++, turn = !turn) {
            int x;
            sscanf(cmd[i]+1, "%d", &x);
            x--;
            if (cmd[i][0] == 'L') {
                int idx = 0;
                while (idx < n && g[x][idx] != ' ')	idx++;
                for (int i = idx; i > 0; i--)
                    g[x][i] = g[x][i-1];
                g[x][0] = turn ? 'O' : 'X';
            }
            if (cmd[i][0] == 'R') {
                int idx = n-1;
                while (idx > 0 && g[x][idx] != ' ')	idx--;
                for (int i = idx; i < n-1; i++)
                    g[x][i] = g[x][i+1];
                g[x][n-1] = turn ? 'O' : 'X';
            }
            if (cmd[i][0] == 'T') {
                int idx = 0;
                while (idx < n && g[idx][x] != ' ')	idx++;
                for (int i = idx; i > 0; i--)
                    g[i][x] = g[i-1][x];
                g[0][x] = turn ? 'O' : 'X';
            }			
            if (cmd[i][0] == 'B') {
                int idx = n-1;
                while (idx > 0 && g[idx][x] != ' ')	idx--;
                for (int i = idx; i < n-1; i++)
                    g[i][x] = g[i+1][x];
                g[n-1][x] = turn ? 'O' : 'X';
            }
//			for (int i = 0; i < n; i++, puts(""))
//				for (int j = 0; j < n; j++)
//					putchar(g[i][j]);
//			puts("---");
            if (ret = isCompleted())
                break;
        }
        if (ret)
            puts(ret < 0 ? "X WINS" : "O WINS");
        else
            puts("TIE GAME");
        if (testcase)
            puts("");
    }
    return 0;
}
/*
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT
*/
Read More +
解題區/解題區 - UVa

UVa 828 - Deciphering Messages

Problem

給一加密原則，現在要求解密，並且在只有一組文本情況下輸出正解。

一開始給定一字串 L，接著加密時，每一組訊息的 word，由左而右加密。

  • 如果字符 c 存在於 L，使用凱薩加密 shift N 位。
  • 如果字符 c 不存在於 L，輸出三個字浮，分別是 L[m]、c 使用凱薩加密 shift N 位、L[m+1]。每一次使用這一條 m 就 +1，假想 L 是環狀的。

Sample Input

1
2
3
4
5
6
7
8
9
10
1
RSAEIO
2
5
RTSSKAEAGE
GRSCAV
RGSSCAV
RUSIQO
RUSSGAACEV JEGIITOOGR

Sample Output

1
2
3
4
5
RICE
error in encryption
EAT
error in encryption
SEAT HERE

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
int inL[128] = {}, N, Q, Llen;
char L[128], s[1024];
char text[128];
int sol;
void dfs(int idx, int pl, int m) {
    while (s[idx] == ' ')	text[pl++] = ' ', idx++;
    if (sol >= 2)	return;
    if (s[idx] == '\0') {
        sol++;
        text[pl] = '\0';
        puts(text);
        return;
    }
    
    char a, b, c;
    for (int i = 'A'; i <= 'Z'; i++) {
        if (inL[i]) {
            a = L[m%Llen];
            b = (i-'A'+N)%26 + 'A';
            c = L[(m+1)%Llen];
            text[pl] = i;
            if (a == s[idx] && b == s[idx+1] && c == s[idx+2]) {
                dfs(idx+3, pl+1, m+1);
            }
        } else {
            a = (i-'A'+N)%26 + 'A';
            text[pl] = i;
            if (a == s[idx]) {
                dfs(idx+1, pl+1, m);
            }
        } 
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", L);
        scanf("%d %d", &N, &Q);
        memset(inL, 0, sizeof(inL));
        for (int i = 0; L[i]; i++)
            inL[L[i]] = 1;
        Llen = strlen(L);
        while (getchar() != '\n');
        for (int i = 0; i < Q; i++) {
            gets(s);
            sol = 0;
            dfs(0, 0, 0);
            if (sol != 1)
                puts("error in encryption");
        }
        if (testcase)
            puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 818 - Cutting Chains

Problem

有 n 個鐵環，現在已知鐵環之間緊扣在一起，目標要把鐵環串成一鏈，可以選擇將鐵環剪開，隨後再將其串在一起。

找最少剪開的次數。

Sample Input

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

Sample Output

1
2
3
4
5
Set 1: Minimum links to open is 1
Set 2: Minimum links to open is 2
Set 3: Minimum links to open is 1
Set 4: Minimum links to open is 1
Set 5: Minimum links to open is 1

Solution

n < 15，窮舉哪幾個環需要剪開，接著把這些需要剪開的環先抽出來，查看剩餘的鐵環的情況，必須滿足都是鏈狀，而且連通元件的個數不能大於剪開的個數 + 1，如此一來，在放回剪開的環才能串在一起。

鏈狀的檢查：檢查每一個 node 的 degree 不可大於 2，同時不應該存在環。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int g[16][16], gmask[16];
int visited[16];
int dfs(int u, int p, int open, int n) {
    visited[u] = 1;
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        if (g[u][i] == 0 || i == p)
            continue;
        if (visited[i] || dfs(i, u, open, n))
            return 1;
    }
    return 0;
}
int checkChain(int open, int n) {
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        int t = gmask[i]^(gmask[i]&open);
        int degree = __builtin_popcount(t);
        if (degree > 2)
            return 0;
    }
    
    int op = __builtin_popcount(open);
    int comp = 0;
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)	continue;
        if (visited[i] == 0) {
            if (dfs(i, -1, open, n)) // have cycle
                return 0;
            comp++;
        }
    }
    return op >= comp - 1;
}
int main() {
    int cases = 0;
    int n, x, y;
    while (scanf("%d", &n) == 1 && n) {
        memset(g, 0, sizeof(g));
        memset(gmask, 0, sizeof(gmask));
        while (scanf("%d %d", &x, &y) == 2) {
            if (x == -1)	break;
            x--, y--;
            g[x][y] = g[y][x] = 1;
            gmask[x] |= 1<<y, gmask[y] |= 1<<x;
        }
        
        int ret = 0x3f3f3f3f;
        for (int i = 0; i < (1<<n); i++) { // 1: open.
            int op = __builtin_popcount(i);
            if (op >= ret)	continue;
            if (checkChain(i, n))
                ret = min(ret, op); 
        }
        printf("Set %d: Minimum links to open is %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 814 - The Letter Carrier's Rounds

Problem

模擬郵件發送的協定訊息，給定給一台 mail server 上的使用者名稱，接著發送群組訊息。

每一組發送者，會按照輸入順序的 mail server，將相同的 server 上的使用者統一發送，如果存在不合法的使用者名稱，必須回傳找不到，如果對一個 mail server 中都沒有合法使用者，則忽略此次傳送。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report!  --Fiona
*
*

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
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
Connection between Cairo and MexicoCity
     HELO Cairo
     250
     MAIL FROM:<Hamdy@Cairo>
     250
     RCPT TO:<Conrado@MexicoCity>
     250
     RCPT TO:<Lisa@MexicoCity>
     550
     DATA
     354
     Congratulations on your efforts !!
     --Hamdy
     .
     250
     QUIT
     221
Connection between Cairo and SanFrancisco
     HELO Cairo
     250
     MAIL FROM:<Hamdy@Cairo>
     250
     RCPT TO:<Shariff@SanFrancisco>
     250
     DATA
     354
     Congratulations on your efforts !!
     --Hamdy
     .
     250
     QUIT
     221
Connection between London and HongKong
     HELO London
     250
     MAIL FROM:<Fiona@London>
     250
     RCPT TO:<Chen@HongKong>
     250
     DATA
     354
     Thanks for the report!  --Fiona
     .
     250
     QUIT
     221
Connection between London and Paris
     HELO London
     250
     MAIL FROM:<Fiona@London>
     250
     RCPT TO:<Natasha@Paris>
     550
     QUIT
     221

Solution

一個純模擬的題目，關於此類協定可以在計算機網路中學到。

保證寄信者都是合法的，小心每一行的資訊可能很長，用 char array 很容易 buffer overflow。也因此掛了很多 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
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <vector> 
using namespace std;
set<string> MTA;
int readMTA() {
    string cmd, mta, name;
    int n;
    while (cin >> cmd) {
        if (cmd == "*")	return 1;
        cin >> mta >> n; 
        for (int i = 0; i < n; i++) {
            cin >> name;
            MTA.insert(string(name) + "@" + string(mta));
        }
    }
    return 0;
}
void parse_address(const string& s, string& user, string& mta) {
  int k = s.find('@');
  user = s.substr(0, k);
  mta = s.substr(k+1);
}
int main() {
    string msg;
    readMTA();
    while (cin >> msg) {
        if (msg[0] == '*')	break;	
        vector<string> user, mta, mail;
        set<string> S;
        vector<int>	used;
        string u, m;
        parse_address(msg, u, m);
        user.push_back(u), mta.push_back(m);
        while (cin >> msg && msg[0] != '*') {
            parse_address(msg, u, m);
            if (S.count(u + "@" + m))	continue;
            S.insert(u + "@" + m);
            user.push_back(u), mta.push_back(m);
        }
        while (getchar() != '\n');
        while (getline(cin, msg) && msg[0] != '*')
            mail.push_back(msg);
        used.resize(user.size(), 0);
        for (int i = 1; i < user.size(); i++) {
            if (used[i])	continue;
            printf("Connection between %s and %s\n", mta[0].c_str(), mta[i].c_str());
            printf("     HELO %s\n", mta[0].c_str());
            printf("     250\n");
            printf("     MAIL FROM:<%s@%s>\n", user[0].c_str(), mta[0].c_str());
            printf("     250\n");
            int s = 0;
            for (int j = i; j < user.size(); j++) {
                if (mta[j] == mta[i]) {
                    used[j] = 1;
                    printf("     RCPT TO:<%s@%s>\n", user[j].c_str(), mta[j].c_str());
                    if (MTA.count(user[j] + "@" + mta[j]))
                        printf("     250\n"), s++;
                    else
                        printf("     550\n");
                }
            }
            if (s > 0) {
                printf("     DATA\n");
                printf("     354\n");
                for (int j = 0; j < mail.size(); j++)
                    printf("     %s\n", mail[j].c_str());
                printf("     .\n");
                printf("     250\n");
            }
            printf("     QUIT\n");
            printf("     221\n");
        }
    }
    return 0;
}
/*
MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report!  --Fiona
*
*
*/
Read More +
解題區/解題區 - UVa

UVa 810 - A Dicey Problem

Problem

給一個 2D 地圖，上面放置一骰子，人從 2D 地圖的下方往上方看，骰子必須貼著某一條邊，往上下左右的地方滾過去，滾的時候必須滿足，其骰子上方的點數與地圖該格的點數相同，或者是移動到星號位置。

一開始給定骰子面向玩家的點數、以及骰子上方的點數，骰子滾動出去回到原本地方的最短路徑為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DICEMAZE1
3 3 1 2 5 1
-1 2 4
5 5 6
6 -1 -1
DICEMAZE2
4 7 2 6 3 6
6 4 6 0 2 6 4
1 2 -1 5 3 6 1
5 3 4 5 6 4 2
4 1 2 0 3 -1 6
DICEMAZE3
3 3 1 1 2 4
2 2 3
4 5 6
-1 -1 -1
END

Sample Output

1
2
3
4
5
6
7
8
DICEMAZE1
  (1,2),(2,2),(2,3),(3,3),(3,2),(3,1),(2,1),(1,1),(1,2)
DICEMAZE2
  (2,6),(2,5),(2,4),(2,3),(2,2),(3,2),(4,2),(4,1),(3,1),
  (2,1),(2,2),(2,3),(2,4),(2,5),(1,5),(1,6),(1,7),(2,7),
  (3,7),(4,7),(4,6),(3,6),(2,6)
DICEMAZE3
  No Solution Possible

Solution

每一個 2D 位置 (x, y) 會有兩個骰子資訊做為紀錄，只需要知道骰子的兩個面，即可知道骰子的結構。

針對其狀態進行 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
#include <stdio.h>
#include <string.h> 
#include <queue>
#include <vector>
#include <assert.h>
using namespace std;
#define MAXSTATE 65536
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct state {
    int x, y, top, front;
    state *prev;
} states[MAXSTATE];
int statesIdx;
int n, m, sx, sy, dtop, dfront;
int g[32][32];
state* getNewState(int x, int y, int dtop, int dfront, state *prev = NULL) {
    state *p = &states[statesIdx++];
    assert (statesIdx < MAXSTATE);
    p->x = x, p->y = y, p->top = dtop, p->front = dfront, p->prev = prev;
    return p;
}
int diceTable[7][7]; // [front][top] = right
void rotateDice(int dir, int dtop, int dfront, int &rtop, int &rfront) {
    rtop = rfront = 1;
    if (dir == 0) { // roll up
        rtop = dfront, rfront = 7 - dtop;
    } else if (dir == 1) { // roll down
        rtop = 7 - dfront, rfront = dtop;
    } else if (dir == 2) { // roll left
        rfront = dfront;
        rtop = diceTable[dfront][dtop];
    } else if (dir == 3) { // roll right
        rfront = dfront;
        rtop = 7 - diceTable[dfront][dtop];
    }
}
void bfs(int sx, int sy, int dtop, int dfront) {
    statesIdx = 0;
    int used[32][32][7][7] = {}; // used[x][y][dtop][dfront]
    int tx, ty, tdtop, tdfront;
    queue<state*> Q;
    state *u, *v;
    Q.push(getNewState(sx, sy, dtop, dfront));
    used[sx][sy][dtop][dfront] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        for (int i = 0; i < 4; i++) {
            tx = u->x + dx[i], ty = u->y + dy[i];
            if (tx <= 0 || ty <= 0 || tx > n || ty > m)
                continue;
            if (g[tx][ty] != -1 && g[tx][ty] != u->top)
                continue;
            if (tx == sx && ty == sy) { // back to start square, print result
                vector< pair<int, int> > ret;
                state *p = u;
                ret.push_back(make_pair(sx, sy));
                while (p != NULL) {
                    ret.push_back(make_pair(p->x, p->y));
                    p = p->prev;
                }
                for (int i = ret.size() - 1, j = 0; i >= 0; i--, j++) {
                    if (j%9 == 0)	printf("  ");
                    if (j%9 != 0)	printf(",");
                    printf("(%d,%d)", ret[i].first, ret[i].second);					if (j%9 == 8 || i == 0)	{
                        if (i)	printf(",\n");
                        else	puts("");
                    }
                }
                return ;
            }
            rotateDice(i, u->top, u->front, tdtop, tdfront);
            if (used[tx][ty][tdtop][tdfront])
                continue;
            used[tx][ty][tdtop][tdfront] = 1;
            v = getNewState(tx, ty, tdtop, tdfront, u);
            Q.push(v);
        }
    }
    puts("  No Solution Possible");
}
int main() {
    // diceface[front][top] = right
    diceTable[1][2] = 4, diceTable[1][3] = 2, diceTable[1][4] = 5, diceTable[1][5] = 3;
    diceTable[2][1] = 3, diceTable[2][3] = 6, diceTable[2][4] = 1, diceTable[2][6] = 4;
    diceTable[3][1] = 5, diceTable[3][2] = 1, diceTable[3][5] = 6, diceTable[3][6] = 2;
    diceTable[4][1] = 2, diceTable[4][2] = 6, diceTable[4][5] = 1, diceTable[4][6] = 5;
    diceTable[5][1] = 4, diceTable[5][3] = 1, diceTable[5][4] = 6, diceTable[5][6] = 3;
    diceTable[6][2] = 3, diceTable[6][3] = 5, diceTable[6][4] = 2, diceTable[6][5] = 4;
    
    char testcase[1024];
    while (scanf("%s", testcase) == 1) {
        if (!strcmp("END", testcase))
            break;
        scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &dtop, &dfront);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &g[i][j]);
        printf("%s\n", testcase);
        bfs(sx, sy, dtop, dfront);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1665 - Islands

Problem

給一個地勢圖，詢問若高度低於 x 時，有多少連通子圖。

Sample Input

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

Sample Output

1
2 3 1 0 0

Solution

由於詢問操作的 x 是嚴格遞增，可以發現盤面上的元素越來越少。如果反過來操作，從高度 x 由大到小開始詢問，就可以發現元素越來越多，同時是一個聯集的操作，如此一來可以使用并查集運行。

把每一個高度位置，從高到低排序，針對詢問依序將地點放置進去，每次的放置必須與相鄰存在的元素進行聯集。

為了加快速度

  • 使用基數排序，加快對於一開始需要的排序成本，已達到線性需求。
  • 優化輸入
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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm> 
using namespace std;
#define MAXN 1024
int g[MAXN][MAXN], h[131072], out[131072];
int parent[MAXN * MAXN], weight[MAXN * MAXN];
struct Pos {
    int x, y, h;
    Pos(int a = 0, int b = 0, int c = 0):
        x(a), y(b), h(c) {}
    bool operator<(const Pos &a) const {
        return h > a.h;
    }
};
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return 0;
    if (weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
Pos D[MAXN * MAXN], TMP[MAXN * MAXN];
void RadixSort(Pos *A, Pos *B, int n) {
    int a, x, d, C[256];
    Pos *T;
    for(x = 0; x < 4; x++) {
        d = x * 8;
        for(a = 0; a < 256; a++)     	C[a] = 0;
        for(a = n-1; a >= 0; a--)      	C[(A[a].h>>d)&255]++;
        for(a = 256 - 2; a >= 0; a--)   C[a] += C[a+1];
        for(a = n-1; a >= 0; a--)   	B[--C[(A[a].h>>d)&255]] = A[a];
        T = A, A = B, B = T;
    }    
}
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    const int dx[] = {0, 0, 1, -1};
    const int dy[] = {1, -1, 0, 0};
    int testcase, n, m, q, tx, ty;
//	scanf("%d", &testcase);
    ReadInt(&testcase);
    while (testcase--) {
//		scanf("%d %d", &n, &m);
        ReadInt(&n);
        ReadInt(&m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
//				scanf("%d", &g[i][j]);
                ReadInt(&g[i][j]);
//		scanf("%d", &q);
        ReadInt(&q);
        for (int i = 0; i < q; i++)
//			scanf("%d", &h[i]);
            ReadInt(&h[i]);
        
        int didx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                D[didx++] = Pos(i, j, g[i][j]);
            }
        }
        RadixSort(D, TMP, n*m);
        int idx = 0, nm = n*m, sum = 0;
        Pos u;
        for (int i = nm; i >= 0; i--)
            parent[i] = i, weight[i] = 1;
        for (int i = q - 1; i >= 0; i--) {
            while (idx < nm && D[idx].h > h[i]) {
                sum++;
                u = D[idx++];
//				printf("add %d %d - %d\n", u.x, u.y, u.h);
                for (int j = 0; j < 4; j++) {
                    tx = u.x + dx[j], ty = u.y + dy[j];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    if (g[tx][ty] > h[i]) {
                        sum -= joint(u.x * m + u.y, tx * m + ty);
                    }
                }
            }
            out[i] = sum;
//			printf("%d\n", sum);
        }
        for (int i = 0; i < q; i++)
            printf("%d ", out[i]);
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12412 - A Typical Homework

Problem

寫一個模擬成績登錄系統的程式。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
0011223344 1 John 79 98 91 100
0022334455 1 Tom 59 72 60 81
0011223344 2 Alice 100 100 100 100
2423475629 2 John 60 80 30 99
0
3
0022334455
John
0
5
1
2
0011223344
0
5
0
4
0

Sample Output

1
略

Solution

純苦工題目。

Try adding 1e-5 to all floating point values as you print them.

難怪會 WA，看到時小夥伴們都傻眼，不過應該也是因為大部分仍然使用 float 輸出，用 double 反而會得到 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
// WTF > Try adding 1e-5 to all floating point values as you print them.
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define eps 1e-5
class Student {
    public:
    string SID, name;
    int CID, score[4];
    Student(int c, int d[], string a = "", string b = "") {
        SID = a, name = b;
        CID = c;
        for (int i = 0; i < 4; i++)
            score[i] = d[i];
    }
    void print() {
        printf("%s %d %s %d %d %d %d %d %.2lf\n", 
            SID.c_str(), CID, name.c_str(),
                score[0], score[1], score[2], score[3], getTotal(), getAvg());
    }
    int getTotal() {
        return score[0] + score[1] + score[2] + score[3];
    }
    double getAvg() {
        return (score[0] + score[1] + score[2] + score[3]) / 4.0 + eps;
    }
};
class SPMS {
    public:
    map<string, int> R_SID;
    vector<Student> students;
    void printMainMenu() {
        puts("Welcome to Student Performance Management System (SPMS).\n");
        puts("1 - Add\n2 - Remove\n3 - Query\n4 - Show ranking\n5 - Show Statistics\n0 - Exit\n");
    }
    void addStudent() {
        char SID[128], name[128];
        int CID, score[4];
        while (true) {
            puts("Please enter the SID, CID, name and four scores. Enter 0 to finish.");
            scanf("%s", SID);
            if (!strcmp(SID, "0"))
                return;
            scanf("%d %s", &CID, name);
            for (int i = 0; i < 4; i++)	scanf("%d", &score[i]);
            
            if (R_SID[SID]) {
                puts("Duplicated SID.");
            } else {
                R_SID[SID]++;
                Student u(CID, score, SID, name);
                students.push_back(u);
            }
        }
    }
    void removeStudent() {
        char s[128];
        while (true) {
            puts("Please enter SID or name. Enter 0 to finish.");
            scanf("%s", s);
            if (!strcmp(s, "0"))
                return;
            int cnt = 0;
            for (vector<Student>::iterator it = students.begin();
                it != students.end(); ) {
                if (it->SID == s || it->name == s) {
                    cnt++;
                    R_SID[it->SID]--;
                    it = students.erase(it);
                } else {
                    it++;
                }
            }
            printf("%d student(s) removed.\n", cnt);
        }
    }
    int getRank(Student u) {
        int ret = 1;
        for (int i = 0; i < students.size(); i++)
            if (students[i].getTotal() > u.getTotal())
                ret++;
        return ret;
    }
    void queryStudent() {
        char s[128];
        while (true) {
            puts("Please enter SID or name. Enter 0 to finish.");
            scanf("%s", s);
            if (!strcmp(s, "0"))
                return;
            for (vector<Student>::iterator it = students.begin();
                it != students.end(); it++) {
                if (it->SID == s || it->name == s) {
                    printf("%d ", getRank(*it));
                    it->print();
                }
            }
        }
    }
    void printRankList() {
        puts("Showing the ranklist hurts students' self-esteem. Don't do that.");
    }
    void printStatistics() {
        puts("Please enter class ID, 0 for the whole statistics.");
        int CID;
        scanf("%d", &CID);
        
        int pass[4] = {}, fail[4] = {}; // subject
        int sum[4] = {}, n = 0;
        int sumtable[5] = {};
        vector<int> table; // student
        table.resize(students.size(), 0); 
        for (int i = 0; i < students.size(); i++) {
            if (CID && CID != students[i].CID)
                continue;
            n++;
            for (int j = 0; j < 4; j++) {
                sum[j] += students[i].score[j];
                if (students[i].score[j] >= 60) {
                    pass[j]++;
                    table[i]++;
                } else {
                    fail[j]++;
                }
            }
            sumtable[table[i]]++;
        }
        
        for (int i = 3; i >= 1; i--)
            sumtable[i] += sumtable[i+1];
        printf("Chinese\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
            (double) sum[0] / n + eps, pass[0], fail[0]);
        printf("Mathematics\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
            (double) sum[1] / n + eps, pass[1], fail[1]);
        printf("English\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
            (double) sum[2] / n + eps, pass[2], fail[2]);
        printf("Programming\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
            (double) sum[3] / n + eps, pass[3], fail[3]);
        printf("Overall:\nNumber of students who passed all subjects: %d\nNumber of students who passed 3 or more subjects: %d\nNumber of students who passed 2 or more subjects: %d\nNumber of students who passed 1 or more subjects: %d\nNumber of students who failed all subjects: %d\n\n",
            sumtable[4], sumtable[3], sumtable[2], sumtable[1], sumtable[0]);
    }
} spms;
int main() {
    int cmd;
    while (true) {
        spms.printMainMenu();	
        scanf("%d", &cmd);
        if (cmd == 0)
            return 0;
        if (cmd == 1)
            spms.addStudent();
        if (cmd == 2)
            spms.removeStudent();
        if (cmd == 3)
            spms.queryStudent();
        if (cmd == 4)
            spms.printRankList();
        if (cmd == 5)
            spms.printStatistics();
    }	
    return 0;
}
/*
1
0011223344 1 John 79 98 91 100
0022334455 1 Tom 59 72 60 81
0011223344 2 Alice 100 100 100 100
2423475629 2 John 60 80 30 99
0
3
0022334455
John
0
5
1
2
*/
Read More +