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

UVa 10335 - Ray Inside a Polygon

Problem

給一個凸多邊形，接著再給定一射線的起始位置和角度，請問經過 m 次反射後的位置為何？如果射線打入凸多邊形的端點時，視如射線遺失。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4 4
2.00 0.00 0.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 0
2.00 0.00 45.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
0 0

Sample Output

1
2
lost forever...
4.00 2.00

Solution

模擬每一步的射線可能打入的凸邊形的邊，因此每一次反射將要窮舉所有邊，查看是否存在線段與射線相交，如果發現此一可能再找到下一個反射線的起點與方向向量。

找到反射線的起點很簡單，直接用線段交即可找到，問題是在於方向向量怎麼計算，如果是用角度旋轉會造成嚴重的誤差。因此先把射線起點投影到線段上，接著再打到對稱點，然後從對稱點拉到交點得到方向向量，這麼做會降低嚴重的誤差問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
// I hate it, more eps adjust. 
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-8
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 {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &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;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
int same(Pt a, Pt b) {
    return fabs(a.x - b.x) < 0.005 && fabs(a.y - b.y) < 0.005;
}
int main() {
    Pt p[32];
    double theta;
    int n, m;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        Pt S, lvec;
        S.read();
        scanf("%lf", &theta);
        theta = theta * pi / 180;
        lvec = Pt(cos(theta), sin(theta));
        for (int i = 0; i < n; i++) // anti-clockwise
            p[i].read();
        
        int lost = 0;
        Seg on;
        for (int i = 0, j = n-1; i < n; j = i++) {
            Seg b(p[j], p[i]);
            if (onSeg(b.s, b.e, S))
                on = b;
        }
        for (int it = 0; it <= m; it++) { // #reflect.
            Seg pick = on, a(S, S + lvec);
            for (int i = 0, j = n-1; i < n; j = i++) {
                Seg b(p[j], p[i]);
                if (cmpZero(cross(a.s, a.e, b.s)) * cmpZero(cross(a.s, a.e, b.e)) <= 0) {
                    if (b != pick) {
                        pick = b;
                        break;
                    }
                }
            }
            Pt poj = getIntersect(pick, Seg(S, S + Pt(pick.s.y - pick.e.y, pick.e.x - pick.s.x)));
            Pt sym = S + (poj - S) * 2;
            S = getIntersect(a, pick);	
            lvec = S - sym;			
//			printf("%lf %lf %lf %lf\n", pick.s.x, pick.s.y, pick.e.x, pick.e.y);
//			printf("%lf %lf\n", S.x, S.y);
            if (same(S, pick.s) || same(S, pick.e)) {
                lost = 1;
                break;
            }
//			double r;
//			if (dot(pick.e - pick.s, lvec) <= 0)
//				r = getAngle(lvec, pick.e - pick.s);
//			else
//				r = getAngle(lvec, pick.s - pick.e);
//			lvec = rotateRadian(lvec, 2 * r);
            on = pick;
//			printf("it %d: %lf %lf\n", it, S.x, S.y);
//			printf("%lf %lf %lf %lf\n", lvec.x, lvec.y, poj.x, poj.y);
        }
        if (lost)
            puts("lost forever...");
        else {
            if (fabs(S.x) < eps && S.x < 0)
                S.x = - S.x;
            if (fabs(S.y) < eps && S.y < 0)
                S.x = - S.y;
            printf("%.2lf %.2lf\n", S.x, S.y);
        }
    }
    return 0;
}
/*
4 4
2.00 0.00 0.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 0
2.00 0.00 45.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
3 501
10.99 109 0
10 10
11 110
11 10
3 0
1 0 91
0 0
5 5
5 0
3 1
1 0 91
0 0
5 5
5 0
3 2
1 0 91
0 0
5 5
5 0
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 12684 - VivoParc

Problem

動物園的 4 種動物配置，動物都有地域性，不希望相鄰的地方會具有與自己相同的物種。

給一個 graph，最多用四個顏色著色，使得相鄰不同色，輸出任意種方案即可。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
8
1-2
3-1
4-5
4-8
1-7
1-4
7-1
2-4
1-8
6-7
2-3
1-5
1-6
7-6
7-8
2-5
7-1
3-4
5-6
7-8

Sample Output

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

Solution

看起來 N 還算大，窮舉順序會稍微影響速度，依序窮舉節點，檢查是否存在相鄰同色。由於不曉得是不是只有一個連通元件，連通元件分開找解，防止浪費時間的搜索。

接著根據 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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[128];
int visited[128];
int A[128], An, color[128];
int used[128];
int dfs(int idx) {
    if (idx == An)
        return 1;
    for (int c = (idx == 0 ? 4 : 1); c <= 4; c++) {
        int u = A[idx], v, ok = 1;
        for (int i = 0; i < g[u].size() && ok; i++) {
            v = g[u][i];
            if (used[v] && color[v] == c)
                ok = 0;
        }
        if (ok) {
            used[u] = 1;
            color[u] = c;
            if (dfs(idx+1))
                return 1;
            used[u] = 0;
        }
    }
    return 0;
}
void bfs(int st) {
    queue<int> Q;
    int u;
    An = 0;
    Q.push(st), visited[st] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        A[An++] = u;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (visited[v] == 0) {
                visited[v] = 1;
                Q.push(v);
            }
        }
    }
    memset(used, 0, sizeof(used));
    dfs(0);
}
int main() {
    char line[128];
    int x, y, n, cases = 0;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n'); 
        for (int i = 0; i <= n; i++)
            g[i].clear();
        while (gets(line)) {
            if (line[0] == '\0')
                break;
            sscanf(line, "%d-%d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for (int i = 1; i <= n; i++) {
            sort(g[i].begin(), g[i].end());
            g[i].resize(distance(g[i].begin(), unique(g[i].begin(), g[i].end())));
        }
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                bfs(i);
            }
        }
        if (cases++)	puts("");
        for (int i = 1; i <= n; i++)
            printf("%d %d\n", i, color[i]);
    }
    return 0;
}
/*
8
1-2
3-1
4-5
4-8
1-7
1-4
7-1
2-4
1-8
6-7
2-3
1-5
1-6
7-6
7-8
2-5
7-1
3-4
5-6
7-8
*/
Read More +
解題區/解題區 - UVa

