Problem

You are given an integer sequence of length N and another value X. You have to find a contiguous subsequence of the given sequence such that the sum is greater or equal to
X. And you have to find that segment with minimal length.

Sample Input

1
2
3
4
5
6
7

3
5 4
1 2 1 2 1
6 -2
-5 -6 -7 -8 -9 -10
5 3
-1 1 1 1 -1

Sample Output

1
2
3

3
-1
3

Solution

題目描述：

找一段長度最小，且該區間總和大於等於指定 X。

題目解法：

離散化後，利用掃描線的思路進行維護。

利用前綴和 SUM[i]，查找小於等於 SUM[i] - X 的最大值。

隨後更新 SUM[i] 位置的值 i。

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

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
#define MAXN 5024288
#define INF 0x3f3f3f3f
long long A[MAXN], SM[MAXN], SB[MAXN];
// binary index tree
int BIT[MAXN<<1];
void modify(int x, int v, int L) {
    while(x <= L) {
        BIT[x] = max(BIT[x], v);
        x += x&(-x);
    }
}
int query(int x) {
    int ret = - INF;
    while(x) {
        ret = max(ret, BIT[x]);
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int testcase, N, X;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &N, &X);
        for(int i = 1; i <= N; i++)
            scanf("%lld", A+i);
        
        for(int i = 1; i <= N; i++)
            SM[i] = SM[i-1] + A[i];
        for(int i = 0; i <= N; i++)
            SB[i] = SM[i];
        for(int i = 1; i <= N + 1; i++)
            BIT[i] = - INF;
        sort(SB, SB + N + 1);
        int M = unique(SB, SB + N + 1) - SB;		
        int ret = INF;
        for(int i = 0; i <= N; i++) {
            long long v = SM[i] - X;
            int pos = upper_bound(SB, SB + M, v) - SB;
            if(pos - 1 >= 0 && i)  {
                ret = min(ret, i - query(pos));
//				printf("query %d\n", i - query(pos));
            }
            pos = upper_bound(SB, SB + M, SM[i]) - SB;
            modify(pos, i, M);
//			printf("%lld %d\n", v, pos);
        }
        
        printf("%d\n", ret == INF ? -1 : ret);
    }
    return 0;
}
/*
3
5 4
1 2 1 2 1
6 -2
-5 -6 -7 -8 -9 -10
5 3
-1 1 1 1 -1
*/

Problem

The Swamp County Environmental Office is concerned about the number of structures in the county. They have a theory that all the rain water landing on roofs of buildings, parking lots, roads, and highways is going down the sewage system instead of draining to the ecologically sensitive and historically important swamp land the county is famous for.

Your team has been hired to do the analysis of rain water captured by building roofs. The Planning Commission, which processes all building permits, and hence knows the plans of every structure in the county, will provide the data. Their database contains a set of measurements for the roofs of every building on every lot in the county.

The Engineering staff of the Planning Commission has determined that all the roofs in the county can be represented by one or more quadrilaterals. Each quadrilateral has the following characteristics:

length of baseline, in feet;
length of ridgeline, in feet;
distance between baseline and ridgeline, in feet;
and inclination of the roof segment, in degrees. 

The baseline is always parallel to the ridgeline. A roof segment is always flat, but may be inclined. The inclination of the segment occurs along the baseline or ridgeline axis. A roof segment that is inclined 90 degrees is a wall that is assumed to have negligible thickness, and hence gathers no rain–such a segment will not appear in the data. Assume that the buildings are on level land, and that no roof segment overlaps any other. A roof segment may have either a baseline or ridgeline length of zero (such a segment is actually a triangle). A lot may contain one or more buildings, but your program need only compute the area covered by roofs on a lot-by-lot basis.

Input

Each lot is represented by a series of numbers separated from each other by white space and/or new-lines. The lot size, in square feet, is followed by a list of roof segments. Each roof segment will consist of the length of the baseline, the length of the ridgeline, the distance between the baseline and the ridgeline, and the inclination. Each lot description including the last will end with a blank line.

Output

For each lot compute and print the following statistics: the total roof surface area of buildings in square feet, the total floor space covered by roofs in square feet, and the percentage of rain intercepted by roofs. Print these values in labeled columns, one lot per line, with two digits after the decimal point. Print percent signs after the percentage of rain figures.

At the end of the run compute and print the following statistics: the total roof surface area of all roofs in the county, the total floor space covered by roofs in the county, the overall percentage of rain intercepted by roofs, the average roof surface area on a lot, and the average floor space covered by roofs on a lot. Skip a line after the per-lot listing and print these values on separate lines with appropriate labels.

Print each value with two digits after the decimal point. Print a percent sign after the overall percentage of rain value. Use a report format similar to that of the sample output below.

One of the reasons Swamp County has remained so is the relative lack of wind in the county–you may therefore assume that all rain falls vertically.

Sample Input

1
2
3
4

100 10 10 10 60
10 10 10 60
200 5 10.5 5 30  10 10 7.5 45

Sample Output

1
2
3
4
5
6
7
8
9
10

Roof Area     Floor Area     % Covered
---------     ----------     ---------
   200.00         100.00       100.00%
   113.75          86.59        43.30%
 
Total surface area of roofs      313.75
Total area covered by roofs      186.59
Percentage of total area covered by roofs   62.20%
Average roof surface area per lot          156.88
Average floor space covered per lot         93.30

Solution

題目描述：

屋頂為一個三維空間的平面，假想成梯形也可以，頃角就是單純地將梯形與平面 x-y 夾角 theta。

分別算出梯形面積和陰影面積。

題目解法：

最坑的就是輸入，其實看了很久都沒有明白到底是怎麼區隔每一組。
查閱了討論區給的測資才湊出 AC 代碼。

想辦法讀到每一組測資是 4n + 1 個數字，否則繼續將空白行讀入。

brianfry713’s Input:

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

100 10 10 10 60
10 10 10 60
200 5 10.5 5 30  10 10 7.5 45
100
10 10 10
60 10
10 10 60
200 5 10.5 5 30  10 10 7.5 45
100 0 10 7.5 45 10
0 7.5 -135
300

