解題區►解題區 - UVa

UVa 751 - Triangle War

Problem

兩名玩家進行放邊的操作，當其中一名玩家成功創建一個三角形，則可以再放入一邊，直到該操作無法創建一個新的三角形，則進行輪替。最大化自己與對方的分數差異。

一開始先模擬兩名玩家的操作過程。

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
4
6
2 4
4 5
5 9
3 6
2 5
3 5
7
2 4
4 5
5 9
3 6
2 5
3 5
7 8
6
1 2
2 3
1 3
2 4
2 5
4 5
10
1 2
2 5
3 6
5 8
4 7
6 10
2 4
4 5
4 8
7 8

Sample Output

1
2
3
4
Game 1: B wins.
Game 2: A wins.
Game 3: A wins.
Game 4: B wins.

Solution

這題很妙，總之先定義狀態 dp(盤面狀況，剩餘三角形) = 最大化差異。

那麼轉移方程要看操作是否造成輪替，如果仍然為自己，則把下一步的最大化結果累加上來，反之扣除。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
int dp[1<<18][11];
char used[1<<18][11] = {};
int trans[11][11], tri[10];
int countTri(int state) {
	int ret = 0;
	for (int i = 0; i < 9; i++) {
		if ((state&tri[i]) == tri[i])
			ret++;
	}
	return ret;
}
int dfs(int state, int score) {
	if (used[state][score])		return dp[state][score];
	used[state][score] = 1;
	
	int ret = 0, nstate, had = 9 - score, c, t;
	for (int i = 0; i < 18; i++) {
		if ((state>>i)&1) {
			nstate = state ^ (1<<i); // used it.
			c = countTri(((1<<18)-1)^nstate);
			if (c > had) { // create new
				t = c - had + dfs(nstate, score - (c - had));
				ret = max(ret, t);
			} else {
				t = score - dfs(nstate, score);
				ret = max(ret, t);
			}
		}
	}
	dp[state][score] = ret;
	return ret;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	trans[1][2] = 0, trans[1][3] = 1;
	trans[2][3] = 2;
	trans[2][4] = 3, trans[2][5] = 4, trans[3][5] = 5, trans[3][6] = 6;
	trans[4][5] = 7, trans[5][6] = 8;
	trans[4][7] = 9, trans[4][8] = 10, trans[5][8] = 11, trans[5][9] = 12, trans[6][9] = 13, trans[6][10] = 14;
	trans[7][8] = 15, trans[8][9] = 16, trans[9][10] = 17;
	tri[0] = (1<<0)|(1<<1)|(1<<2);
	tri[1] = (1<<3)|(1<<4)|(1<<7);
	tri[2] = (1<<2)|(1<<4)|(1<<5);
	tri[3] = (1<<5)|(1<<6)|(1<<8);
	tri[4] = (1<<9)|(1<<10)|(1<<15);
	tri[5] = (1<<7)|(1<<10)|(1<<11);
	tri[6] = (1<<11)|(1<<12)|(1<<16);
	tri[7] = (1<<8)|(1<<12)|(1<<13);
	tri[8] = (1<<13)|(1<<14)|(1<<17);
	int testcase, cases = 0;
	int n, x, y;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		
		int state = 0, A = 0, B = 0, turn = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &x, &y);
			if (x > y)	swap(x, y);
			int c = countTri(state|(1<<trans[x][y])) - countTri(state);
			if (c) {
				if (turn == 0)		A += c;
				else				B += c;
			} else {
				turn = !turn;
			}
			state |= 1<<trans[x][y];
		}
//		printf("score %d %d\n", A, B);
		state = ((1<<18)-1)^state; // unused: 1
		int had = A + B;
		int mx = dfs(state, 9 - had);
		if (turn == 0)	A += mx, B += 9 - had - mx;
		else			B += mx, A += 9 - had - mx;
		printf("Game %d: %s wins.\n", ++cases, A > B ? "A" : "B");
	}
	return 0;
}
/*
4
6
2 4
4 5
5 9
3 6
2 5
3 5
7
2 4
4 5
5 9
3 6
2 5
3 5
7 8
6
1 2
2 3
1 3
2 4
2 5
4 5
10
1 2
2 5
3 6
5 8
4 7
6 10
2 4
4 5
4 8
7 8
*/
Read More +
解題區►解題區 - UVa

UVa 509 - RAID

Problem

參照《算法競賽入門經典》一書

一種磁碟儲存的機制，磁碟除了資料儲存，同時也會賦予檢查碼，來修正錯誤的資訊，即便能力相當有限，最多修正一個錯誤位元。

現在要求的工作是進行錯誤位元的復原，並且輸出 16 進制下的資料，如果資料不足 4 bits，則剩餘位元接補上 0。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5 2 5
E
0001011111
0110111011
1011011111
1110101100
0010010111
3 2 5
E
0001111111
0111111011
xx11011111
3 5 1
O
11111
11xxx
x1111
0

Sample Output

1
2
3
Disk set 1 is valid, contents are: 6C7A79EDFC
Disk set 2 is invalid.
Disk set 3 is valid, contents are: FFC

Solution

