解題區/解題區 - 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 +
學校課程/資料庫系統

資料庫系統－劉寶鈞

single value function 的意思？問問 劉寶鈞 老師 吧！

課程心得

強烈建議遠離 此課程，分析如下描述， 劉寶鈞 老師強烈建議把定義背得一模一樣，最好不要翻譯，因為很難達到一樣的水平，也很難說好。資料庫歷史悠久，因此歷史課程會持續一陣子，課程內容並沒有相當多的實務經驗。老師秉持著數年專業，保證嚴格批閱所有考卷。

如果沒人抱怨，我來說說這鬼畜的經歷，絕不能讓其消散。

期中考分析

保證題目描述與錯字 100% 複製考卷

  1. 傳統檔案系統為何不能共享 而資料庫如何做到可以共享？(10 分)
    傳統檔案系統的資料存在各自的電腦中，而且格式不一，有相當大的重複資料，由於各自管理所需要的資料，更新時間也會不一致，因此在共享的支援相當不利，共享的結果不一定是最新、不能同時匹配在不同的電腦中的資料。
    資料庫系統將資料集中化管理，收集到同一個系統中，並且藉由 SQL 中的 DML 支持使用者進行共享資料的存取、檢索，由系統管理同一時間多名使用者對資料的存取。
    上述為零分作答，劉寶鈞老師說明若沒提到 SCHEME DATA 一律零分。

  2. 以 Relation Model 為例 說明 Data Model 之三要素。(10 分)
    略說－有 資料表示法、資料的操作、約束條件，舉幾個例子便可完事。
    此題作答還算正常，但是沒有舉例子大致上會被扣到慘不忍睹。

  3. 比較說明 DDL 及 DML。(10 分)
    略說－Data Definition Language、Data Manipulation Language，分別是定義資料庫、資料表用的，另一個是對使用者詢問、操作資料。
    此題作答還算正常，但是沒有舉例子大致上會被扣到慘不忍睹。

  4. 何謂 3-value logic ？並證明 P OR (NOT P) = 1 在 2-value logic 是成立的，但在 3-value logic is not always true。(10 分)
    3-value logic 分別為 true, false, unknown。

在 2-value 中

P NOT P P OR (NOT P)
T F T
F T T

在 3-value 中

P NOT P P OR (NOT P)
T F T
F T T
unknown unknown unknown

用 0 表示 false, 1 表示 true, 1/2 表示 unknown，AND = MIN, OR = MAX, NOT = 1 - x。
=> P = 1/2, P OR (NOT P) = MAX(0.5, 1 - 0.5) = 0.5 = unknown。

unknown 不屬於 true，因此 3-value 在 P OR (NOT P) = 1 not always true。
以上作答零分，劉寶鈞老師在考卷上對 unknown 用紅筆寫了 What ? 一開始直接零分，之後才勉為其難拿到五分。投影片上面也這麼寫的，到底在 What ? 什麼勁，你自己拿出來講的東西上都這麼寫，寫下去分數還沒有？

  1. 寫出若含 NULL value 五個 single value function 的規則。(10 分)
    WHAT the fuck about single value function ?
    略列表 AND OR NOT EQUAL PRODUCT 的幾種情況。
    上述為零分作答，劉寶鈞老師說明 single value function 的要寫出 aggregate function。我問老師「為什麼不直接寫 aggregate function？」老師回答道「就是故意不這麼寫。」

  2. 寫出 SQL query 之 SELECT, FROM, WHERE, GROUP BY, HAVING 之義意。(10 分)
    錯字直接按表抄，這一題原本對於 HAVING 的解釋不夠完善，掛掉直接只剩下五分。WTF，五個定義錯一個就直接砍一半分數？對於 HAVING 只有寫提供 WHERE 無法進行 aggregation function 的判斷條件，必須與 GROUP BY 一起使用。這樣難道錯了嗎？GROUP BY 都解釋了，你還說我錯？

結語

我不是肚子裡的肥蟲，一定是我蠢得無可救藥，拿了不及格的成績？

很久沒有衝動想要殺人，這下子又開始想殺人。

助教不替老師改考卷，讓老師這樣改考卷行嗎？

我是個壞學生，這門課真的氣死人，出口罵髒話根本不足以洩憤。

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 +