brianfry713’s Output:

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

Roof Area     Floor Area     % Covered
---------     ----------     ---------
   200.00         100.00       100.00%
   113.75          86.59        43.30%
     0.00           0.00         0.00%
   600.00         590.88      5908.85%
  7701.25        7133.96     71339.57%
     0.00           0.00         0.00%
Total surface area of roofs     8615.00
Total area covered by roofs     7911.43
Percentage of total area covered by roofs 1098.81%
Average roof surface area per lot         1435.83
Average floor space covered per lot       1318.57

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

#include <stdio.h>
#include <sstream>
#include <iostream>
#include <math.h>
using namespace std;
const double pi = acos(-1);
double A, B, C, N;
char* getLot() {
    char line[1024], *v;
    string ret = "", token;
    int tokenCnt = 0;
    while(tokenCnt%4 != 1) {
        while((v = gets(line)) && line[0] != '\0') {
            ret += " ", ret += line;
            stringstream ss(line);
            while(ss >> token)
                tokenCnt++;
        }
        if(!v)
            return v;
    }
    stringstream sin(ret);
    double lotsize, baseline, ridgeline, dist, theta;
    double a = 0, b = 0;
    sin >> lotsize;
    while(sin >> baseline >> ridgeline >> dist >> theta) {
        a += (baseline + ridgeline) * dist/2.0;
        b += (baseline + ridgeline) * dist/2.0 * cos(theta / 180.0 * pi);	
    }
    printf("%9.2lf     %10.2lf     %8.2lf%%\n", a, b, b * 100 /lotsize);
    A += a, B += b, C += lotsize, N++;
    return v;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    
    puts("Roof Area     Floor Area     % Covered");
    puts("---------     ----------     ---------");
    char line[1024];
    while(true) {
        if(getLot()) {
        } else {
            break;
        }
    }
    puts("");
    printf("Total surface area of roofs  %10.2lf\n", A);
    printf("Total area covered by roofs  %10.2lf\n", B);
    printf("Percentage of total area covered by roofs  %6.2lf%%\n", B*100/C);
    printf("Average roof surface area per lot      %10.2lf\n", A/N);
    printf("Average floor space covered per lot    %10.2lf\n", B/N);
    return 0;
}

Problem

The word the is the most common three-letter word. It even shows up inside other words, such as “other” and “mathematics”. Sometimes it hides, split between two words, such as “not here”. Have you ever wondered what the most common words of lengths other than three are?

Your task is the following. You will be given a text. In this text, find the most common word of length one. If there are multiple such words, any one will do. Then count how many times this most common word appears in the text. If it appears more than once, output how many times it appears. Then repeat the process with words of length 2, 3, and so on, until you reach such a length that there is no longer any repeated word of that length in the text.

Input Specification

The input consists of a sequence of lines. The last line of input is empty and should not be processed. Each line of input other than the last contains at least one but no more than one thousand uppercase letters and spaces. The spaces are irrelevant and should be ignored.

Sample Input

1
2

THE OTHER MATHEMATICS NOT HERE
AA

Note that the last line of the sample input is a blank line.

Output Specification

For each line of input, output a sequence of lines, giving the number of repetitions of words of length 1, 2, 3, and so on. When you reach a length such that there are no repeated words of that length, output one blank line, do not output anything further for that input line, and move on to the next line of input.

Output for Sample Input

1
2
3
4
5
6
7

5
4
4
2
2
2

Solution

題目描述：

依序將長度為 1, 2, 3, 4 … 其重複出現次數最高的字串次數輸出，只考慮重複次數大於 1 的所有情況。

題目解法：

由於題目只查看大寫字母，忽略空白不計，若存在有空白的行時特別處理，否則在隨後的 trim() 會有輸出錯誤。

直接套上 Suffix Array，使用 Double algorithm 建造法，並且建出高度數組。

建造在 O(n log n)，但是輸出處理最慘會到 O(n^2)。