這題很簡單，但是一直沒注意到陣列開太小而炸掉，我的預設記憶體不夠大而 WA。剩下的細節則注意錯誤位元如果是檢查碼就可以無視，而同時檢查碼只支持修正一個位元，如果需要修正兩個以上則表示無法復原。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;
char mem[128][65536];
int main() {
    int cases = 0;
    int D, S, B;
    char kind[8];
    while (scanf("%d %d %d", &D, &S, &B) == 3 && D) {
        scanf("%s", kind);
        for (int i = 0; i < D; i++)
            scanf("%s", mem[i]);
        int n = S * B, kv = kind[0] == 'E' ? 0 : 1;
        int err = 0;
        for (int i = 0, j = 0; i < n; i += S, j++) {
            j %= D;
            for (int p = i; p < i + S; p++) {
                int broken = 0, brokenPos = 0, XOR = 0;
                for (int k = 0; k < D; k++) {
                    if (mem[k][p] == 'x')
                        broken++, brokenPos = k;
                    else
                        XOR ^= mem[k][p] - '0';
                }
                if (broken >= 2)
                    err = 1;
                else if (broken == 1) {
                    if (brokenPos == j) {
                    } else {
                        mem[brokenPos][p] = '0' + (kv^XOR);
                    }
                } else {
                    if (XOR != kv)  err = 1;
                }
            }
        }
        printf("Disk set %d is ", ++cases);
        if (err) {
            puts("invalid.");
        } else {
            char buff[65536];
            memset(buff, '0', sizeof(buff));
            int m = 0;
            for (int i = 0, j = 0; i < n; i += S, j++) {
                j %= D;
                for (int k = 0; k < D; k++) {
                    if (k == j) continue;
                    for (int p = i; p < i + S; p++) {
                        buff[m++] = mem[k][p];
                    }
                }
            }
            printf("valid, contents are: ");
            for (int i = 0; i < m; i += 4) {
                int val = 0;
                val |= (buff[i + 0] - '0') << 3;
                val |= (buff[i + 1] - '0') << 2;
                val |= (buff[i + 2] - '0') << 1;
                val |= (buff[i + 3] - '0') << 0;
                printf("%X", val);
            }
            puts("");
        }
    }
    return 0;
}
/*
 
 5 2 5
 E
 xx01011111
 0110111011
 1011011111
 1110101100
 0010010111
 5 2 5
 E
 0001011111
 0110111011
 1011011111
 1110101100
 0010010111
 3 2 5
 E
 0001111111
 0111111011
 xx11011111
 3 5 1
 O
 11111
 11xxx
 x1111
 0
*/
Read More +
解題區►解題區 - UVa

UVa 506 - System Dependencies

Problem

參照《算法競賽入門經典》一書

軟體安裝時，會同時下載所需要的插件包，而插件包的軟體也有可能繼續安裝所需要的插件包。如此遞迴下去把所需要的元件都安裝好。

當安裝一個軟體時，分成使用者安裝和系統安裝兩種，使用者只能刪除自己安裝的軟體，其相依的插件包必須由系統來進行刪除，系統刪除時，會檢查是否還有其他軟體需要相依，若不存在相依，則會將此軟體刪除。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
INSTALL TELNET
INSTALL foo
REMOVE NETCARD
INSTALL BROWSER
INSTALL DNS
LIST
REMOVE TELNET
REMOVE NETCARD
REMOVE DNS
REMOVE NETCARD
INSTALL NETCARD
REMOVE TCPIP
REMOVE BROWSER
REMOVE TCPIP
END

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
DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
   Installing NETCARD
INSTALL TELNET
   Installing TCPIP
   Installing TELNET
INSTALL foo
   Installing foo
REMOVE NETCARD
   NETCARD is still needed.
INSTALL BROWSER
   Installing HTML
   Installing BROWSER
INSTALL DNS
   Installing DNS
LIST
   NETCARD
   TCPIP
   TELNET
   foo
   HTML
   BROWSER
   DNS
REMOVE TELNET
   Removing TELNET
REMOVE NETCARD
   NETCARD is still needed.
REMOVE DNS
   Removing DNS
REMOVE NETCARD
   NETCARD is still needed.
INSTALL NETCARD
   NETCARD is already installed.
REMOVE TCPIP
   TCPIP is still needed.
REMOVE BROWSER
   Removing BROWSER
   Removing HTML
   Removing TCPIP
REMOVE TCPIP
   TCPIP is not installed.
END

Solution

一道模擬，假想一張 DAG 圖，刪除時暴力檢查其逆向的依存軟體是否存在。

