解題區/解題區 - UVa

UVa 198 - Peter's Calculator

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;
}
Read More +
解題區/解題區 - UVa

UVa 11178 - Morley's Theorem

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;
}
Read More +
解題區/解題區 - UVa

UVa 427 - FlatLand Piano Movers

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;
}
Read More +
解題區/解題區 - UVa

UVa 174 - Strategy

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;
}
Read More +
解題區/解題區 - UVa

UVa 171 - Car Trialling

Problem

Car trialling requires the following of carefully worded instructions. When setting a trial, the organiser places traps in the instructions to catch out the unwary.

Write a program to determine whether an instruction obeys the following rules, which are loosely based on real car trialling instructions. BOLD-TEXT indicates text as it appears in the instruction (case sensitive), | separates options of which exactly one must be chosen, and .. expands, so A..D is equivalent to A | B | C | D .

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
instruction = navigational | time-keeping | navigational AND time-keeping
navigational = directional | navigational AND THEN directional
directional = how direction | how direction where
how = GO | GO when | KEEP
direction = RIGHT | LEFT
when = FIRST | SECOND | THIRD
where = AT sign
sign = "signwords"
signwords = s-word | signwords s-word
s-word = letter | s-word letter
letter = A..Z | .
time-keeping = record tex2html_wrap_inline61 change
record = RECORD TIME
change = cas TO nnn KMH
cas = CHANGE AVERAGE SPEED | CAS
nnn = digit | nnn digit

digit = 0..9 Note that s-word and nnn are sequences of letters and digits respectively, with no intervening spaces. There will be one or more spaces between items except before a period (.), after the opening speech marks or before the closing speech marks.

Input

Each input line will consist of not more than 75 characters. The input will be terminated by a line consisting of a single #.

Output

The output will consist of a series of sequentially numbered lines, either containing the valid instruction, or the text Trap! if the line did not obey the rules. The line number will be right justified in a field of 3 characters, followed by a full-stop, a single space, and the instruction, with sequences of more than one space reduced to single spaces.

Sample input

1
2
3
4
5
6
7
KEEP LEFT AND THEN GO RIGHT
CAS TO 20 KMH
GO FIRST       RIGHT AT "SMITH ST."  AND   CAS TO 20 KMH
GO 2nd RIGHT
GO LEFT AT "SMITH STREET AND RECORD TIME
KEEP RIGHT AND THEN RECORD TIME
#

Sample output

1
2
3
4
5
6
1. KEEP LEFT AND THEN GO RIGHT
2. CAS TO 20 KMH
3. GO FIRST RIGHT AT "SMITH ST." AND CAS TO 20 KMH
4. Trap!
5. Trap!
6. Trap!

Solution

題目描述：

根據題目給定的規則，將汽車引領的命令句子做合法語句判斷。

題目解法：

根據編譯器的方式，採用 LL(1) 修改題目給定的規則後，要進行建表，但是發現有幾處無法排除的語法規則，之後採用 SLR(1) 來完成。

SLR(1) 是由 LR(0) 加上 follow set 完成。

詳細的運作過程請詳見 wiki 說明，或者是修編譯器。

1
There will be one or more spaces between items except before a period (.), after the opening speech marks or before the closing speech marks.

本題最邪惡的地方在這裡，句號（.）前不可以用空白，前雙引號後不可有空白、後雙引號前不可以有空白。

雖然題目有包含這些 token 的語法產生，但還是用最暴力的方式將句子做基礎的 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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
#include <stdio.h> 
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string.h>
#include <ctype.h>
#include <assert.h>
using namespace std;
#define HTMLProduction
// #define DEBUG
class Production {
    public:
        int 			label;
        string 			LHS;
        vector<string> 	RHS;
        
        Production(string L = "", vector<string> R = vector<string>(), int l=0) {
            LHS = L;
            RHS = R;
            label = l;
        }
        bool operator<(const Production &p) const {
            if(LHS != p.LHS)
                return LHS < p.LHS;
            for(size_t i = 0, j = 0; i < RHS.size() && j < p.RHS.size(); i++, j++) {
                if(RHS[i] != p.RHS[i])
                    return RHS[i] < p.RHS[i];
            }
            return RHS.size() < p.RHS.size();
        }
        
        bool operator==(const Production &p) const {
            if(LHS != p.LHS || RHS.size() != p.RHS.size())
                return false;
            for(size_t i = 0, j = 0; i < RHS.size(); i++, j++) {
                if(RHS[i] != p.RHS[i])
                    return false;
            }
            return true;
        }
        
        bool operator!=(const Production &p) const {
            return !(*this == p);
        }
        
        void print() {
            printf("%s -> ", LHS.c_str());
            for(size_t i = 0; i < RHS.size(); i++)
                printf("%s", RHS[i].c_str());
        }
};
class Grammar {
    public:
        /* LR parsing */
        class ConfigurationSet {
            public:
                class State {
                    public:
                        int dot;
                        vector<string> lookahead;
                        
                        State(int d=0, vector<string> l=vector<string>()):
                            dot(d), lookahead(l) {}
                        bool operator<(const State &x) const {
                            return dot < x.dot;
                        }
                        bool operator!=(const State &x) const {
                            return dot != x.dot;
                        }
                };
                
                set< pair<Production, State> > 	configs;
                int 							label;
                ConfigurationSet() {
                    label = 0;
                }
                /* method */
                static ConfigurationSet closure0(ConfigurationSet& s, Grammar& g);
                static ConfigurationSet go_to0(ConfigurationSet& s, string X, Grammar& g);
                void print(Grammar &g) {
                    set< pair<Production, State> >::iterator it;
                    Production p;
                    
                    for(it = configs.begin(); it != configs.end(); it++) {
                        p = it->first;
                        printf("%s ->", p.LHS.c_str());
                        for(size_t i = 0; i < p.RHS.size(); i++) {
                            if(i == it->second.dot)
                                printf("¡E");
                            printf(" %s ", p.RHS[i].c_str());
                        }
                        if(it->second.dot == p.RHS.size())
                            printf("¡E");
                        printf(" ,{");
                        set<string> fset = g.follow_set[p.LHS];
                        for(set<string>::iterator jt = fset.begin();
                            jt != fset.end(); jt++) {
                            if(jt != fset.begin())
                                cout << ", ";
                            cout << *jt;
                        }
                        printf("}");
                        puts("");
                    }
                }
                bool operator<(const ConfigurationSet &x) const {
                    if(configs.size() != x.configs.size())
                        return configs.size() < x.configs.size();
                    for(set< pair<Production, State> >::iterator it = configs.begin(), jt = x.configs.begin();
                        it != configs.end(); it++, jt++) {
                        if(it->first != jt->first)
                            return it->first < jt->first;
                        if(it->second != jt->second)
                            return it->second < jt->second;
                    }
                    return false;
                    // return label < x.label;
                }
        };		
        