在其他的做法中，可以看到有人使用 hash function 進行比較 (將每一組單詞丟到同一個欄中，之後在進行比較)，這也是個挺不錯的做法，但是風險還是存在。

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 <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct SuffixArray {
    int sa[1005], h[1005], n;
    int w[1005], ta[1005], tb[1005];
    char str[1005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
int main() {
    SuffixArray in;
    while(gets(in.str) && in.str[0] != '\0') {
    	int n = 0;
    	for(int i = 0; in.str[i]; i++)
    		if(in.str[i] != ' ')
    			in.str[n++] = in.str[i];
    	in.str[n] = '\0';
    	
        in.build();
        in.build_h();
        
        if(n == 0)
        	puts("0");
        for(int i = 1; i <= in.n; i++) {
        	int cnt = 0, ret = 0;
        	for(int j = 0; j < in.n; j++) {
        		if(in.h[j] >= i)
        			cnt++;
        		else
        			ret = max(ret, cnt), cnt = 0;
        	}
        	ret = max(ret, cnt);
        	if(ret <= 0)
        		break;
        	printf("%d\n", ret + 1);
        }
        puts("");
    }
    return 0;
}

Problem

The Transferable Vote system for determining the winner of an election requires that a successful candidate obtain an absolute majority of the votes cast, even when there are more than two candidates. To achieve this goal, each voter completes his or her ballot by listing all the candidates in order of preference. Thus if there are five candidates for a single position, each voter’s ballot must contain five choices, from first choice to fifth choice.

In this problem you are to determine the winner, if any, of elections using the Transferable Vote system. If there are c candidates for the single position, then each voter’s ballot will include c distinct choices, corresponding to identifying the voter’s first place, second place, tex2html_wrap_inline32 , and nth place selections. Invalid ballots will be discarded, but their presence will be noted. A ballot is invalid if a voter’s choices are not distinct (choosing the same candidate as first and second choice isn’t permitted) or if any of the choices aren’t legal (that is, in the range 1 to c).

For each election candidates will be assigned sequential numbers starting with 1. The maximum number of voters in this problem will be 100, and the maximum number of candidates will be 5.

            Table A                 Table B
-------------------------------    --------- 
Voter    First   Second  Third
         Choice  Choice  Choice
  1        1       2       4
  2        1       3       2       1   3   2
  3        3       2       1       3   2   1
  4        3       2       1       3   2   1
  5        1       2       3       1   2   3
  6        2       3       1       3   1
  7        3       2       1       3   2   1
  8        3       1       1
  9        3       2       1       3   2   1
 10        1       2       3       1   2   3
 11        1       3       2       1   3   2
 12        2       3       1       3   1

Consider a very small election. In Table A are the votes from the 12 voters for the three candidates. Voters 1 and 8 cast invalid ballots; they will not be counted. This leaves 10 valid ballots, so a winning candidate will require at least 6 votes (the least integer value greater than half the number of valid ballots) to win. Candidates 1 and 3 each have 4 first choice votes, and candidate 2 has two. There is no majority, so the candidate with the fewest first choice votes, candidate 2, is eliminated. If there had been several candidates with the fewest first choice votes, any of them, selected at random, could be selected for elimination.

With candidate 2 eliminated, we advance the second and third choice candidates from those voters who voted for candidate 2 as their first choice. The result of this action is shown in Table B. Now candidate 3 has picked up 2 additional votes, giving a total of 6. This is sufficient for election. Note that if voter 12 had cast the ballot 2 1 3 then there would have been a tie between candidates 1 and 3.

Input

There will be one or more elections to consider. Each will begin with a line containing the number of candidates and the number of voters, c and n. Data for the last election will be followed by a line containing two zeroes.

Following the first line for each election will be n additional lines each containing the choices from a single ballot. Each line will contain only c non-negative integers separated by whitespace.

Output

For each election, print a line identifying the election number (they are numbered sequentially starting with 1). If there were any invalid ballots, print an additional line specifying the number of such. Finally, print a line indicating the winner of the election, if any, or indication of a tie; be certain to identify the candidates who are tied. Look at the samples below for the exact output format.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

3 12
1 2 4
1 3 2
3 2 1
3 2 1
1 2 3
2 3 1
3 2 1
3 1 1
3 2 1
1 2 3
1 3 2
2 3 1
3 12
1 2 4
1 3 2
3 2 1
3 2 1
1 2 3
2 3 1
3 2 1
3 1 1
3 2 1
1 2 3
1 3 2
2 1 3
4 15
4 3 1 2
4 1 2 3
3 1 4 2
1 3 2 4
4 1 2 3
3 4 2 1
2 4 3 1
3 2 1 4
3 1 4 2
1 4 2 3
3 4 1 2
3 2 1 4
4 1 3 2
3 2 1 4
4 2 1 4
0 0

Sample Output

1
2
3
4
5
6
7
8
9

Election #1
   2 bad ballot(s)
   Candidate 3 is elected.
Election #2
   2 bad ballot(s)
   The following candidates are tied: 1 3
Election #3
   1 bad ballot(s)
   Candidate 3 is elected.

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 <algorithm>
using namespace std;
int main() {
    int n, m, cases = 0, x;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        int bad[1024] = {}, A[1024][16];
        int badCount = 0;
        for(int i = 0; i < m; i++) {
            int mark[16] = {};
            for(int j = 0; j < n; j++) {
                scanf("%d", &x);
                A[i][j] = x;
                if(x > n || x < 1) {
                    bad[i] = 1;
                    continue;
                }
                mark[x]++;
                if(mark[x] > 1)
                    bad[i] = 1;
            }
            badCount += bad[i];
        }
        
        printf("Election #%d\n", ++cases);
        printf("   %d bad ballot(s)\n", badCount);
        
        int Atop[1024] = {}, alive[1024] = {}, aliveCount = n;
        for(int i = 1; i < n; i++) {
            int votes[16] = {}, mx = 0, del = -1;
            for(int j = 0; j < m; j++) {
                if(bad[j])	continue;
                while(alive[A[j][Atop[j]]])
                    Atop[j]++;
                votes[A[j][Atop[j]]]++;
            }
            for(int j = 1; j <= n; j++)
                mx = max(mx, votes[j]);
            for(int j = 1; j <= n; j++) {
                if(votes[j] < mx && alive[j] == 0)
                    del = j, mx = votes[j];
            }
            if(del == -1)	break;
            alive[del] = 1, aliveCount--;
        }
        if(aliveCount == 1) {
            for(int i = 1; i <= n; i++)
                if(alive[i] == 0)
                    printf("   Candidate %d is elected.\n", i);
        } else {
            printf("   The following candidates are tied:");
            for(int i = 1; i <= n; i++)
                if(alive[i] == 0)
                    printf(" %d", i);
            puts("");
        }
    }
    return 0;
}

Problem

Little Johnny has got a new car. He decided to drive around the town to visit his friends. Johnny wanted to visit all his friends, but there was many of them. In each street he had one friend. He started thinking how to make his trip as short as possible. Very soon he realized that the best way to do it was to travel through each street of town only once. Naturally, he wanted to finish his trip at the same place he started, at his parents’ house.

The streets in Johnny’s town were named by integer numbers from 1 to n, n < 1995. The junctions were independently named by integer numbers from 1 to m, tex2html_wrap_inline32 . All junctions in the town had different numbers. Each street was connecting exactly two (not necessarily different) junctions. No two streets in the town had the same number. He immediately started to plan his round trip. If there was more than one such round trip, he would have chosen the one which, when written down as a sequence of street numbers is lexicographically the smallest.

But Johnny was not able to find even one such round trip. Help Johnny and write a program which finds the desired shortest round trip. If the round trip does not exist the program should write a message. Assume that Johnny lives at the junction ending the 1st street input with smaller number. All streets in the town are two way. There exists a way from each street to another street in the town. The streets in the town are very narrow and there is no possibility to turn back the car once he is in the street.

Input

Input file consists of several blocks. Each block describes one town. Each line in the block contains three integers x, y, z, where x > 0 and y > 0 are the numbers of junctions which are connected by the street number z. The end of the block is marked by the line containing x = y = 0. At the end of the input file there is an empty block, x = y = 0.

Output

The output file consists of 2 line blocks corresponding to the blocks of the input file. The first line of each block contains the sequence of street numbers (single members of the sequence are separated by space) describing Johnny’s round trip. If the round trip cannot be found the corresponding output block contains the message ``Round trip does not exist.’’. The second line of each block is empty.

Sample Input

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

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

Sample Output

1
2
3

1 2 3 5 4 6
Round trip does not exist.

Solution

題目描述：

每一條路上都有編號，並且每個編號唯一且個數小於 44。

求一條經過所有邊且不重複的環道。

題目解法：

記得注意起始是第一條邊最小編號的點。

之後對於每一個點相鄰邊根據編號進行排序即可，按著窮舉思路由小開始枚舉即可。

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 <vector>
#include <algorithm>
#include <deque>
using namespace std;
struct edge {
    int to, label;
    edge(int a=0, int b=0):
        to(a), label(b) {}
    bool operator<(const edge &x) const {
        return label < x.label;
    }
};
#define MAXN 2048
vector<edge> g[MAXN];
int label_used[MAXN];
deque<int>	path;
void dfs(int u) {
    for(int i = 0; i < g[u].size(); i++) {
        if(label_used[g[u][i].label] == 0) {
        	label_used[g[u][i].label] = 1;
            dfs(g[u][i].to);
            path.push_front(g[u][i].label);
        }
    }
}
int main() {
    int x, y, z;
    while(true) {
    	for(int i = 0; i < MAXN; i++)
    		g[i].clear();
    	int e = 0, start = 0;
    	while(scanf("%d %d", &x, &y) == 2) {
    		if(x == 0 && y == 0)
    			break;
    		/* Johnny lives at the junction ending the 1st street 
				input with smaller number. */
    		if(e == 0)
    			start = min(x, y);
    		scanf("%d", &z);
    		g[x].push_back(edge(y, z));
    		g[y].push_back(edge(x, z));
    		e++;
    	}
    	if(e == 0)	break;
    	
    	int odd = 1;
    	for(int i = 0; i < MAXN; i++) {
    		odd &= g[i].size()%2 == 0;
    	}
    	if(!odd) {
    		puts("Round trip does not exist.\n");
    		continue;
    	}
    	for(int i = 0; i < MAXN; i++)
    		sort(g[i].begin(), g[i].end());
    	memset(label_used, 0, sizeof(label_used));
    	path.clear();
    	dfs(start);
    	for(int i = 0; i < path.size(); i++) 
    		printf("%d%c", path[i], i == path.size()-1 ? '\n' : ' ');
    	puts("");
    }
    return 0;
}

Problem

The musical notes are the basic units of Western music. Each note is associated with a frequency. Two notes for which the fundamental frequencies have a ratio of power of 2 (one is half of the other, one is double of the other, etc..) are perceived as very similar. Therefore, any notes with that kind of relationship are given the same name, as described below.

There are twelve basic notes in a sequence of increasing frequency, each note separated from the previous note by the same distance in the musical scale (this distance is called a semitone). Seven of these twelve notes are represented by letters of the alphabet (A, B, C, D, E, F and G). The table below shows the distance, in semitones, between the notes.

Notes A-B B-C C-D D-E E-F F-G G-A
Number of semitone 2 1 2 2 1 2 2

Notice that there are five notes that are not represented by letters of the alphabet: the notes between A and B, between C and D, between D and E, betwen F and G and between G and A.

Notes can be modified by two accidentals, called sharp and flat, represented respectively by the symbols #' andb’. A sharp raises the note a semitone, a flat lowers the note a semitone. A note with an accidental is denoted by the name of the note followed by the accidental symbol. Notice that with this scheme we can represent all twelve notes.

The figure below illustrates the name of the notes in accordance with the scheme described above, in a fragment of a piano keyboard.

A melody can be represented by a sequence of notes. For example,

A A D C# C# D E E E F# A D G# A

is a well known melody. Note however that as the distances between the semitones are always equal, the same melody can be written starting with another note (we say that the melody is in another key):

B B E D# D# E Gb Gb Gb G# B E A# B

Your neighbor is a famous composer who suspects someone has plagiarized one of her songs. She asked your help to write a program that, given the sequence of notes of the melody in her song, and the sequence of notes of a suspicious snippet of melody, determines if the suspicious snippet occurs, in some key, in her song.

Input

The input consists of several test cases. The first line of a test case contains two integers M and T ( 1$\le$M$\le$105, 1$\le$T$\le$104, T$\le$M), indicating the number of notes in the song suspected of having been plagiarized and in the suspect snippet. Each of the next two lines contains M and T notes, respectively, indicating the notes of the song and of the suspect snippet.

Notes in each line are separated by one space; each note is one among A',B’, C',D’, E',F’ or G', possibly followed by an accidental sign:#’ for sharp or `b’ for flat.

The last test case is followed by a line containing only two zeros separated by a blank space.

Output

For each test case your program must print a single line containing one character, S' in case the song has been plagiarized by the text, orN’ in case the song has not been plagiarized by the text.

Sample Input

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

16 4
D G A B C D G G G C D E F# G C C
G G C D
12 2
C C# D D# E F F# G G# A A# B
C D
12 2
C Db D Eb E F Gb G Ab A Bb B
C D
4 3
C E G Bb
D F# A
0 0

Sample Output

1
2
3
4

S
N
N
S

Solution

題目描述：

音階 全全半全全全半，全音中間夾一個黑/白鍵，半音之間沒有。

計算是否為旋律中的一部分，計算旋律時只需考慮音符之間的距離即可，與高低幾度偏移沒有關係。

題目解法：

特別小心，查詢的旋律長度為 1 的時候，無法判斷 (雖然以子字串是有在的)。

接著，直接對距離之間取模之後得到兩個整數序列，直接套用 KMP 判斷序列是否在另一個序列中。

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

#include <stdio.h>
#include <algorithm>
using namespace std;
int notes[128] = {};
int kmpTable[500005];
void KMPtable(int *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(int T[], int P[], int tlen, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1) {
            j = kmpTable[j];
            return i;
        }
    }
    return -1;
}
int main() {
    int M, T;
    int A[100005], B[10005];
    char s[10];
    notes['C'] = 0, notes['D'] = 2;
    notes['E'] = 4,	notes['F'] = 5;
    notes['G'] = 7,	notes['A'] = 9;
    notes['B'] = 11;
    while(scanf("%d %d", &M, &T) == 2 && M + T) {
        int prev, x;
        for(int i = 0; i < M; i++) {
            scanf("%s", &s);
            x = (notes[s[0]] + (s[1] == '#') - (s[1] == 'b') + 12)%12;
            if(i)	A[i - 1] = (prev - x + 12)%12;
            prev = x;
        }
        for(int i = 0; i < T; i++) {
            scanf("%s", &s);
            x = (notes[s[0]] + (s[1] == '#') - (s[1] == 'b') + 12)%12;
            if(i)	B[i - 1] = (prev - x + 12)%12;
            prev = x;
        }
        KMPtable(A, M - 1);
        puts( KMPmatching(A, B, M - 1, T - 1) >= 0 ? "S" : "N");
    }
    return 0;
}