使用 STL 和遞迴可以讓程式更簡單易懂。

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
#include <stdio.h>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
vector<string> getArgs(char line[]) {
    stringstream sin(line);
    vector<string> ret;
    string token;
    while (sin >> token)
        ret.push_back(token);
    return ret;
}
map<string, int> name2id;
map<int, string> id2name;
map<int, vector<int> > dependInstall, invDependInstall;
map<int, int> installStatus;
vector<int> installList;
int getId(string s) {
    int &ret = name2id[s];
    if (ret == 0) {
        ret = (int) name2id.size();
        id2name[ret] = s;
    }
    return ret;
}
string getName(int id) {
    return id2name[id];
}
int isDepended(int id) {
    vector<int> &v = invDependInstall[id];
    for (int i = 0; i < v.size(); i++) {
        if (installStatus[v[i]])    return 1;
    }
    return 0;
}
void installSoft(int id, int top) {
    if (installStatus[id] == 0) {
        vector<int> &v = dependInstall[id];
        for (int i = 0; i < v.size(); i++)
            installSoft(v[i], 0);
        printf("   Installing %s\n", getName(id).c_str());
        installStatus[id] = top ? 1 : 2;
        installList.push_back(id);
    }
}
void removeSoft(int id, int top) {
    if ((top == 1 || installStatus[id] == 2) && !isDepended(id)) {
        installStatus[id] = 0;
        printf("   Removing %s\n", getName(id).c_str());
        vector<int> &v = dependInstall[id];
        for (int i = 0; i < v.size(); i++)
            removeSoft(v[i], 0);
        installList.erase(find(installList.begin(), installList.end(), id));
    }
}
int main() {
    char line[2048];
    while (gets(line)) {
        vector<string> args = getArgs(line);
        puts(line);
        if (args[0] == "DEPEND") {
            vector<int> softId;
            for (int i = 1; i < args.size(); i++) {
                softId.push_back(getId(args[i]));
            }
            vector<int> &v = dependInstall[softId[0]];
            for (int i = 1; i < softId.size(); i++) {
                v.push_back(softId[i]);
                invDependInstall[softId[i]].push_back(softId[0]);
            }
        } else if (args[0] == "INSTALL") {
            if (installStatus[getId(args[1])]) {
                printf("   %s is already installed.\n", args[1].c_str());
            } else {
                installSoft(getId(args[1]), 1);
            }
        } else if (args[0] == "REMOVE") {
            if (installStatus[getId(args[1])] == 0) {
                printf("   %s is not installed.\n", args[1].c_str());
            } else if (isDepended(getId(args[1]))) {
                printf("   %s is still needed.\n", args[1].c_str());
            } else {
                removeSoft(getId(args[1]), 1);
            }
        } else if (args[0] == "LIST") {
            for (int i = 0; i < installList.size(); i++) {
                printf("   %s\n", getName(installList[i]).c_str());
            }
        } else if (args[0] == "END") {
            break;
        }
    }
    return 0;
}
/*
 DEPEND   TELNET TCPIP NETCARD
 DEPEND TCPIP NETCARD
 DEPEND DNS TCPIP NETCARD
 DEPEND  BROWSER   TCPIP  HTML
 INSTALL NETCARD
 INSTALL TELNET
 INSTALL foo
 REMOVE NETCARD
 INSTALL BROWSER
 INSTALL DNS
 LIST
 REMOVE TELNET
 REMOVE NETCARD
 REMOVE DNS
 REMOVE NETCARD
 INSTALL NETCARD
 REMOVE TCPIP
 REMOVE BROWSER
 REMOVE TCPIP
 END
 */
Read More +
解題區►解題區 - UVa

UVa 212 - Use of Hospital Facilities

Problem

參照《算法競賽入門經典》一書

模擬醫院的手術室和恢復室(病房)，每個病人分配到一個手術室後，手術完成後會被送至恢復室，而送病人於手術室到恢復室都需要 t1 時間，而每個病人在手術室和恢復室的時間也各有不同。

當手術室和恢復室被使用完畢後，分別需要 t2, t3 的時間進行清除整潔工作，隨後才能再給下一位病人使用，保證每一位病人在過程中都能立即使用不會延誤。

編號小的病患，會先選擇可使用的場地，場地編號也會盡可能地小。

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
5 12 07 5 15 10 16
Jones
28 140
Smith
120 200
Thompson
23 75
Albright
19 82
Poucher
133 209
Comer
74 101
Perry
93 188
Page
111 223
Roggio
69 122
Brigham
42 79
Nute
22 71
Young
38 140
Bush
26 121
Cates
120 248
Johnson
86 181
White
92 140

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
 Patient          Operating Room          Recovery Room
 #  Name     Room#  Begin   End      Bed#  Begin    End
 ------------------------------------------------------
 1  Jones      1    7:00    7:28      3    7:33    9:53
 2  Smith      2    7:00    9:00      1    9:05   12:25
 3  Thompson   3    7:00    7:23      2    7:28    8:43
 4  Albright   4    7:00    7:19      1    7:24    8:46
 5  Poucher    5    7:00    9:13      5    9:18   12:47
 6  Comer      4    7:34    8:48      4    8:53   10:34
 7  Perry      3    7:38    9:11      2    9:16   12:24
 8  Page       1    7:43    9:34      6    9:39   13:22
 9  Roggio     4    9:03   10:12      9   10:17   12:19
10  Brigham    2    9:15    9:57      8   10:02   11:21
11  Nute       3    9:26    9:48      7    9:53   11:04
12  Young      5    9:28   10:06      3   10:11   12:31
13  Bush       1    9:49   10:15     10   10:20   12:21
14  Cates      3   10:03   12:03      8   12:08   16:16
15  Johnson    2   10:12   11:38      4   11:43   14:44
16  White      5   10:21   11:53      7   11:58   14:18
Facility Utilization
Type  # Minutes  % Used
-------------------------
Room  1     165   29.68
Room  2     248   44.60
Room  3     258   46.40
Room  4     162   29.14
Room  5     263   47.30
Bed   1     282   50.72
Bed   2     263   47.30
Bed   3     280   50.36
Bed   4     282   50.72
Bed   5     209   37.59
Bed   6     223   40.11
Bed   7     211   37.95
Bed   8     327   58.81
Bed   9     122   21.94
Bed  10     121   21.76
Bed  11       0    0.00
Bed  12       0    0.00

Solution

建議使用一種時間軸的概念，維護一個 priority_queue 來知道下一個事件發生時間，接著在那時間掃描可能發生事件，這樣維護會比較容易寫。