UVA 12763 - Dicey Dice

Problem

有兩個玩家 A, B，盤面上有三個骰子，先手先挑一個骰子出來，後手再從剩餘兩個骰子中挑一個。接著兩個人會分別骰出點數，骰出最大的那個玩家獲勝，如果骰出一樣點數則平手

給予先手玩家，和三個六面骰子，請問獲勝機率高的玩家為何？

Sample Input

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

Sample Output

1
2
3
A
B
fair

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    char s[10];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int player = s[0] - 'A';
        int dice[3][6];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 6; j++) {
                scanf("%d", &dice[i][j]);
            }
        }
        double rmx = 0, rmx2 = 1;
        for (int i = 0; i < 3; i++) { // A player pick
            double mx = 1, mx2 = 0;
            for (int j = 0; j < 3; j++) { // B player pick
                if (i == j)	continue;
                int pa = 0, pb = 0;
                for (int p = 0; p < 6; p++) {
                    for (int q = 0; q < 6; q++) {
                        pa += dice[i][p] > dice[j][q];
                        pb += dice[i][p] < dice[j][q];
                    }
                }
                
                if (mx > pa / 36.0 || (mx == pa / 36.0 && mx2 < pb/36.0)) {
                    mx = pa /36.0;
                    mx2 = pb / 36.0;
                }
            }
            if (rmx < mx || (rmx == mx && rmx2 > mx2)) {
                rmx = mx;
                rmx2 = mx2;
            }
        }
        if (rmx > rmx2)
            printf("%c\n", player + 'A');
        else if (rmx < rmx2)
            printf("%c\n", 1 - player + 'A');
        else
            printf("fair\n");
//			printf("%lf %lf\n", rmx, rmx2);
    }
    return 0;
}
/*
3
A
1 1 1 1 1 1
2 3 2 4 5 3
6 6 6 6 6 6
A
4 3 7 9 2 5
8 1 4 6 9 2
6 5 1 8 3 7
B
1 2 3 4 4 4
1 2 3 4 4 4
1 2 3 4 4 4
*/
Read More +