Problem

Unfortunately, Peter’s Calculator broke down last week. Now Peter is left with his computer, which has no calculator application, and paper and pencil, which is too tiresome for an engineer. As one of Peter’s friends, you are asked to write him a calculator application. After talking to him, you figure out the following:

• Peter does only integer arithmetic. The operations he needs are addition, subtraction and multiplication.
• He would like to use an arbitrary number of variables whose names are not longer than 50 characters.
• His main way of doing calculations are to type in a few formulas and to assign them to variables. Some formulas are complicated expressions, which can refer to yet undefined variables, while other formulas consist of a single number. Then Peter asks for the value of some variables, i.e. he evaluates the formulas.
• Peters wants to redefine some variables and then to reevaluate formulas that depend on these variables.

The input strictly adheres to the following syntax (given in EBNF):

1
2
3
4
5
6
7
8
9
10

file = line { line } <EOF>.
line = [ assignment | print | reset ] <CR>.
assignment = var ":=" expression.
print = "PRINT" var.
reset = "RESET".
expression = term { addop term }.
term = factor { mulop factor }.
factor = "(" expression ")" | var | number.
addop = "+" | "-".
mulop = "*".

In the Extended Backus-Naur Formalism (EBNF), A = B C declares that the grammatical construct A consists of a B followed by a C . A = B | C means that A consists of a B or, alternatively, of a C . A = [ B ] defines construct A to be either a B or nothing and A = B tells you that A consists of the concatenation of any number of B’s (including none).