出題者到處打雜呢！

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <sstream>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct Patient {
    string name;
    int pa, pb;
    int aBegin, aEnd, bBegin, bEnd, aid, bid;
    Patient(int a = 0, int b = 0, string s = ""):
    pa(a), pb(b), name(s) {}
} D[2048];
int main() {
    int N, M, K, ST_T, PA_T, PB_T, PAB_T;
    char s[1024];
    int x, y;
    while (scanf("%d %d %d %d %d %d %d", &N, &M, &ST_T, &PAB_T, &PA_T, &PB_T, &K) == 7) {
        for (int i = 0; i < K; i++) {
            scanf("%s %d %d", s, &x, &y);
            D[i] = Patient(x, y, s);
        }
        int aWorking[32] = {}, bWorking[32] = {};
        int aFinTime[32] = {}, bFinTime[32] = {};
        int aPid[32], bPid[32], aUsed[32] = {}, bUsed[32] = {};
        int preTime = -1, pid = 0;
        
        memset(aPid, -1, sizeof(aPid));
        memset(bPid, -1, sizeof(bPid));
        
        priority_queue<int, vector<int>, greater<int> > timeline;
        timeline.push(ST_T * 60);
        while (!timeline.empty()) {
            int now = timeline.top();
            timeline.pop();
            if (now == preTime) continue;
            preTime = now;
            vector<int> A2B;
            for (int i = 0; i < N; i++) {
                if (aWorking[i] && aFinTime[i] <= now) {
                    aWorking[i] = 0;
                    if (aPid[i] >= 0) {
                        A2B.push_back(aPid[i]);
                        aWorking[i] = 1;
                        aFinTime[i] = now + PA_T;
                        aPid[i] = -1;
                        timeline.push(now + PA_T);
                    }
                }
            }
            for (int i = 0; i < M; i++) {
                if (bWorking[i] && bFinTime[i] <= now) {
                    bWorking[i] = 0;
                    if (bPid[i] >= 0) {
                        bWorking[i] = 1;
                        bFinTime[i] = now + PB_T;
                        bPid[i] = -1;
                        timeline.push(now + PB_T);
                    }
                }
            }
            for (int i = 0; i < A2B.size(); i++) {
                int x = A2B[i];
                for (int j = 0; j < M; j++) {
                    if (bWorking[j] == 0) {
                        bWorking[j] = 1;
                        bFinTime[j] = PAB_T + now + D[x].pb;
                        bPid[j] = x, bUsed[j] += D[x].pb;
                        D[x].bid = j;
                        D[x].bBegin = now + PAB_T, D[x].bEnd = bFinTime[j];
                        timeline.push(bFinTime[j]);
                        break;
                    }
                }
            }
            for ( ; pid < K; pid++) {
                int ok = 0;
                for (int i = 0; i < N; i++) {
                    if (aWorking[i] == 0) {
                        aWorking[i] = 1;
                        aFinTime[i] = now + D[pid].pa;
                        aPid[i] = pid, aUsed[i] += D[pid].pa;
                        D[pid].aid = i;
                        D[pid].aBegin = now, D[pid].aEnd = aFinTime[i];
                        timeline.push(aFinTime[i]);
                        ok = 1;
                        break;
                    }
                }
                if (!ok)
                    break;
            }
        }
        
        int ST = 0x3f3f3f3f, ED = 0;
        puts(" Patient          Operating Room          Recovery Room");
        puts(" #  Name     Room#  Begin   End      Bed#  Begin    End");
        puts(" ------------------------------------------------------");
        for (int i = 0; i < K; i++) {
            printf("%2d  %-9s %2d  %3d:%02d  %3d:%02d    %3d  %3d:%02d  %3d:%02d\n",
                   i+1, D[i].name.c_str(), D[i].aid+1,
                   D[i].aBegin/60, D[i].aBegin%60, D[i].aEnd/60, D[i].aEnd%60, D[i].bid+1,
                   D[i].bBegin/60, D[i].bBegin%60, D[i].bEnd/60, D[i].bEnd%60);
            ST = min(ST, D[i].aBegin);
            ED = max(ED, D[i].bEnd);
        }
        puts("");
        puts("Facility Utilization");
        puts("Type  # Minutes  % Used");
        puts("-------------------------");
        for (int i = 0; i < N; i++) {
            printf("%-4s %2d %7d %7.2lf\n", "Room", i+1, aUsed[i], (double) aUsed[i]*100/(ED - ST));
        }
        for (int i = 0; i < M; i++) {
            printf("%-4s %2d %7d %7.2lf\n", "Bed", i+1, bUsed[i], (double) bUsed[i]*100/(ED - ST));
        }
        puts("");
    }
    return 0;
}
/*
 
 */
Read More +
解題區►解題區 - UVa

UVa 210 - Concurrency Simulator

Problem

模擬 CPU 排程，並且每種指令的所需時間都不同。一個程式可以使用 quantum 的時間，最多負一次執行某個指令 (quantum > 0 變成 quantum <= 0 的情況)。而當 unlock 只將一個程式從 block queue 吐出，而非所有程序。

保證每一個程序都會有一對 lock/unlock。

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
1
3 1 1 1 1 1 1
a = 4
print a
lock
b = 9
print b
unlock
print b
end
a = 3
print a
lock
b = 8
print b 
unlock
print b
end
b = 5
a = 17
print a
print b
lock
b = 21
print b
unlock
print b
end

Sample Output

1
2
3
4
5
6
7
8
9
10
1: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21

Solution

作業系統排程 lock & unlock 模擬，去年某一天心血來潮寫，卻狂 WA。現在回過頭才發現對 quantum 的使用錯誤，在有限時間內，即使在有剩餘時間下，執行下一條單位操作，直到沒有剩餘時間，我卻用加法限制於 quantum 下，導致炸掉。