        static const string 		lambda;
        set<string>					symbols;
        string 						start_symbol;
        vector<Production> 			rules;
        /* LL(1) attribute */
        map<string, set<string> > 	first_set;
        map<string, set<string> > 	follow_set;
        map<string, bool> 			derives_lambda;
        map<string, map<string, Production> >	lltable;
        /* LR attribute */
        vector<ConfigurationSet>	LRstates;
        map<int, map<string, int> >	go_to_table;
        map<int, int>				action_table;
        
        /* common method */
        static bool isNonterminal(string token);
        void buildSymbols();
        /* LL(1) method */
        map<string, bool> mark_lambda();
        void fill_first_set();
        void fill_follow_set();
        set<string> compute_first(vector<string> rhs);
        set<string> get_predict_set(Production p);
        void fill_lltable();
        void lldriver(queue<string> tokens);
        /* LR method*/
        void build_CFSM();
        void build_action();
        void lr0driver(queue<string> tokens);
        int slr1driver(queue<string> tokens);
        void lalr1driver(queue<string> tokens);
        /* homework */
        void hw_build_CFSM();
};
/* ------------------------
ConfigurationSet method
-------------------------- */
Grammar::ConfigurationSet Grammar::ConfigurationSet::closure0(ConfigurationSet& s, Grammar& g) {
    ConfigurationSet 	r = s;
    bool				changes;
    string				A;
    Production			P;
    int 				dotPos;
    
    set< pair<Production, State> >::iterator it;
    do {
        changes = false;
        for(it = r.configs.begin(); it != r.configs.end(); it++) {
            P = it->first;
            dotPos = it->second.dot;
            if(dotPos >= P.RHS.size() || P.RHS[dotPos] == Grammar::lambda)
                continue;
            A = P.RHS[dotPos];
            if(Grammar::isNonterminal(A)) {
                /* B -> x.Ay */
                /* Predict productions with A as the left-hand side */
                for(size_t i = 0; i < g.rules.size(); i++) {
                    if(g.rules[i].LHS == A) {
                        if(r.configs.find(make_pair(g.rules[i], State(0))) == r.configs.end()) {
                            r.configs.insert(make_pair(g.rules[i], State(0)));
                            changes = true;
                        }
                    }
                }
            }
        }
    } while(changes);
    return r;
}
Grammar::ConfigurationSet Grammar::ConfigurationSet::go_to0(ConfigurationSet& s, string X, Grammar& g) {
    ConfigurationSet sb;
    set< pair<Production, State> >::iterator it;
    Production 	P;
    int 		dotPos;
    
    for(it = s.configs.begin(); it != s.configs.end(); it++) {
        P = it->first;
        dotPos = it->second.dot;
        if(dotPos >= P.RHS.size() || P.RHS[dotPos] == Grammar::lambda)
            continue;
        if(P.RHS[dotPos] == X) {
            State state(dotPos + 1, it->second.lookahead);
            sb.configs.insert(make_pair(P, state));
        }
    }
    return closure0(sb, g);
}
/* ------------------------
Grammar method
-------------------------- */
const string Grammar::lambda("l");
set<string> Grammar::compute_first(vector<string> rhs) {
    set<string> result;
    size_t 		i;
    
    if(rhs.size() == 0 || rhs[0] == Grammar::lambda) {
        result.insert(Grammar::lambda);
    } else {
        result = first_set[rhs[0]];
        for(i = 1; i < rhs.size() && 
            first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end(); i++) {
            set<string> f = first_set[rhs[i]];
            f.erase(Grammar::lambda);
            result.insert(f.begin(), f.end());	
        }
        if(i == rhs.size() 
            && first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end()) {
            result.insert(Grammar::lambda);
        } else {
            result.erase(Grammar::lambda);
        }
    }
    
    return result;
} 
/*
 * please call get_predict_set() after fill_follow_set() and fill_first_set()
 */
set<string> Grammar::get_predict_set(Production p) {
    set<string> result;
    set<string> rfirst;
    
    rfirst = compute_first(p.RHS);
    if(rfirst.find(Grammar::lambda) != rfirst.end()) {
        rfirst.erase(Grammar::lambda);
        result.insert(rfirst.begin(), rfirst.end());
        rfirst = follow_set[p.LHS];
        result.insert(rfirst.begin(), rfirst.end());
    } else {
        result.insert(rfirst.begin(), rfirst.end());
    }
    
    return result;
}
/*
 * 
 */