The production var stands for the name of a variable, which starts with a letter followed by up to 49 letters or digits. Letters may be uppercase or lowercase. The production number stands for a integer number. The precise syntax for these productions are given below. The case of letters is important for both variables and statements.

1
2
3
4

var = letter { letter | digit }.
number = [ "-" ] digit { digit }.
letter = "A" | "B" | ... | "Z" | "a" | "b" | ... | "z".
digit = "0" | "1" | ... | "8" | "9".

Between the parts of a grammatical construct but not within the names of variables or integer numbers, any number of spaces may appear. stands for the end of the input file and stands for the new-line character. All lines in the input file are shorter than 200 characters.

The value of a variable is said to be undefined:

• if it has not yet been defined or it refers to a variable, which has not yet been defined;
• if the definition of the variable contains a cycle.

Your are to write a program that implements Peter’s calculator. It should store all variable definitions and for each “PRINT” statement evaluate the specified variable based on the latest variable definitions. If your program encounters a “RESET” statement, it should delete all stored variables so that all variables become undefined.

Input

The input file contains calculations adhering to the syntax given above. Each line contains either an assignment to a variable, a “PRINT” statement, a “RESET” statement or nothing.

Output

For each “PRINT” statement found in the input file, your program should output a line containing the numerical value of the specified variable or the word “UNDEF” if the variable is undefined.

Sample Input

1
2
3
4
5
6
7
8
9

a := b + c
b := 3
c := 5
PRINT d
PRINT a
b := 8
PRINT a
RESET
PRINT a

Sample Output

1
2
3
4

UNDEF
8
13
UNDEF

Solution

題目描述：

輸入有一連串的變數函數，適時地打印出詢問的變數值，如果存在循環依靠 (無法推論) 或者是變數尚未定義，直接輸出 UNDEF。

後輸入的變數函數會覆蓋原先的函數。

題目解法：

將每一組函數轉成後序運算式子，爾後再使用深度優先搜索走訪查看是否有環。

著重的問題在於負數的分析，例如 0 - -50, (a + b) - 50 等等。

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