題目中 “When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue”，為什麼只有一個 blocked queue 元素彈出，雖然在效率考量上是這樣，誤看成全部彈出，怪不得會一直 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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <list>
#include <sstream>
using namespace std;
#define MAXN 1024
#define MAXM 32
#define MAXVAR 26
struct Memory {
    char s[MAXM][MAXM];
    int counter;
    void read() {
        int n = 0;
        while (gets(s[n])) {
            if (s[n][0] == 'e' && s[n][1] == 'n' && s[n][2] == 'd')
                return;
            n++;
        }
    }
} mem[MAXN];
int N, unitTime[5], quantum, locked, var[MAXVAR];
deque<int> readyQ, blockQ;
vector<string> decode(string s) {
    vector<string> ret;
    stringstream sin(s);
    while (sin >> s)
        ret.push_back(s);
    return ret;
}
int toInt(string s) {
    int ret;
    stringstream sin(s);
    sin >> ret;
    return ret;
}
void execute(int pid) {
    int q = quantum;
    while (q > 0) {
        vector<string> args = decode(mem[pid].s[mem[pid].counter]);
        if (args[0].length() == 1) {
            var[args[0][0] - 'a'] = toInt(args[2]);
            q -= unitTime[0];
        } else if (args[0] == "print") {
            printf("%d: %d\n", pid+1, var[args[1][0] - 'a']);
            q -= unitTime[1];
        } else if (args[0] == "lock") {
            if (locked) {
                blockQ.push_back(pid);
                return;
            }
            locked = 1;
            q -= unitTime[2];
        } else if (args[0] == "unlock") {
            locked = 0;
            if (!blockQ.empty()) {
                readyQ.push_front(blockQ.front());
                blockQ.pop_front();
            }
            q -= unitTime[3];
        } else if (args[0] == "end") {
            return ;
        }
        mem[pid].counter++;
    }
    readyQ.push_back(pid);
}
void run(int N) {
    for (int i = 0; i < N; i++)
        readyQ.push_back(i), mem[i].counter = 0;
    for (int i = 0; i < MAXVAR; i++)
        var[i] = 0;
    locked = 0;
    int pid;
    while (!readyQ.empty()) {
        pid = readyQ.front(), readyQ.pop_front();
        execute(pid);
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < 5; i++)
            scanf("%d", &unitTime[i]);
        scanf("%d", &quantum);
        while (getchar() != '\n');
        for (int i = 0; i < N; i++)
            mem[i].read();
        
        run(N);
        
        if (testcase)
            puts("");
    }
    return 0;
}
/*
 */
Read More +
解題區►解題區 - 其他題目

2015 Facebook Hacker Cup Round 1

起床才發現，Facebook Hacker Cup Round 2 比賽不是比 24 小時，翻譯機的小夥伴醒了嗎？在這樣的情況下，只好自主宣告放棄，看題一直失敗，整個心情都壞了。關於 Round 2，根本沒看懂題目，就這麼結束了。

［2015 Facebook Hacker Cup Round 1］

＊Homework (10 points)

數學老師給一份質數作業，要求找到 [A, B] 之間的正整數，有多少不同質因數個數恰好等於 K 個，例如 12 = 2^2 * 3，則 f(12) = 2。寫一個程式來快速完成它。

A, B 小於等於 1000 萬，而詢問組數不超過 100 組，預估就算 O(n) 窮舉，速度來說仍然可以在時間內完成。無聊可以使用線性篩法，快速得到某個數字 x 必含的其中一個質因數來加速，f(x) = f(y) + 1, x = y * z, z power of prime nubmer。而區間查找可以針對 K 分開成數組，進行二分搜索。這樣寫太拚，有六分鐘的時間，暴力一點也無仿。

＊Autocomplete (25 points)

手機輸入單詞，會自動補上正在輸入單字的後綴，現在要求依序輸入單字，至少要敲入幾個字母，才能將所有單字完成。這題有點奇怪，照理來說要給定一個字典，接著開始鍵入，但這題是根據之前輸入的單詞，如果前綴相同就不能自動完成，怎麼補完的一點都不科學。

這題用內建 set<string>，可以使用 iterator it = map.lower_bound(word), it--; 來找到最有可能的前綴單詞，一定得輸入最大共同前綴長 +1，如果不想用內建，可以帶入 Trie 來完成，保證單詞總長不超過 100 萬，在某些題目 Trie 的速度跟泛用性相當高。

＊Winning at Sports (25 points)

在比賽中，勝利情況分成有、無壓力兩種方案，無壓力的情況是過程中，最後獲勝者的分數恆大於另一方，有壓力的情況是過程中，在另一方達到終盤分數前，最後獲勝者的分數不得大於另一方。現在給定終盤分數，請問兩種方案的比賽過程分別有多少種。

Dynamic programming 狀態 dp[a][b] 表示分別得分 a, b 的方法數，每次轉移 dp[a+1][b] += dp[a][b], dp[a][b+1] += dp[a][b] 特別小心條件範圍，分別對兩種方案做一次迭代。

＊Corporate Gifting (40 points)

每名員工都有一位上司，保證是樹狀結構，每名員工將要買禮物送給上司，禮物的花費為 $1, $2, …, $n，每個人都不想送出 $x 後，又從下屬中得到 $x 的禮物，請問該公司買禮物的總花費最小值為何？