void Grammar::fill_lltable() {
    string		A; // nonterminal
    Production 	p;
    
    for(size_t i = 0; i < rules.size(); i++) {
        p = rules[i];
        A = p.LHS;
        set<string> predict_set = get_predict_set(p);
        
        for(set<string>::iterator it = predict_set.begin();
            it != predict_set.end(); it++) {
            assert(lltable[A].find(*it) == lltable[A].end());
            lltable[A][*it] = p;
        }
    }
    
}
void Grammar::buildSymbols() {
    symbols.clear();
    for(size_t i = 0; i < rules.size(); i++) {
        symbols.insert(rules[i].LHS);
        for(size_t j = 0; j < rules[i].RHS.size(); j++) {
            symbols.insert(rules[i].RHS[j]);
        }
    }
}
bool Grammar::isNonterminal(string token) {
#ifdef HTMLProduction
    if(token == Grammar::lambda)
        return false;
    if(token[0] == '<' && token[token.length() - 1] == '>')
        return true;
    return false;
#else
    if(token == Grammar::lambda)
        return false;
    for(size_t i = 0; i < token.length(); i++) {
        if(isupper(token[i]))
            return true;
    }
    return false;
#endif
}
/* ------------------------
Grammar LL method
-------------------------- */
map<string, bool> Grammar::mark_lambda() {
    bool 				rhs_derives_lambda;
    bool 				changes;
    Production 			p;
    
    derives_lambda.clear();
    
    /* initially, nothing is marked. */
    for(size_t i = 0; i < rules.size(); i++) {
        derives_lambda[rules[i].LHS] = false;
    }
    do {
        changes = false;
        for(size_t i = 0; i < rules.size(); i++) {
            p = rules[i];
            if(!derives_lambda[p.LHS]) {
                if(p.RHS.size() == 0 || p.RHS[0] == Grammar::lambda) {
                    changes = derives_lambda[p.LHS] = true;
                    continue;
                }
                /* does each part of RHS derive lambda ? */
                rhs_derives_lambda = derives_lambda[string(p.RHS[0])];
                for(size_t j = 1; j < p.RHS.size(); j++) {
                    rhs_derives_lambda &= derives_lambda[p.RHS[j]];
                }
                if(rhs_derives_lambda) {
                    changes = true;
                    derives_lambda[p.LHS] = true;
                }
            }
        }
    } while(changes);
    return derives_lambda;
}
void Grammar::fill_first_set() {
    
    string 		A; // nonterminal
    string 		a; // terminal
    Production 	p;
    bool 		changes;
        
    mark_lambda();
    first_set.clear();
    
    for(size_t i = 0; i < rules.size(); i++) {
        A = rules[i].LHS;
        if(derives_lambda[A])
            first_set[A].insert(Grammar::lambda);
    }
    
    for(size_t i = 0; i < rules.size(); i++) {
        for(size_t j = 0; j < rules[i].RHS.size(); j++) {
            a = rules[i].RHS[j];
            if(!isNonterminal(a)) {
                if(a != Grammar::lambda)
                    first_set[a].insert(a);
                if(j == 0) { // A -> aXX
                    first_set[rules[i].LHS].insert(a);
                }
            }
        }
    }
    
    do {
        changes = false;
        for(size_t i = 0; i < rules.size(); i++) {
            p = rules[i];
            set<string> rfirst = compute_first(p.RHS);
            size_t oldsize = first_set[p.LHS].size();
            first_set[p.LHS].insert(rfirst.begin(), rfirst.end());
            size_t newsize = first_set[p.LHS].size();
            if(oldsize != newsize)
                changes = true;
        }
    } while(changes);
} 
void Grammar::fill_follow_set() {
    string 	A, B; // nonterminal
    Production 	p;
    bool 	changes;
    
    for(size_t i = 0; i < rules.size(); i++) {
        A = rules[i].LHS;
        follow_set[A].clear();
    }
    
    follow_set[start_symbol].insert(Grammar::lambda);
        
    do {
        changes = false;
        for(size_t i = 0; i < rules.size(); i++) {
            /* A -> a B b
             * I.e. for each production and each occurrence
             * of a nonterminal in its right-hand side. 
             */
            p = rules[i];
            A = p.LHS;
            for(size_t j = 0; j < p.RHS.size(); j++) {
                B = p.RHS[j];
                if(isNonterminal(B)) {
                    vector<string> beta(p.RHS.begin() + j + 1, p.RHS.end());
                    set<string> rfirst = compute_first(beta);
                    size_t oldsize = follow_set[B].size();
                    
                    if(rfirst.find(Grammar::lambda) == rfirst.end()) {
                        follow_set[B].insert(rfirst.begin(), rfirst.end());	
                    } else {
                        rfirst.erase(Grammar::lambda);
                        follow_set[B].insert(rfirst.begin(), rfirst.end());	
                        rfirst = follow_set[A];
                        follow_set[B].insert(rfirst.begin(), rfirst.end());
                    }
                    size_t newsize = follow_set[B].size();			
                    if(oldsize != newsize)
                        changes = true;
                }
            }
        }
    } while(changes);
}
void Grammar::lldriver(queue<string> tokens) {
    stack<string> 	stk;
    string 			X;
    string			a;
    Production		p;
    /* Push the Start Symbol onto an empty stack */
    stk.push(start_symbol);
    
    while(!stk.empty() && !tokens.empty()) {
        X = stk.top();
        a = tokens.front();
        // cout << X << " " << a << endl;
        if(isNonterminal(X) && lltable[X].find(a) != lltable[X].end()) {
            p = lltable[X][a];
            stk.pop();
            for(int i = p.RHS.size() - 1; i >= 0; i--) {
                if(p.RHS[i] == Grammar::lambda)
                    continue;
                stk.push(p.RHS[i]);
            }
        } else if(X == a) {
            stk.pop();
            tokens.pop();
        } else if(lltable[X].find(Grammar::lambda) != lltable[X].end()) {
            stk.pop();
        } else {
            /* Process syntax error. */
            puts("Bad!");
            return;
        }
    }
    while(!stk.empty()) {
        X = stk.top();
        if(lltable[X].find(Grammar::lambda) != lltable[X].end())
            stk.pop();
        else
            break;
    }
    if(tokens.size() == 0 && stk.size() == 0)
        puts("Good");
    else
        puts("Bad!");
    return;
}
/* ------------------------
Grammar LR method
-------------------------- */
void Grammar::build_action() {
    ConfigurationSet 	s;
    Production 			P;
    int					dotPos;
    set< pair<Production, ConfigurationSet::State> >::iterator it;
    
    for(size_t i = 0; i < LRstates.size(); i++) {
        s = LRstates[i];
        int reduce = 0, rule = 0, accept = 1;
        for(it = s.configs.begin(); it != s.configs.end(); it++) {
            P = it->first, dotPos = it->second.dot;
            if(dotPos == P.RHS.size())
                reduce++, rule = P.label;
            accept &= P.LHS == Grammar::start_symbol;
        }
        if(accept == 1)
            action_table[i] = 0;
        else if(reduce == 1)
            action_table[i] = -1;
        else
            action_table[i] = 1;
    }
#ifdef DEBUG
    printf("State |");
    for(size_t i = 0; i < LRstates.size(); i++)
        printf("%5d|", i);
    puts("");
    printf("Action|");
    for(size_t i = 0; i < action_table.size(); i++) {
        printf("%5d|", action_table[i]);
    }
    puts("");
#endif
}
void Grammar::build_CFSM() {
    set<ConfigurationSet> 	S;
    queue<ConfigurationSet>	Q;
    ConfigurationSet 		s0, sb;
    int 					label = 0;
    ConfigurationSet::State state;
    
    state.dot = 0;
    state.lookahead = vector<string>();
    state.lookahead.push_back(Grammar::lambda);
    for(size_t i = 0; i < rules.size(); i++) {
        if(rules[i].LHS == this->start_symbol) {
            s0.configs.insert(make_pair(rules[i], state));
        }
    }
    s0 = ConfigurationSet::closure0(s0, *this);
    s0.label = label++;
    
    S.insert(s0);
    Q.push(s0);
    
    buildSymbols();
    /* hw need */
    map<int, vector< pair<int, string> > > hwPrint;
    /* hw need */
    while(!Q.empty()) {
        s0 = Q.front(), Q.pop();
        LRstates.push_back(s0);
        for(set<string>::iterator it = symbols.begin();
            it != symbols.end(); it++) {
            sb = ConfigurationSet::go_to0(s0, *it, *this);
            if(sb.configs.size() > 0) {
                if(S.find(sb) == S.end()) {
                    sb.label = label++;
                    S.insert(sb);
                    Q.push(sb);
                }
                
                go_to_table[s0.label][*it] = (* S.find(sb)).label;
                /* hw need */
                hwPrint[(* S.find(sb)).label].push_back(make_pair(s0.label, *it));
            }
        }
    }
    // build_action();
#ifdef DEBUG	
    printf("Total State: %d\n", label);
    for(int i = 0; i < label; i++) {
        if(hwPrint[i].size() > 0) {
            printf("State %d from", i);
            for(vector< pair<int, string> >::iterator it = hwPrint[i].begin();
                it != hwPrint[i].end(); it++) {
                printf("%cState %d(%s)", it == hwPrint[i].begin() ? ' ' : ',', it->first, it->second.c_str());
            }
            puts("");
        } else {
            printf("State %d\n", i);
        }
        LRstates[i].print(*this);
        puts("");
    }
#endif
}
int Grammar::slr1driver(queue<string> tokens) {
    stack<int> 		stateStk;
    stack<string> 	tokenStk;
    int 			state;
    string			X;
    
    stateStk.push(0); /* push start state */
    while(!tokens.empty()) {
        state = stateStk.top();
        X = tokens.front();
#ifdef DEBUG 
        puts("");
        printf("state %d front %s\n", state, X.c_str());
        LRstates[state].print(*this);
        for (std::stack<int> dump = stateStk; !dump.empty(); dump.pop())
        	std::cout << "state stack "<< dump.top() << '\n';
        for (std::stack<string> dump = tokenStk; !dump.empty(); dump.pop())
        	std::cout << "token stack "<< dump.top() << '\n';
#endif
        int reduce = 0, shift = 0;
        Production P;
        for(set< pair<Production, ConfigurationSet::State> >::iterator it = LRstates[state].configs.begin(); 
            it != LRstates[state].configs.end(); it++) {
            Production q = it->first;
            ConfigurationSet::State s = it->second;
            if(follow_set[q.LHS].find(X) != follow_set[q.LHS].end() && 
                    (s.dot == q.RHS.size() || q.RHS[0] == Grammar::lambda)) {
                reduce++;
                P = q;
            }
        }
        if(go_to_table[state].find(X) != go_to_table[state].end())
            shift++;
        if(reduce + shift >= 2)
            assert(false); // grammar can't use simple LR.
        if(reduce + shift == 0)
            return 0;
        if(reduce == 1) { // Reduce
            for(size_t i = 0; i < P.RHS.size(); i++) 
                tokenStk.pop(), stateStk.pop();
            tokenStk.push(P.LHS);
            state = stateStk.top();
            if(go_to_table[state].find(P.LHS) == go_to_table[state].end()) {
                return 0;
            }
            state = go_to_table[state][P.LHS];
            stateStk.push(state);
        } else { // shift
            state = go_to_table[state][X];
            stateStk.push(state);
            tokenStk.push(X);
            tokens.pop();
        }
    }
    while(!stateStk.empty()) {
        state = stateStk.top();
        X = Grammar::lambda;
#ifdef DEBUG 
        puts("");
        printf("state %d front %s\n", state, X.c_str());
        LRstates[state].print(*this);
        for (std::stack<int> dump = stateStk; !dump.empty(); dump.pop())
        	std::cout << "state stack "<< dump.top() << '\n';
        for (std::stack<string> dump = tokenStk; !dump.empty(); dump.pop())
        	std::cout << "token stack "<< dump.top() << '\n';
#endif
        int reduce = 0, shift = 0;
        Production P;
        for(set< pair<Production, ConfigurationSet::State> >::iterator it = LRstates[state].configs.begin(); 
            it != LRstates[state].configs.end(); it++) {
            Production q = it->first;
            ConfigurationSet::State s = it->second;
            if(follow_set[q.LHS].find(X) != follow_set[q.LHS].end() && 
                    (s.dot == q.RHS.size() || q.RHS[0] == Grammar::lambda)) {
                reduce++;
                P = q;
            }
        }
        if(go_to_table[state].find(X) != go_to_table[state].end())
            shift++;
        if(reduce + shift >= 2)
            assert(false); // grammar can't use simple LR.
        if(reduce + shift == 0)
            return 0;
        if(reduce == 1) { // Reduce
            for(size_t i = 0; i < P.RHS.size(); i++) 
                tokenStk.pop(), stateStk.pop();
            tokenStk.push(P.LHS);
            state = stateStk.top();
            if(go_to_table[state].find(P.LHS) == go_to_table[state].end()) {
                if(P.LHS == Grammar::start_symbol)
                    return 1;
                return 0;
            }
            state = go_to_table[state][P.LHS];
            stateStk.push(state);
        } else { // shift
            state = go_to_table[state][X];
            stateStk.push(state);
            tokenStk.push(X);
            tokens.pop();
        }
    }
    return 0;
}
void parsingProduction(string r, Grammar &g) {
    static int 		production_label = 0;
    stringstream 	sin(r);
    string 			lhs, foo;
    vector<string> 	tokens;
    sin >> lhs >> foo;
    while(sin >> foo)
        tokens.push_back(foo);
    Production p(lhs, tokens);
    p.label = ++production_label;
    g.rules.push_back(p);
}
bool isNumber(string str) {
    for(int i = 0; i < str.length(); i++) {
        if(!isdigit(str[i]))
            return false;
    }
    return true;
}
int scanTokens(char s[], queue<string>& tokens, vector<string>& val) {
    string keyword[18] = {"AND", "THEN", "GO", "KEEP", 
            "RIGHT", "LEFT", "FIRST", "SECOND", "THIRD", 
            "AT", "RECORD", "TIME", "TO", "KMH", "CHANGE",
            "AVERAGE", "SPEED", "CAS"};
    for(int i = 0; s[i]; i++) {
        if(s[i] == '"') {
            // s-word can't empty, and after the opening speech marks no more space.
            if(s[i + 1] == '"' || isspace(s[i + 1]))	
                return 0;
            i++;
            while(s[i] != '"') {
                if(isupper(s[i])) {}
                else if(isspace(s[i])) {s[i] = '_';}
                else if(s[i] == '.') {
                    if(isspace(s[i - 1]) || s[i - 1] == '_') {
                        return 0;
                    }
                } else {
                    return 0;
                }
                i++;
            }
            if(s[i] == '\0' || isspace(s[i - 1]) || s[i - 1] == '_')
                return 0;
        }
    }
    stringstream 	sin(s);
    string 			token;
    while(sin >> token) {
        int f = 0;
        for(int i = 0; i < 18; i++) {
            if(token == keyword[i])
                tokens.push(token), val.push_back(token), f = 1;
        }
        if(f)	continue;
        if(token[0] == '"')
            tokens.push("SIGNWORDS"), val.push_back(token), f = 1;
        if(f)	continue;
        if(isNumber(token))
            tokens.push("NNN"), val.push_back(token), f = 1;
        if(f)	continue;
        return 0;
    }
    return 1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    Grammar g;
    parsingProduction("<instruction> 	-> <navigational>", g);
    parsingProduction("<instruction> 	-> <time-keeping>", g);
    parsingProduction("<instruction> 	-> <navigational> AND <time-keeping>", g);
    parsingProduction("<navigational> 	-> <directional>", g);
    parsingProduction("<navigational> 	-> <navigational> AND THEN <directional>", g);
    parsingProduction("<directional> 	-> <how> <direction>", g);
    parsingProduction("<directional> 	-> <how> <direction> <where>", g);
    parsingProduction("<how> 			-> GO", g);
    parsingProduction("<how> 			-> GO <when>", g);
    parsingProduction("<how>			-> KEEP", g);
    parsingProduction("<direction> 		-> RIGHT", g);
    parsingProduction("<direction>		-> LEFT", g);
    parsingProduction("<when>			-> FIRST", g);
    parsingProduction("<when>			-> SECOND", g);
    parsingProduction("<when>			-> THIRD", g);
    parsingProduction("<where> 			-> AT <sign>", g);
    parsingProduction("<sign>			-> SIGNWORDS", g);
    parsingProduction("<time-keeping> 	-> <record>", g);
    parsingProduction("<time-keeping>	-> <change>", g);
    parsingProduction("<record>			-> RECORD TIME", g);
    parsingProduction("<change>			-> <cas> TO NNN KMH", g);
    parsingProduction("<cas>			-> CHANGE AVERAGE SPEED", g);
    parsingProduction("<cas> 			-> CAS", g);
    g.start_symbol = "<instruction>";
        
    g.fill_first_set();
    g.fill_follow_set();
    g.build_CFSM();
    
    char 	line[1024];
    int 	cases = 0;
    while(gets(line)) {
        if(!strcmp(line, "#"))
            break;
        queue<string> tokens;
        vector<string> val;
        int f = scanTokens(line, tokens, val);
        printf("%3d.", ++cases);
        if(!f) {
            puts(" Trap!");
            continue;
        }
        f = g.slr1driver(tokens);
        if(!f) {
            puts(" Trap!");
            continue;
        }
        for(int i = 0; i < val.size(); i++) {
            if(val[i][0] == '"')
                for(int j = 0; j < val[i].length(); j++)
                    if(val[i][j] == '_')
                        val[i][j] = ' ';
            printf(" %s", val[i].c_str());
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 345 - It's Ir-Resist-Able

Problem

A common component in electronic circuits is the resistor. Each resistor has two terminals, and when current flows through a resistor, some of it is converted to heat, thus ``resisting”; the flow of the current. The extent to which it does this is indicated by a single positive numeric value, cleverly called the resistance of the resistor. By the way, the units of resistance are Ohms. Here’s what a single resistor looks like in a diagram of an electronic circuit:

When two resistors are connected in series, as shown below, then their equivalent resistance is just the sum of the resistances of the individual resistors. For example, if the two resistors below had resistances of 100 and 200 Ohms, respectively, then the combined resistance (from point A to point B) would be 300 Ohms. Of course, combining three or more resistors in series would yield a resistance equal to sum of all the individual resistances.

Resistors may also be connected in parallel, like this:

If these two resistors had resistances of 100 and 150 Ohms, then the parallel combination would yield an equivalent resistance between points A and B of

displaymath61

Connecting three resistors in parallel uses the same rule, so a 100 Ohm, 150 Ohm, and 300 Ohm resistor in parallel would yield a combined resistance of just 50 Ohms: that is,

displaymath63

In this problem you’re provided one or more descriptions of resistors and their interconnections. Each possible interconnection point (the terminals of a resistor) is identified by a unique positive integer, its label. And each resistor is specified by giving its two interconnection point labels and its resistance (as a real number).

For example, the input

1 2 100

would tell us that a 100 Ohm resistor was connected between points 1 and 2. A pair of resistors connected in series might be specified like this:

1 2 100
2 3 200

Here we’ve got our 100 Ohm resistor connected at points 1 and 2, and another 200 Ohm resistor connected to points 2 and 3. Two resistors in parallel would be similarly specified:

1 2 100
1 2 150

Once you know how the resistors are interconnected, and the resistance of each resistor, it’s possible to determine the equivalent resistance between any two points using the simple rules given above. In some cases, that is. Some interconnections of resistors can’t be solved using this approach: you won’t encounter any of these in this problem, however.

Notes

  • Be aware that there may be input test cases with some resistors that don’t contribute to the overall resistance between the indicated points. For example, in the last case shown in the Sample Input section below, the resistor between points 1 and 2 is unused. There must be some flow through a resistor if it is to contribute to the overall resistance.
  • No resistor will have its ends connected together. That is, the labels associated with the ends of a resistor will always be distinct.

Input

There will be one or more cases to consider. Each will begin with a line containing three integers N, A, and B. A and B indicate the labels of points between which you are to determine the equivalent resistance. N is the number of individual resistors, and will be no larger than 30. N, A and B will all be zero in the line following the last case. Following each N A B line will be N lines, each specifying the labels of the points where a resistor is connected, and the resistance of that resistor, given as a real number.

Output

For each input case, display a line that includes the case number (they are numbered sequentially starting with 1) and the equivalent resistance, accurate to two decimal places.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 1 3
1 2 100
2 3 200
2 1 2
1 2 100
1 2 150
6 1 6
1 2 500
1 3 15
3 4 40
3 5 100
4 6 60
5 6 50
0 0 0

Sample Output

1
2
3
Case 1: 300.00 Ohms
Case 2: 60.00 Ohms
Case 3: 75.00 Ohms

Solution

題目描述：

給定指定的兩個端點 A B，接著會有 N 個電阻，每個電阻值位於端點 X Y 之間。
求 A B 之間的等效電阻，特別注意到端點編號是任意整數，並且有可能兩個端點相同 (A = B)，也有可能會有無會流經的電路區域。

題目解法：

我們假設每個端點的電動勢 (Volt)，使用克希荷夫電路定律（Kirchhoff Circuit Laws）中的 電流定律 ，得到下列公式。

對於每一個端點而言，入電流總量等於出電流總量：

$\sum_{j = 1}^{n} \frac{V_{j} - V_{i}}{R_{i, j}} = 0$

但是題目給定的起點和終點並不會在其中，因此假設起點 V[A] = INF，終點 V[B] = 0，接著算出其他所有點的電動勢。共有 n - 2 條方程式，n - 2 個變數，使用高斯消去求解。

  • 必須預處理與起點、終點之間的電流關係。
  • 特別注意到起點和終點相同，直接輸出等效電阻 0。
  • 端點編號離散化集中處理。
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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <iostream>
using namespace std;
// learn: http://blog.csdn.net/jiangshibiao/article/details/28661223		
#define MAXN 105
#define INF 1e+6
#define eps 1e-9
double R[MAXN][MAXN] = {}, V[MAXN] = {}; // R: resist, V: voltage
double f[MAXN][MAXN] = {}; // function need solved;
int main() {
    int N, A, B;
    int x, y, l;
    int cases = 0;
    double w;
    char s1[105], s2[105];
    while(scanf("%d %d %d", &N, &A, &B) == 3) {
        if(N == 0)
            break;
        map<int, int> label;
        l = label[A];
        if(l == 0)	label[A] = label.size();
        A = label[A];
        
        l = label[B];
        if(l == 0)	label[B] = label.size();
        B = label[B];
        
        memset(R, 0, sizeof(R));
        memset(V, 0, sizeof(V));
        memset(f, 0, sizeof(f));
        vector<double> g[MAXN][MAXN];
        for(int i = 0; i < N; i++) {
            scanf("%d %d %lf", &x, &y, &w);
            
            l = label[x];
            if(l == 0)	label[x] = label.size();
            x = label[x];
            
            l = label[y];
            if(l == 0)	label[y] = label.size();
            y = label[y];
            
            g[x][y].push_back(w);
            g[y][x].push_back(w);
        }
        N = label.size();
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(g[i][j].size()) {
                    double r = 0;
                    for(int k = 0; k < g[i][j].size(); k++) {
                        r += 1.0 / g[i][j][k];
                    }
                    R[i][j] = 1.0 / r;
                }
            }
        }
        V[A] = INF, V[B] = 0;
        for(int i = 1; i <= N; i++) {
            if(i == A)	continue;
            if(i == B)	continue;
            if(R[i][A] > 0)
                f[i][i] -= 1.0 / R[i][A], f[i][N + 1] -= V[A] / R[i][A];
            if(R[i][B] > 0)
                f[i][i] -= 1.0 / R[i][B], f[i][N + 1] -= V[B] / R[i][B];
            for(int j = 1; j <= N; j++) {
                if(R[i][j] > 0 && i != j && j != A && j != B)
                    f[i][j] = 1.0 / R[i][j], f[i][i] -= 1.0 / R[i][j];
            }
        }
        // Gaussian Elimination
        for(int i = 1; i <= N; i++) {
            int k = i;
            for(int j = i + 1; j <= N; j++)
                if(f[j][i] > 0)
                    k = j;
            if(fabs(f[k][i]) < eps)
                continue;
            for(int j = 1; j <= N + 1; j++)
                swap(f[i][j], f[k][j]);
            for(int j = 1; j <= N; j++) {
                if(i == j)	continue;
                for(int k = N + 1; k >= i; k--)
                    f[j][k] = f[j][k] - f[j][i] / f[i][i] * f[i][k];
            }
        }
        for(int i = 1; i <= N; i++) {
            if(i == A)	continue;
            if(i == B)	continue;
            if(fabs(f[i][i]) > eps)
                V[i] = f[i][N + 1] / f[i][i];
        }
        
        double IB = 0;
        for(int i = 1; i <= N; i++)
            if(R[i][B] > 0)
                IB += V[i] / R[i][B];
        if(fabs(IB) < eps)
            printf("Case %d: %.2lf Ohms\n", ++cases, 0);
        else
            printf("Case %d: %.2lf Ohms\n", ++cases, (V[A] - V[B]) / IB);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 313 - Intervals

Problem

In the ceiling in the basement of a newly open developers building a light source has been installed. Unfortunately, the material used to cover the floor is very sensitive to light. It turned out that its expected life time is decreasing dramatically. To avoid this, authorities have decided to protect light sensitive areas from strong light by covering them. The solution was not very easy because, as it is common, in the basement there are different pipelines under the ceiling and the authorities want to install the covers just on those parts of the floor that are not shielded from the light by pipes. To cope with the situation, the first decision was to simplify the real situation and, instead of solving the problem in 3D space, to construct a 2D model first.

Within this model, the x-axis has been aligned with the level of the floor. The light is considered to be a point light source with integer co-ordinates tex2html_wrap_inline36 . The pipes are represented by circles. The center of the circle i has the integer co-ordinates tex2html_wrap_inline40 and an integer radius tex2html_wrap_inline42 . As pipes are made from solid material, circles cannot overlap. Pipes cannot reflect the light and the light cannot go through the pipes. You have to write a program which will determine the non-overlapping intervals on the x-axis where there is, due to the pipes, no light from the light source.

Input

The input file consists of blocks of lines, each of which except the last describes one situation in the basement. The first line of each block contains a positive integer number N < 500 expressing the number of pipes. The second line of the block contains two integers tex2html_wrap_inline48 and tex2html_wrap_inline50 separated by one space. Each of the next N lines of the block contains integers tex2html_wrap_inline54 , tex2html_wrap_inline56 and tex2html_wrap_inline42 , where tex2html_wrap_inline60 . Integers in individual lines are separated by one space. The last block consists of one line containing n = 0.

Output

The output file consists of blocks of lines, corresponding to the blocks in the file (except the last one). One empty line must be put after each block in the output file. Each of the individual lines of the blocks in the output file will contain two real numbers, the endpoints of the interval where there is no light from the given point light source. The reals are exact to two decimal places and separated by one space. The intervals are sorted according to increasing x-coordinate.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
6
300 450
70 50 30
120 20 20
270 40 10
250 85 20
220 30 30
380 100 100
1
300 300
300 150 90
1
300 300
390 150 90
0

Sample Output

1
2
3
4
5
6
7
0.72 78.86
88.50 133.94
181.04 549.93
75.00 525.00
300.00 862.50

Solution

題目描述：

現在天花板上面有一盞燈，然後下方有數個圓，請問陰影部分的區間由小至大輸出分別為何。
假設不會有圓的高度大於燈的位置，而陰影呈現在 x 軸上。

題目解法：

求圓 (cx, cy, r) 外一點的切線，由於點 (a, b) 在圓外，通常此點切於圓的線會有兩條。

假設該線斜率為 m，則通過的線為 y = m * (x - a) + b。

藉由點線距公式 |m * (cx - a) - cy + b |/sqrt(m*m + 1) = r，求得 m 之後得到兩條切線，往後求交 x 軸的位置即可。(特別考慮 m 不存在的情況)

最後使用掃描線算法來算聯集。

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 <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int main() {
    int N;
    double bx, by, cx, cy, cr;
    while (scanf("%d", &N) == 1 && N) {
    	scanf("%lf %lf", &bx, &by);
        vector< pair<double, double> > interval;
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf %lf", &cx, &cy, &cr);
            double a, b, c;
            a = (cx - bx) * (cx - bx) - cr * cr;
            b = 2 * (cx - bx) * (by - cy);
            c = (by - cy) * (by - cy) - cr * cr;
            if (b * b - 4 * a * c > 0) {
#define eps 1e-6
                if (fabs(a) > eps) {
                    double m1 = (-b + sqrt(b * b - 4 * a * c))/(2 * a);
                    double m2 = (-b - sqrt(b * b - 4 * a * c))/(2 * a);
                    double l, r;
                    c = by - m1 * bx;
                    l = -c / m1;
                    c = by - m2 * bx;
                    r = -c / m2;
                    if (l >= r)
                        swap(l, r);
                    interval.push_back(make_pair(l, r));
                } else {
                    double m1 = -c / b;
                    double l, r;
                    c = by - m1 * bx;
                    l = -c / m1;
                    r = bx;
                    if (l >= r)
                        swap(l, r);
                    interval.push_back(make_pair(l, r));
                }
            }
        }
        sort(interval.begin(), interval.end());
        double coverL, coverR;
        coverL = interval[0].first;
        coverR = interval[0].second;
        for (int i = 0; i < interval.size(); i++) {
            if (interval[i].first <= coverR) {
                coverR = max(coverR, interval[i].second);
            } else {
                printf("%.2lf %.2lf\n", coverL, coverR);
                coverL = interval[i].first;
                coverR = interval[i].second;
            }
        }
        printf("%.2lf %.2lf\n", coverL, coverR);
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10118 - Free Candies

The Problem

Little Bob is playing a game. He wants to win some candies in it - as many as possible.

There are 4 piles, each pile contains N candies. Bob is given a basket which can hold at most 5 candies. Each time, he puts a candy at the top of one pile into the basket, and if there’re two candies of the same color in it ,he can take both of them outside the basket and put them into his own pocket. When the basket is full and there are no two candies of the same color, the game ends. If the game is played perfectly, the game will end with no candies left in the piles.

For example, Bob may play this game like this (N=5):

Step1 Initial Piles Step2 Take one from pile #2
Piles Basket Pocket Piles Basket Pocket

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

nothing     nothing

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

2     nothing

Step3 Take one from pile #2 Step4 Take one from pile #3
Piles Basket Pocket Piles Basket Pocket

1 3 4
1 6 7
2 3 3 3
4 9 8 6
8 7 2 1

2 5     nothing

1 4
1 6 7
2 3 3 3
4 9 8 6
8 7 2 1

2 3 5     nothing

Step5 Take one from pile #2 Step6 put two candies into his pocket
Piles Basket Pocket Piles Basket Pocket

1 4
1 6 7
2 3 3
4 9 8 6
8 7 2 1

2 3 3 5     nothing

1 4
1 6 7
2 3 3
4 9 8 6
8 7 2 1

2 5     a pair of 3

Note that different numbers indicate different colors, there are 20 kinds of colors numbered 1..20.

‘Seems so hard…’Bob got very much puzzled. How many pairs of candies could he take home at most?

The Input

The input will contain no more than 10 test cases. Each test case begins with a line containing a single integer n(1<=n<=40) representing the height of the piles. In the following n lines, each line contains four integers xi1,xi2,xi3,xi4 (in the range 1..20). Each integer indicates the color of the corresponding candy. The test case containing n=0 will terminate the input, you should not give an answer to this case.

The Output

Output the number of pairs of candies that the cleverest little child can take home. Print your answer in a single line for each test case.

Sample Input

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

Sample Output

1
2
3
8
0
3

Solution

題目描述：

現在盤面上共有 4 堆，每一堆呈現 stack 的方式，並且每一堆都會有 n 個糖果，接下來每一步將會把每一堆的 top 糖果放入籃子中，假使籃子中有相同編號的糖果，則會將這兩個相同編號的糖果收入口袋。請問到籃子滿 5 個糖果之前，最多有多少對的糖果可以帶回家。

題目解法：

將搜索狀態進行標記，之後走訪遇到相同狀態直接退回。這個問題在相同狀態下的結果必然相同。

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
#include <stdio.h> 
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 45
int N, pile[4][MAXN];
int used[MAXN][MAXN][MAXN][MAXN] = {}, testcase = 0;
int dp[MAXN][MAXN][MAXN][MAXN];
int dfs(int p1, int p2, int p3, int p4, int state) {
    if(__builtin_popcount(state) == 5)
        return 0;
    if(used[p1][p2][p3][p4] == testcase)
        return dp[p1][p2][p3][p4];
    used[p1][p2][p3][p4] = testcase;
    int &ret = dp[p1][p2][p3][p4];
    int t, v;
    ret = 0;
    if(p1 < N) {
        t = pile[0][p1];
        v = (state>>t)&1;
        ret = max(ret, v + dfs(p1+1, p2, p3, p4, state^(1<<t)));
    }
    if(p2 < N) {
        t = pile[1][p2];
        v = (state>>t)&1;
        ret = max(ret, v + dfs(p1, p2+1, p3, p4, state^(1<<t)));
    }
    if(p3 < N) {
        t = pile[2][p3];
        v = (state>>t)&1;
        ret = max(ret, v + dfs(p1, p2, p3+1, p4, state^(1<<t)));
    }
    if(p4 < N) {
        t = pile[3][p4];
        v = (state>>t)&1;
        ret = max(ret, v + dfs(p1, p2, p3, p4+1, state^(1<<t)));
    }
    return ret;
}
int main() {
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < 4; j++)
                scanf("%d", &pile[j][i]);
        testcase++;
        int ret = dfs(0, 0, 0, 0, 0);
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12598 - Starting School

Problem

The first day of school is a very memorable day to everyone. Po is starting school from today and Po is very excited. As this is Po’s first day at school, no one is assigned roll number yet. So all the students form a line in the school field and they are being assigned roll number one by one. The teacher is a bit crazy. Instead of assigning roll number from 1, she starts assigning them one by one in a random fashion. Po watches this madness for the first K students and then steps up. Po says Po can assign them very easily for the rest of the students. The idea is very simple. Roll number should be unique and a student should get the smallest roll number that has not been assigned yet to any of the students. For example if K = 4, total number of students are 10 and the first K students’ roll numbers are 1, 3, 5, 10 then the next 6 roll numbers should be 2, 4, 6, 7, 8 and 9.

開學第一天是值得紀念的，Po 從今天開始在這所學校上課，他相當地興奮。Po 到達學校的第一天，沒有人被指派座號，因此所有的學生都在操場上等著被一個接著一個發送座號。老師有點喪心病狂，一開始從 1 號開始發送，但是他採用隨機發送，並沒有按著順序發。Po 看到前 K 位同學被這麼發送，Po 認為自己可以發送剩餘的學生編號，而發送方式相當簡單，將剩餘的最小座號發送給當前編號最小 (一開始規定學生編號為 1 - n) 的學生。

K = 4，一開始指派編號給 1 3 5 10 的學生座號，而剩餘座號就是發送順序為 2 4 6 7 8 9。

Though this is a very good idea, the teacher got mad at Po. So she starts asking the roll number for various students. As there are many students, Po is feeling helpless. Can you help Po?

Input

First line will contain an integer T (T <= 30), the number of test cases. Each case will start with three integers N (0 < N <= 109), K (0 < K <= 50,000 and K <= N) and Q (0 < Q <= 50,000). N is the total number of students, K is described earlier and Q is the number of queries of the crazy teacher. Next line will contain K distinct integers, the first K roll number assigned by the teacher. These values will be between 1 and 1000000000 (inclusive). Next will be Q integers, each indicating a position of students. These values will be between 1 and N (inclusive). (Large input output file, use faster I/O)

Output

For each case print one line “Case T:” where T is the case number. Then for each query print one line with the roll number of the student standing on the queried position. See sample I/O for clarity.

Sample Input

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

Output for Sample Input

1
2
3
4
5
6
7
8
Case 1:
4
6
9
10
Case 2:
2
8

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int A[65536], B[65536], C[65536], D[65536];
int main() {
    int testcase, cases = 0, N, K, Q;
    int x, l, r;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &N, &K, &Q);
        for(int i = 1; i <= K; i++)
            scanf("%d", &A[i]), B[i] = A[i];
        sort(B + 1, B + 1 + K);
        B[0] = 0, B[K+1] = N + 1;
        int M = 1;
        C[0] = 0;
        for(int i = 1; i <= K + 1; i++) {
            l = B[i - 1] + 1, r = B[i] - 1;
            if(l <= r) {
                C[M] = C[M - 1] + r - l + 1;
                D[M] = l;
                M++;
            }
        }
        printf("Case %d:\n", ++cases);
        while(Q--) {
            scanf("%d", &x);
            if(x <= K)
                printf("%d\n", A[x]);
            else {
                x -= K;
                int pos = lower_bound(C, C + M, x) - C;
                printf("%d\n", D[pos] + x - C[pos-1] - 1);
            }
        }
    }
    return 0;
}

加速 IO 的做法如下，優化輸入函數，以及反饋的二分搜索，但是排名還是沒有達到想要的目標。

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>
using namespace std;
int A[65536], B[65536], C[65536], D[65536];
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int testcase, cases = 0, N, K, Q;
    int x, l, r;
    ReadInt(&testcase);
    while(testcase--) {
        ReadInt(&N);
        ReadInt(&K);
        ReadInt(&Q);
        int *p = A + 1, *q = B + 1;
        for(int i = 1; i <= K; i++, p++, q++) {
            ReadInt(p), *q = *p;
        }
        sort(B + 1, B + 1 + K);
        B[0] = 0, B[K+1] = N + 1;
        int M = 1;
        C[0] = 0;
        p = B, q = p+1;
        for(int i = 1; i <= K + 1; i++, p = q++) {
            l = *p + 1, r = *q - 1;
            if(l <= r) {
                C[M] = C[M - 1] + r - l + 1;
                D[M] = l;
                M++;
            }
        }
        printf("Case %d:\n", ++cases);
        int prevX = 0, prevP = 0, pos;
        while(Q--) {
            ReadInt(&x);
            if(x <= K)
                printf("%d\n", A[x]);
            else {
                x -= K;
                if(x >= prevX)
                    pos = lower_bound(C + prevP, C + M, x) - C;
                else
                    pos = lower_bound(C, C + prevP, x) - C;
                printf("%d\n", D[pos] + x - C[pos-1] - 1);
                prevX = x, prevP = pos;
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11031 - Looking for a Subset

Problem

Given a set S = { a1, a2, a3, … , an }, you have to find a subset of S, P = { ax1, ax2, ax3, … , axm } such that ( x1 < x2 < … < xm ) and ( ax1< ax2< … < axm ). If there are several subsets possible then you should find the subset where x1 is minimum. If there is still a tie then check for the lowest x2 and so on.

Input

The input file contains several sets of inputs. The total number of test cases will be less than 25. The description of each set is given below:

Each case starts with two integers n (1 ≤ n ≤ 10000) and q (1 ≤ q ≤ 100), q is the number of queries. The next line contains n integers (seperated by a space) denoting a1, a2, a3, … , an respectively. And the next q lines, each contains an integer denoting m (1 ≤ m ≤ n). There is no number in the input file that contains more than 8 digits.

The input will be terminated by the case where n = q = 0. And this case should not be processed.

Output

For each case in the input, you should first print the case number starting from 1.
Then for each query first print the query number starting from 1. And for each m you have to find the result.
If there exists a subset as described above you should print the elements of the subset in a single line. The numbers should be seperated by a space.
Otherwise print ``Impossible’’ without the quotes.

See the sample input-output for more details. Output should be formatted like the sample output.

Sample Input

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

Output for Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
Set 1:
  Subset 1:
    Impossible
  Subset 2:
    1 2 3 6
  Subset 3:
    Impossible
Set 2:
  Subset 1:
    2 4 6
  Subset 2:
    Impossible

Solution

題目描述：

對於每次詢問 m，找到一個嚴格遞增的子序列，並且子序列長度等於 m 且字典順序最小。

題目解法：

基於每次字典順序最小，只能採用 greedy 的掃描方式，因此對於每次詢問必須到達 O(n)，無法在 O(m) 的時間完成。

關於貪心的操作，建造反向的遞減序列，狀態為 從這個位置為子序列的頭最長的遞減序列長度為何。

為了在 O(n log n) 得到 LDS 表格，這裡使用一個 binary indexed tree 來完成操作。

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
#include <stdio.h> 
#include <algorithm>
#include <map>
using namespace std;
#define maxN 10005
int A[maxN], LDS[maxN];
int BIT[maxN];
void modify(int i, int val, int L) {
    while(i <= L) {
        BIT[i] = max(BIT[i], val);
        i += i&(-i);
    }
}
int query(int i) {
    int ret = 0;
    while(i) {
        ret = max(ret, BIT[i]);
        i -= i&(-i);
    }
    return ret;
}
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int N, Q, M, u;
    int cases = 0;
    while(ReadInt(&N) && ReadInt(&Q) && N+Q) {
        map<int, int> R;
        for(int i = 0; i < N; i++) {
            ReadInt(A+i);
            R[A[i]] = 0;
        }
        for(int i = 1; i <= N; i++)
            BIT[i] = 0;
            
        int size = R.size();
        for(map<int, int>::iterator it = R.begin();
            it != R.end(); it++) {
            it->second = size--;
        }
        /* reverse LDS with ending at i-th element */
        int maxLDS = 0;
        for(int i = N-1; i >= 0; i--) {
            LDS[i] = query((u = R[A[i]]) - 1) + 1;
            modify(u, LDS[i], R.size());
            maxLDS = max(maxLDS, LDS[i]);
        }
        printf("Set %d:\n", ++cases);
        for(int i = 1; i <= Q; i++) {
            ReadInt(&M);
            printf("  Subset %d:\n", i);
            if(M > maxLDS) {
                printf("    Impossible\n");
                continue;
            }
            printf("   ");
            int prevA = -0x3f3f3f3f;
            for(int j = 0; j < N && M; j++) {
                if(LDS[j] >= M && prevA < A[j]) {
                    printf(" %d", A[j]);
                    M--, prevA = A[j];
                }
            }
            puts("");
        }
    }
    return 0;
}
Read More +