#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <sstream>
#include <map>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return 0;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    return -1;
}
int isoperator(char c) {
    switch(c) {
        case '(':case ')':case '+': case '-':case '*': case '/':return 1;
    }
    return 0;
}
int isvariable(string token) {
    return isalpha(token[0]);
}
void trans(const char *infix, char buffer[]) {
    int len = strlen(infix), prevOp = 1;
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
        if(isalpha(infix[i]) || isdigit(infix[i]) 
            || (infix[i] == '-' && isdigit(infix[i+1]) && prevOp)) {
            prevOp = 0;
        	sprintf(ptr, "%c", infix[i]), i++;
        	while(*ptr)    ptr++;
            while(isalpha(infix[i]) || isdigit(infix[i])) {
            	sprintf(ptr, "%c", infix[i]), i++;
            	while(*ptr)    ptr++;
            }
            sprintf(ptr, " "), i--;
            while(*ptr)		ptr++;
        } else {
        	prevOp = 0;
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(') {
                    while(!op.empty() && priority_op(op.top()) >= priority_op(infix[i])) {
                        sprintf(ptr, "%c ", op.top()), op.pop();
                        while(*ptr) ptr++;
                    }
            	}
            	prevOp = 1;
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
void trimWhiteSpace(char s[]) {
    int j = 0;
    for(int i = 0; s[i]; i++)
        if(!isspace(s[i]))
            s[j++] = s[i];
    s[j] = '\0';
}
map<string, string> VAL_exp;
map<string, int>	VAL_val;
map<string, int>	VAL_stk;
int error_FLAG;
int calcPostfix(const char* postfix);
int getValue(string VAL_name) {
    if(!isvariable(VAL_name)) {
    	stringstream scin(VAL_name);
    	int value;
    	scin >> value;
    	return value;
    }
    if(VAL_exp.find(VAL_name) == VAL_exp.end() || VAL_stk[VAL_name]) {
        error_FLAG = 1;
        return 0;
    }
    if(VAL_val.find(VAL_name) == VAL_val.end()) {
        VAL_stk[VAL_name] = 1;
//		cout << "solving " << VAL_name << ", " << VAL_exp[VAL_name] << endl; 
        VAL_val[VAL_name] = calcPostfix(VAL_exp[VAL_name].c_str());
//		cout << "solved " << VAL_name << ", val = " << VAL_val[VAL_name] << endl;
        VAL_stk[VAL_name] = 0;
    }
    return VAL_val[VAL_name];
}
int calcPostfix(const char* postfix) {
    stringstream 	scin(postfix);
    stack<int> 		stk;
    string			token;
    int 			a, b;
    
    while(scin >> token) {
    	if(token.length() == 1 && isoperator(token[0])) {
            b = stk.top(), stk.pop();
            a = stk.top(), stk.pop();
            switch(token[0]) {
                case '+': a = a+b;break;
                case '-': a = a-b;break;
                case '*': a = a*b;break;
                case '/': a = a/b;break;
            }
            stk.push(a);
    	} else {
    		stk.push(getValue(token));
    	}
    	if(error_FLAG)	return 0;
    }
    return stk.top();
}
void printVal(string valName) {
    error_FLAG = 0;
    VAL_val.clear();
    VAL_stk.clear();
    int val = getValue(valName);
    if(error_FLAG)
        puts("UNDEF");
    else
        printf("%d\n", val);
}
int main() {
//	freopen("input.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    string 	LHS, RHS;
    int 	pos;
    char 	postfix[32767], lines[32767];
    
    while(gets(lines)) {
    	trimWhiteSpace(lines);
    	string str(lines);
    	if(str.find(":=") != string::npos) {
    		pos = str.find(":=");
    		LHS = str.substr(0, pos);
    		RHS = str.substr(pos + 2);
    		trans(RHS.c_str(), postfix);
    		VAL_exp[LHS] = postfix;
    	} else if(str.find("PRINT") != string::npos) {
    		pos = str.find("PRINT");
    		RHS = str.substr(pos + 5);
    		printVal(RHS);
    	} else if(str.find("RESET") != string::npos) {
    		VAL_exp.clear();
    	}
    }
    return 0;
}

Problem

Morley’s theorem states that that the lines trisecting the angles of an arbitrary plane triangle meet at the vertices of an equilateral triangle. For example in the figure below the tri-sectors of angles A, B and C has intersected and created an equilateral triangle DEF.

Of course the theorem has various generalizations, in particular if all of the tri-sectors are intersected one obtains four other equilateral triangles. But in the original theorem only tri-sectors nearest to BC are allowed to intersect to get point D, tri-sectors nearest to CA are allowed to intersect point E and tri-sectors nearest to AB are intersected to get point F. Trisector like BD and CE are not allowed to intersect. So ultimately we get only one equilateral triangle DEF. Now your task is to find the Cartesian coordinates of D, E and F given the coordinates of A, B, and C.

Input

First line of the input file contains an integer N (0<N<5001) which denotes the number of test cases to follow. Each of the next lines contain six integers . This six integers actually indicates that the Cartesian coordinates of point A, B and C are respectively. You can assume that the area of triangle ABC is not equal to zero, and the points A, B and C are in counter clockwise order.

Output

For each line of input you should produce one line of output. This line contains six floating point numbers separated by a single space. These six floating-point actually means that the Cartesian coordinates of D, E and F are respectively. Errors less than will be accepted.

Sample Input

1
2
3

2
1 1 2 2 1 2
0 0 100 0 50 50

Output for Sample Input

1
2

1.316987 1.816987 1.183013 1.683013 1.366025 1.633975
56.698730 25.000000 43.301270 25.000000 50.000000 13.397460

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

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
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 angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
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);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
Pt solve(Pt A, Pt B, Pt C) {
    double radABC = angle(A - B, C - B);
    double radACB = angle(A - C, B - C);
    
    Pt vB = rotateRadian(C - B, radABC /3);
    Pt vC = rotateRadian(B - C, - radACB /3);
    
    return getIntersection(B, vB, C, vC);
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        Pt A, B, C, D, E, F;
        scanf("%lf %lf", &A.x, &A.y);
        scanf("%lf %lf", &B.x, &B.y);
        scanf("%lf %lf", &C.x, &C.y);
        D = solve(A, B, C);
        E = solve(B, C, A);
        F = solve(C, A, B);
        printf("%lf %lf %lf %lf %lf %lf\n", D.x, D.y, E.x, E.y, F.x, F.y);
    }
    return 0;
}

Problem

FlatLand Piano Movers, as part of their Total Quality Management project, has decided to focus on the job estimation process. Part of this process involves walking the proposed paths that are to be used to move a piano to see if it will fit through corridors and around corners. Now this is harder than it might seem, since FlatLand is a 2-dimensional world.

FlatLand pianos are rectangles of various sizes. FlatLand building codes require all turns in corridors to be right angle turns and prohibit T intersections. All dimensions are in furlongs. You can assume that each portion of a corridor is long enough so that other corners or doors into rooms don’t have any effect on getting around a turn. You can also assume that the piano is narrower than the width of any corridor. Note that the piano actually has to turn in the corner, since it can only be pushed or pulled on one of its shorter sides (there are no square pianos).

Your team’s job is to write a program for a palmtop computer that will determine if a given piano will fit around a corner in a corridor.

Input