樹狀最小帶權著色問題，套入樹形 Dp 的思路，定義狀態 dp[u][2] 表示以節點 u 當作 subtree root 的最佳解，其中 u 買 $?1, $?2 的兩種花費最小方案。合併時，窮舉 root 購入的價格，結合子樹的最小花費，防止同色即可。根據官方題解，使用的是 dp[u][log n]，可想而知數學推導得到最大購入不超過 $(log n)，但實際運作，我並沒有這麼做，而是看子樹最大著色數為何，再根據最大著色數進行窮舉。

這一題看到 N=200000 就要有點警惕，一般電腦預設 stack 大小，遞迴深度最多撐到 10 萬，呈現鏈狀很容易造成 stackoverflow，其一解決方案是編譯器調參數，其二 bfs 後的拓墣排序。

Read More +
解題區►解題區 - 其他題目

2015 Facebook Hacker Cup 資格賽

［2015 Facebook Hacker Cup 資格賽］贖罪篇

windows 參賽，卡了一個 \r\n 問題，剛好有裝 git，使用以下指令做轉換

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt
  • Cooking the Books (15 points)

會計師要騙過稽查人員，可以把金融數值任意交換兩個位置上的數字，請問能交換得到的最大、最小值分別為何？並且數字不可起首為 0。

喵蛋，最簡單的這題 recover step 因 continue 指令而被忽略，窮舉兩個位置做交換，大部分可以看到寫法有 string compare, int compare，最方便是在字串下處理，接著看要轉數字或者直接用字典順序比較都行。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
	freopen("cooking_the_books.txt", "r", stdin);
	freopen("out.txt", "w+", stdout); 
	int testcase, cases = 0;
	char s[64];
	scanf("%d", &testcase);
	while (testcase--) {
		long long ret1, ret2, tmp;
		scanf("%s", s);
		sscanf(s, "%lld", &ret1);
		sscanf(s, "%lld", &ret2);
		int n = strlen(s);
		for (int i = 0; i < n; i++) {
			for (int j = i+1; j < n; j++) {
				swap(s[i], s[j]);
				sscanf(s, "%lld", &tmp);
				if (s[0] != '0') { 
					ret1 = min(ret1, tmp);
					ret2 = max(ret2, tmp);
				} 
				swap(s[i], s[j]);
			}
		}
		printf("Case #%d: %lld %lld", ++cases, ret1, ret2);
		putchar('\n');
	}
	return 0;
}
  • New Year’s Resolution (30 points)

新年新希望，目標均衡飲食，要求蛋白質、澱粉、脂肪攝取剛好的量，挑選 n 個食物，只有不選、或者是只能一樣走。求是否能辦到？

在 n 不大的時候，套用 bitmask 窮舉最為方便。用 Dfs 搜索當然喜聞樂見，如果 n 很大，而要求的量很小，則可以使用三維 dp[P][C][F] 狀態來解決。如果要求倍數關係，而數量無限的話，可以轉換成幾何分析。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
	freopen("new_years_resolution.txt", "r", stdin);
	freopen("out.txt", "w+", stdout); 
	int testcase, n, cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		int GP, GC, GF;
		int P[32], C[32], F[32];
		scanf("%d %d %d", &GP, &GC, &GF);
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d %d %d", &P[i], &C[i], &F[i]);
			
		int ret = 0;
		for (int i = (1<<n)-1; i >= 0 && !ret; i--) {
			int a = 0, b = 0, c = 0;
			for (int j = 0; j < n; j++) {
				if ((i>>j)&1) {
					a += P[j];
					b += C[j];
					c += F[j];
				}
			}
			ret |= a == GP && b == GC && c == GF;
		}
		printf("Case #%d: %s\n", ++cases, ret ? "yes" : "no");
	}
	return 0;
}
  • Laser Maze (55 points)

給予 2D 地圖，裡面的雷射裝置將會感應使用者的腳步，每踏一步則順時針換方向，並且發射出雷射，雷射只會因牆壁、雷射塔而被屏蔽，但是雷射跟雷射之間不會相消、折射。現在雷射裝置的起始方向各有不同，避開雷射，找最少步數抵達終點。(只能走上下左右四個方向，停留不能解決問題，雷射裝置因感測而行動。)

基礎的 Bfs，因為只有四個方向，根據時間做紀錄，每四次操作進行一個循環，則 int dist[time4][pos_x][pos_y]，考慮在哪一個 time mod 4 抵達某個位置。接下來麻煩的是檢查操作，檢查操作有兩種，其一，預處理每個時間下雷射發射，其二，從當前位置反搜索雷射光是否對著自己。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
char g[128][128];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dv[] = "<^>v";
int dist[4][128][128], n, m;
int valid(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < m;
}
char next(char c, int t) {
	static char v[] = "^>v<";
	for (int i = 0; i < 4; i++) {
		if (v[i] == c)
			return v[(i + t)%4];
	}
	assert(false);
}
int test(int t, int x, int y) {
	int tx, ty;
	for (int i = 0; i < 4; i++) {
		tx = x, ty = y;
		while (valid(tx, ty) && g[tx][ty] == '.')
			tx += dx[i], ty += dy[i];
		if (valid(tx, ty) && g[tx][ty] != '#') {
			char c = g[tx][ty];
			if (next(c, t) == dv[i])
				return 1;
//			printf("%c %c %d\n", next(g[tx][ty], t), dv[i], i);
		}
	}
	return 0;
}
void bfs() {
	memset(dist, 0, sizeof(dist));
	int sx, sy, ex, ey;
	int x, y, tx, ty, t;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (g[i][j] == 'S')
				sx = i, sy = j, g[i][j] = '.';
			if (g[i][j] == 'G')
				ex = i, ey = j, g[i][j] = '.';
		}
	}
	dist[0][sx][sy] = 1;
	queue<int> X, Y, T;
	X.push(sx), Y.push(sy), T.push(0);
	while (!X.empty()) {
		x = X.front(), X.pop();
		y = Y.front(), Y.pop();
		t = T.front(), T.pop();
		int d = dist[t][x][y] + 1;
		if (x == ex && y == ey) {
			printf("%d\n", d - 2);
			return;
		}
		for (int i = 0; i < 4; i++) {
			tx = x + dx[i], ty = y + dy[i];
			if (!valid(tx, ty))
				continue;
			if (g[tx][ty] != '.')
				continue;
			if (test((t+1)%4, tx, ty))
				continue;
			if (dist[(t+1)%4][tx][ty] == 0) {
				dist[(t+1)%4][tx][ty] = d;
				X.push(tx), Y.push(ty), T.push((t+1)%4);
			}
		}
	}
	puts("impossible");
}
int main() {
	freopen("laser_maze.txt", "r", stdin);
	freopen("out.txt", "w+", stdout);
	int testcase, cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++)
			scanf("%s", &g[i]);
		printf("Case #%d: ", ++cases);
		bfs();
	}
	return 0;
}
/*
999
2 5
##^##
S...G
2 6
###<##
S....G
2 5
##v##
S...G
1 5
S..G<
1 6
S...G<
5 5
S....
.....
.>v..
.^<..
....G
*/
Read More +
解題區►解題區 - UVa