The input consists of a series of lines up to 80 columns in width followed by the end-of-file. Each line consists of a series of number pairs. The numbers of a pair are separated by a comma and the pairs are separated by at least one space. The first pair is the size of a piano, and the remaining pairs are the widths of corridors on each side of the turns. Consider the example:

1

600,200 300,500 837,500 350,350

This is a 600 by 200 piano. The first turn is from a 300 furlong wide corridor through a right angle turn into a 500 furlong wide corridor. The next turn is from an 837 furlong wide corridor into one 500 furlongs wide. The last turn is from a 350 furlong wide corridor into another 350 furlong wide corridor.

Output

For each piano, your program is to produce a yes-or-no answer for each turn. If the piano will fit around the turn, print Y''; if not, printN’’. The results for each piano should be printed on a separate line.

Sample Input

1
2

600,200   300,500   837,500  350,350 
137,1200 600,500 600,400

Sample Output

1
2

YYN
YN

Solution

題目描述：

一台鋼琴長寬 W, H，接著要經過一個 T 字路口，進去之後向右轉，一開始進去的寬度為 X，右轉之後的寬度為 Y，問能不能順利轉彎。

每組輸入給定一台鋼琴長寬，接著給定多組路口寬組合。

題目解法：

汽车拐弯问题，给定 X, Y, l, d 判断是否能够拐弯。首先当 X 或者 Y 小于 d，那么一定不能。
其次我们发现随着角度 θ 的增大，最大高度 h 先增长后减小，即为凸性函数，可以用三分法来求解。

这里的 Calc 函数需要比较繁琐的推倒公式：
s = l cos(θ) + w sin(θ) - x;
h = s tan(θ) + w cos(θ);
其中 s 为汽车最右边的点离拐角的水平距离, h 为里拐点最高的距离, θ 范围从 0 到 90。

看著大神給的三分搜索的式子，用簡單的凸性勾勒出來。

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

#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
// http://www.cnblogs.com/newpanderking/archive/2011/08/25/2153777.html
const double pi = acos(-1);
#define eps 1e-6 
double ternary_search(double H, double W, double X, double Y) {
    double l = 0, r = pi /2, mid, midmid;
    double s1, h1, s2, h2;
    while(fabs(l - r) > eps) {
        mid = (l + r) /2;
        midmid = (mid + r) /2;
        s1 = H * cos(mid) + W * sin(mid) - X;
        h1 = s1 * tan(mid) + W * cos(mid);
        s2 = H * cos(midmid) + W * sin(midmid) - X;
        h2 = s2 * tan(midmid) + W * cos(midmid);
        if(h1 < h2)
            l = mid;
        else
            r = mid;
    }
    return h1;
}
int main() {
    char line[1024];
    while(gets(line)) {
        stringstream sin(line);
        string token;
        sin >> token;
        double H, W, X, Y;
        sscanf(token.c_str(), "%lf,%lf", &H, &W);
        if(H < W)
            swap(H, W);
        while(sin >> token) {
            sscanf(token.c_str(), "%lf,%lf", &X, &Y);
            double h = ternary_search(H, W, X, Y);
            printf("%c", h <= Y ? 'Y' : 'N');
        }
        puts("");
    }
    return 0;
}

Problem

A well known psychology experiment involves people playing a game in which they can either trade with each other or attempt to cheat the other player. If both players TRADE then each gains one point. If one TRADEs and the other CHEATs then the TRADEr loses 2 points and the CHEATer wins 2. If both CHEAT then each loses 1 point.

There are a variety of different strategies for playing this game, although most people are either unable to find a winning strategy, or, having decided on a strategy, do not stick to it. Thus it is fairer to attempt to evaluate these strategies by simulation on a computer. Each strategy is simulated by an automaton. An automaton is characterised by a program incorporating the strategy, a memory for previous encounters and a count reflecting the score of that automaton. The count starts at zero and is altered according to the above rules after each encounter. The memory is able to determine what happened on up to the last two encounters with each other contender.

Write a program that will read in details of up to 10 different strategies, play each strategy against each other strategy 10 times and then print out the final scores. Strategies will be in the form of simple programs obeying the following grammar:

1
2
3
4
5
6
7
8