UVa 11186 - Circum Triangle

Problem

半徑為 R 的圓上有 N 個點，請問任挑三點形成的三角形面積總和為多少。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 10
10.00
100.00
300.00
310.00
320.00
3 20
10.00
100.00
300.00
0 0

Sample Output

1
2
286
320

Solution

因此總共有 C(N, 3) 的三角形，聽說直接窮舉三點計算三角形面積就可以過，時間複雜度是 O(n^3)。事實上可以換個方式想，計算三角形面積，相當於用一個圓減去三個弓形面積。

那麼實際上會有 C(N, 3) 個圓減去一堆弓形面積。關於所有弓形面積的計算，可以窮舉兩點拉一條邊作為弦，接著會有兩個弓形，分別找到左右兩側的點數，就能知道有多少三角形分別使用多少次這些弓形面積，加總之後就是總共的弓形面積，複雜度降至 O(n^2)。

事實上還可以再更數學點，但是不太會推導，最後貌似可以在 O(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
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const double pi = acos(-1);
int main() {
	int N;
	double R, theta[512];
	while (scanf("%d %lf", &N, &R) == 2 && N) {
		for (int i = 0; i < N; i++) {
			scanf("%lf", &theta[i]);
			theta[i] = theta[i] * pi / 180;
		}
		sort(theta, theta+N);
		double ret = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i+1; j < N; j++) {
				int a = j - i - 1;
				int b = N - a - 2;
				double A, B, t = theta[j] - theta[i];
				A = t /2 * R * R - R * R * sin(t)/2;
				B = R * R * pi - A;
				ret += a * B + b * A;
//				printf("[%lf %lf] %lf %lf\n", theta[i], theta[j], A, B);
			}
		}
		ret = (double)(N) * (N-1) * (N-2) / 6 * R * R * pi - ret;
		if (N < 3)	ret = 0;
		printf("%.0lf\n", ret);
	}
	return 0;
}
/*
5 10
10.00
100.00
300.00
310.00
320.00
3 20
10.00
100.00
300.00
0 0
*/
Read More +
解題區►解題區 - UVa

UVa 904 - Overlapping Air Traffic Control Zones

Problem

每一個飛機的安全範圍視為在三維空間平行三軸的六面體，給定 n 台飛機的安全範圍，請問重疊至少兩次的空間體積為何？

Sample Input

1
2
3
4
5
6
5
1 1 1 3 3 3
1 1 1 3 3 3
1 1 1 3 3 3
400000000 400000000 400000000 400000001 400000001 400000002
400000000 400000000 400000000 400000002 400000004 400000001

Sample Output

1
9

Solution

離散化 X Y Z 軸出現的座標值，壓縮成 n * n * 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
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <map>
using namespace std;
#define MAXN 32
void mapRelabel(map<int, int> &R, int val[]) {
	int size = 0;
	for (map<int, int>::iterator it = R.begin();
		it != R.end(); it++) {
		val[size] = it->first;
		it->second = size++;
	}
}
int main() {
	int n;
	int lx[MAXN], ly[MAXN], lz[MAXN];
	int rx[MAXN], ry[MAXN], rz[MAXN];
	int xval[MAXN], yval[MAXN], zval[MAXN];
	while (scanf("%d", &n) == 1) {
		map<int, int> RX, RY, RZ;
		for (int i = 0; i < n; i++) {
			scanf("%d %d %d", &lx[i], &ly[i], &lz[i]);
			scanf("%d %d %d", &rx[i], &ry[i], &rz[i]);
			RX[lx[i]] = RX[rx[i]] = 1;
			RY[ly[i]] = RY[ry[i]] = 1;
			RZ[lz[i]] = RZ[rz[i]] = 1;
		} 
		mapRelabel(RX, xval);
		mapRelabel(RY, yval);
		mapRelabel(RZ, zval);
		
		int a = RX.size(), b = RY.size(), c = RZ.size();
		int sx, ex, sy, ey, sz, ez;
		int cnt[MAXN][MAXN][MAXN] = {};
		for (int i = 0; i < n; i++) {
			sx = RX[lx[i]], ex = RX[rx[i]];
			sy = RY[ly[i]], ey = RY[ry[i]];
			sz = RZ[lz[i]], ez = RZ[rz[i]];
			for (int p = sx; p < ex; p++) {
				for (int q = sy; q < ey; q++) {
					for (int r = sz; r < ez; r++) {
						cnt[p][q][r]++;
					}
				}
			}
		}
		
		int ret = 0;
		for (int i = 0; i < a; i++) {
			for (int j = 0; j < b; j++) {
				for (int k = 0; k < c; k++) {
					if (cnt[i][j][k] >= 2) {
						ret += (xval[i+1] - xval[i]) * (yval[j+1] - yval[j]) * (zval[k+1] - zval[k]);
					}
				}
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 10729 - Treequivalence

Problem

給一個平面圖的樹，請問是否同構，每一個節點相鄰的邊將會按照逆時針的順序給定。

Sample Input

1
2
3
4
5
2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))

Sample Output

1
2
different
same

Solution

這一題與 UVa 12489 - Combating cancer 有點不同，這一題限制在平面圖，因此邊的紀錄是有順序性的。而題目不僅要求結構相同，同時在節點上面的 label 也要相同。

但是只要固定一個當作根，成為一個有根樹，那麼在最小表示法中，除了根的分支可以旋轉外，其餘的節點的分支都不能旋轉。因此固定其中一棵樹的根節點，接著窮舉另外一棵樹哪個節點作為根節點，分別找到最小表示法進行比對即可。

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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
// special !!!!!!!! normal planar representation
class Tree {
	public:
	vector<int> g[10005];
	char label[10005];
	int n;
	map<vector<int>, int> tmpR;
	int dfsMinExp(int u, int p) {
		vector<int>	branch;
		for(int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if(v == p)	continue;
			branch.push_back(dfsMinExp(v, u));
		}
		sort(branch.begin(), branch.end());
	
		int a = 63689, b = 378551;
		int ret = 0;
		branch.push_back(label[u]);
		for(int i = 0; i < branch.size(); i++)
			ret = ret * a + branch[i], a *= b;
		return ret;
	}
	vector<int> getTreeMinExp() { // simple (no plane)
		if(n == 1)	return vector<int>(1, (int)label[1]);
		int deg[10005] = {}, u, v;
		int topo[10005] = {}, idx = 0;
		queue<int> Q;
		for(int i = 1; i <= n; i++) {
			deg[i] = g[i].size();
			if(deg[i] == 1)	Q.push(i);
		}
		while(!Q.empty()) {
			u = Q.front(), Q.pop();
			topo[idx++] = u;
			for(int i = 0; i < g[u].size(); i++) {
				v = g[u][i];
				if(--deg[v] == 1)
					Q.push(v);
			}
		}
		vector<int> ret;
		ret.push_back(dfsMinExp(topo[idx-1], -1));
		ret.push_back(dfsMinExp(topo[idx-2], -1));
		return ret;
	}
	
	int dfsCheck(Tree& tree, int u, int p) {
		vector<int> branch;
		if (p < 0) { // root
			for (int i = 0; i < tree.g[u].size(); i++) {
				int v = tree.g[u][i];
				branch.push_back(dfsCheck(tree, v, u));
			}
			
			int idx = 0, bn = branch.size();
			for (int s = 1; s < bn; s++) { // find cycle minExp
				for (int i = idx, j = s, k = 0; k < bn; k++) {
					if (branch[i] != branch[j]) {
						if (branch[j] < branch[i])	idx = s;
						break;
					}
					if (++i >= bn)	i = 0;
					if (++j >= bn)	j = 0;
				}
			}
			rotate(branch.begin(), branch.begin() + idx, branch.end());
		} else {
			int idx;
			for (idx = 0; tree.g[u][idx] != p; idx++);
			
			while (true) {
				idx++;
				if (idx >= tree.g[u].size())
					idx = 0;
				int v = tree.g[u][idx];
				if (v == p)	break;
				branch.push_back(dfsCheck(tree, v, u));
			}
		}
		branch.push_back(-tree.label[u]);
		int &ret = tmpR[branch];
		if (ret == 0)	ret = tmpR.size();
		return ret;
	}
	int equal(Tree &other) { // normal planar representation
		if (n != other.n)	return 0;
		tmpR.clear();
		int b = dfsCheck(other, 1, -1);
		for (int i = 1; i <= n; i++) {
			int a = dfsCheck(*this, i, -1);
			if (a == b)
				return 1;
		}
		return 0;
	}
	void init(int N) { 
		for (int i = 0; i <= N; i++)
			g[i].clear();
		n = 0;
	} 
	int read(int p) {
		int x = ++n;
		char c;
		if (p >= 0)	g[x].push_back(p);
		scanf(" %c%c", &label[x], &c);
		if (c != '(') {
			ungetc(c, stdin);
			return x;
		}
		do {
			g[x].push_back(read(x));
			if (scanf("%c", &c) != 1 || c != ',')
				break;
		} while (true);
		return x;
	}
} tree1, tree2;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		tree1.init(256); tree2.init(256);
		tree1.read(-1); tree2.read(-1);
		int same = tree1.equal(tree2);
		puts(same ? "same" : "different");
	}
	return 0;
}
/*
2
A(B(C,D),E)
E(A,B(C,D))
A(B(C,D),E)
E(A(B(C,D)))
9999
S(Y(Y(O),U(N(S,E,R(D)))))
D(R(N(U(Y(Y(O),S)),S,E)))
*/
Read More +