<program> ::= <statement>.
<statement> ::= <command> tex2html_wrap_inline45 <ifstat>
<ifstat> ::= IF <condition> THEN <statement> ELSE <statement>
<condition> ::= <cond> tex2html_wrap_inline45 <cond> <op> <condition>
<op> ::= AND tex2html_wrap_inline45 OR
<cond> ::= <memory> {= tex2html_wrap_inline45 #} {<command> tex2html_wrap_inline45 NULL}
<memory> ::= {MY tex2html_wrap_inline45 YOUR} LAST {1 tex2html_wrap_inline45 2}
<command> ::= TRADE tex2html_wrap_inline45 CHEAT

Note that LAST1 refers to the previous encounter between these two automata, LAST2 to the encounter before that and that MY' andYOUR’ have the obvious meanings. Spaces and line breaks may appear anywhere in the program and are for legibility only. The symbol #' meansis not equal to’. NULL indicates that an encounter has not ocurred. The following are valid programs:

CHEAT.
IF MY LAST1 = CHEAT THEN TRADE ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADE
ELSECHEAT.

Input

Input will consist of a series of programs. Each program will be no longer than 255 characters and may be split over several lines for convenience. There will be no more than 10 programs. The file will be terminated by a line containing only a single `#’.

Output

Output will consist of one line for each line of input. Each line will consist of the final score of the relevant program right justified in a field of width 3.

Sample input

1
2
3
4
5

CHEAT.
IF MY LAST1 = CHEAT THEN TRADE ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADE
ELSECHEAT.
#

Sample output

1
2
3

  1
-12
-13

Solution

題目描述：

現在這邊有兩台機器人，玩類似 “吹牛” 的紙牌遊戲，欺騙成功者將獲得點數。

而每一台機器的策略也有所不同，並且能根據對方前幾次和自己前幾次的策略進行判斷，給予每一台機器的策略模式，請兩兩互打 10 回合，最後輸出每一台機器的得分概況。

題目解法：

這題不只有語法分析，還有語意分析。總之，遞迴分析是最主要的技巧。
對於 AND 和 OR 運算，測資中似乎沒有優先順序的情況，所以直接由左而右進行即可。

而在分析的時候，嘗試將指針一直往後移動，並且解析出第一個符合條件的 token。

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

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iostream>
#include <map>
#include <assert.h>
#include <string.h>
#include <ctype.h>
using namespace std;
enum ACTION {TRADE, CHEAT, EMPTY};
enum RECORD {LAST1, LAST2};
class Memory {
public:
    map<RECORD, ACTION> R;
    Memory() {
        R[LAST1] = EMPTY;
        R[LAST2] = EMPTY;
    }
    static ACTION getAction(string s) {
        if(s == "TRADE")    return TRADE;
        if(s == "CHEAT")    return CHEAT;
        if(s == "EMPTY")    return EMPTY;
        assert(false);
    }
    ACTION getMemory(string addr) {
        if (addr == "LAST1")
            return R[LAST1];
        if (addr == "LAST2")
            return R[LAST2];
        assert(false);
    }
    void record(ACTION a) {
        ACTION last1 = R[LAST1], last2 = R[LAST2];
        R[LAST1] = a;
        R[LAST2] = last1;
    }
};
class Strategy {
public:
    char prog[1024];
    Strategy(string s) {
        for (int i = 0; i < s.length(); i++) {
            prog[i] = s[i];
        }
        prog[s.length()] = '\0';
    }
    char* match(char *str, const char *p) {
        if (str == NULL)
            return  NULL;
        if (memcmp(str, p, strlen(p)) == 0)
            return str + strlen(p);
        return NULL;
    }
/*
 <condition> ::= <cond> | <cond> <op> <condition>
 <op> ::= AND | OR
 <cond> ::= <memory> {= | #} {<command> | NULL}
 <memory> ::= {MY | YOUR} LAST {1 | 2}
 <command> ::= TRADE | CHEAT
 */
    bool cond(char* &p, Memory MY, Memory YOUR) {
        // printf("condition %s\n", p);
        char        *q;
        Memory      *addr = NULL;
        string      read, equal, kind;
        /* <memory> */
        q = match(p, "MY");
        if(q != NULL)   p = q, addr = &MY;
        q = match(p, "YOUR");
        if(q != NULL)   p = q, addr = &YOUR;
        q = match(p, "LAST1");
        if(q != NULL)   p = q, read = "LAST1";
        q = match(p, "LAST2");
        if(q != NULL)   p = q, read = "LAST2";
        /* {= | #} */
        q = match(p, "=");
        if(q != NULL)   p = q, equal = "=";
        q = match(p, "#");
        if(q != NULL)   p = q, equal = "#";
        /* {<command> | NULL} */
        q = match(p, "TRADE");
        if(q != NULL)  p = q, kind = "TRADE";
        q = match(p, "CHEAT");
        if(q != NULL)  p = q, kind = "CHEAT";
        q = match(p, "NULL");
        if(q != NULL)  p = q, kind = "EMPTY";
        bool ret = equal == "=" ? addr->getMemory(read) == Memory::getAction(kind) :
                                    addr->getMemory(read) != Memory::getAction(kind);
        // cout << "ADDR: " << addr->getMemory(read) << ", ACTION: " << Memory::getAction(kind) << endl;
        // cout << read << ", " << kind << endl; 
        /* <op> <condition> */
        q = match(p, "AND");
        if(q != NULL)  p = q, ret = ret&cond(p, MY, YOUR);
        q = match(p, "OR");
        if(q != NULL)  p = q, ret = ret|cond(p, MY, YOUR);
        // cout << "return " << ret << endl;
        return ret;
    }
    ACTION ifstat(char* &p, Memory a, Memory b) {
        char *q;
        q = match(p, "IF");
        if (q != NULL) {
            p = q;
            bool f = cond(p, a, b);
            ACTION a1, a2;
            q = match(p, "THEN");
            p = q;
            a1 = statement(p, a, b);
            q = match(p, "ELSE");
        	p = q;
        	a2 = statement(p, a, b);
        	return f ? a1 : a2;
        }
        assert(false);
    }
    ACTION statement(char* &p, Memory a, Memory b) {
        // printf("%s\n", p);
        char *q;
        q = match(p, "TRADE");
        if (q != NULL)  {
            p = q;
            return TRADE;
        }
        q = match(p, "CHEAT");
        if (q != NULL) {
            p = q;
            return CHEAT;
        }
        return ifstat(p, a, b);
    }
    ACTION eval(char* &p, Memory a, Memory b) { // read only
        // printf("eval %s\n", p);
        return statement(p, a, b);
    }
};
int main() {
    char c, s[1024];
    vector<Strategy> machine;
    while (true) {
        int n = 0;
        while ((c = getchar()) != EOF) {
            if(c == '.' || (c == '#' && n == 0) )
                break;
            if(isspace(c))
                continue;
            s[n++] = c;
        }
        if (n == 0)
            break;
        s[n++] = '\0';
        machine.push_back(Strategy(s));
    }
#define MAXN 20
    int SCORE[MAXN] = {};
    for (int i = 0; i < machine.size(); i++) {
        for (int j = i + 1; j < machine.size(); j++) {
            Memory      ma, mb;
            Strategy    &A = machine[i];
            Strategy    &B = machine[j];
            char        *p;
            
            for (int k = 0; k < 10; k++) {
                ACTION ia = A.eval(p = A.prog, ma, mb);
                ACTION ib = B.eval(p = B.prog, mb, ma);
                if(ia == TRADE && ib == TRADE)
                	SCORE[i]++, SCORE[j]++;
                else if(ia == TRADE && ib == CHEAT)
                	SCORE[i] -= 2, SCORE[j] += 2;
                else if(ia == CHEAT && ib == TRADE)
                	SCORE[i] += 2, SCORE[j] -= 2;
                else
                	SCORE[i]--, SCORE[j]--;
                ma.record(ia), mb.record(ib);
            }
        }
    }
    for(int i = 0; i < machine.size(); i++)
    	printf("%3d\n", SCORE[i]);
    return 0;
}