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

UVa 11638 - Temperature Monitoring

Problem

We have a device to monitor temperature. After configuring it, we place it inside the chamber whose temperature we wish to monitor. The device is equipped with four alarms each of which can be configured differently. The Alarms are identified by the numbers 1, 2, 3 and 4. The device takes a reading of its surrounding at a regular interval.

In this problem you will be simulating the behavior of such a device.

我們有一個監測溫度裝置，在安裝配置後，將其放入所要監控溫度的室內。這個裝置共有四個警報器，分別編號為 1, 2, 3, 4，這些警報器將會每隔固定一段時間進行溫度檢測。
在這個問題中，請模擬這裝置的行為。

Input

The first line of input contains a positive integer T<101, which denotes the number of test cases. Each case consists of several lines which are described below.

輸入第一行為測資筆數 T (T < 101)

The first line contains a positive integer M, which denotes the measurement interval. That is, the device takes a reading every M seconds.

每一組測資第一行為一個正整數 M，表示裝置每隔 M 秒會進行偵測。

The second line contains a non-negative integer S, which denotes the ‘Startup delay’. This is the amount of time that the device will remain idle after placing inside the chamber before it takes its first reading. The device will instantly take a reading when the ‘Startup delay’ ends.

第二行為一個非負整數 S，表示裝置在前 S 秒正在安裝，這段時間機器將不會進行偵測，在安裝完後，將會立即地進行檢測。

The third line contains four integers. The integers give the threshold temperature for alarm 1,2,3,4 respectively. Here threshold temperature means, when a recorded temperature crosses this temperature the corresponding alarm will be triggered.

第三行會有 4 個正整數，分別表示警報器 1, 2, 3, 4 的警報閥值 (根據閥值進行溫度比較)

The fourth line contains a non-negative integer C. The least significant 8 bits of this integer represents the configurations of the four alarms. The rightmost 4 bits (bit 0 to 3) determine if the alarms are enabled(bit value 1) or disabled(bit value 0). For example, if the bits are set as 0011, this means Alarm 1 and 2 are enabled and Alarm 3 and 4 are disabled. If an alarm is disabled, it will never be triggered.

第四行將會有一個非負整數 C，用最低的 8 個 bits 表示警報器的設定，最右邊的 4 個 bits (bit 0 to bit 3) 表示警報器是否有啟動 (1 表示有啟動，反之則否)，例如 0011 表示警報器 1, 2 被啟動，3, 4 則沒有被啟動。如果警報器沒有被啟動，則將不會被觸發。

The next 4 bits(bits 4 to 7) determine the triggering type of each alarm. A value of 0 means, it’s a low trigger and a value of 1 means it’s a high trigger. For example, if the bits are set as 1100, this means Alarm 1 and 2 are set for low trigger and Alarm 3 and 4 for high trigger. Here high trigger means if a recorded temperature is above the set threshold temperature for an alarm, it will be triggered. Similarly, a Low trigger means if a recorded temperature is below the set threshold temperature for an alarm, that alarm will be triggered.

接下來的 4 個 bits 將會決定警報器的類型，亦即表示 1 高觸發 (大於閥值觸發) 0 表示低觸發 (低於閥值觸發)。例如 1100，警報器 1, 2 將會是低觸發，3, 4 則會是高觸發。

The fifth line contains a positive integer K<=100. The following K lines contain a pair of integers each in the format time temp. Here time represents the duration of a period with constant temperature and temp indicates the temperature of the environment in that period. Note that, time is always positive. The time value of first pair indicates the period immediately following the placement of the device inside the environment to be monitored. Successive time values indicate the duration of periods in the order they occur. The temperature at the border regions is considered to be that of the period just ending. Also, the temperature at the very beginning is that of the first period. Every value in the input will fit in 32 bit signed integer.

第五行將會有一個正整數 K，表示接下來依序發生的時間情況。將會從時間 0 開始，依序播報 (duration, temp) 表示新的溫度持續多久 (duration)。假設所有數據皆可以在 32 bits 內。

Output

For each case of input, there will be one line of output. It will first contain the case number, followed by the triggering status of each of the four alarms. The triggering status will contain four strings of either yes or no, separated by a space. The first string will be yes if alarm 1 was triggered at least once and no otherwise. The second string will be the status of alarm 2 and so on. Look at the sample output for exact formatting.

Sample Input

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

Output for Sample Input

1
2
Case 1: no no no yes
Case 2: no no no no

Solution

題目相當令人討厭，因為區間涵蓋沒有講得很清楚。

但是最後可以明白的是

[ti, tj][tj, tk] 其中 ti < tj < tk，我們在討論觸發的時候，端點是需要被考慮的。

詳細操作，詳見代碼。

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> 
int main() {
	int testcase, cases = 0;
	int M; /* the device takes a reading every M seconds. */
	int S; /* The device will instantly take a reading when the ‘Startup delay’ ends. */
	int threshold[4]; /* */
	int C; /* */
	int enable[4], trigger[4]; /* trigger 0 <, 1 > */
	int K, time, temp;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d", &M);
		scanf("%d", &S);
		for(int i = 0; i < 4; i++)
			scanf("%d", &threshold[i]);
		scanf("%d", &C);
		
		for(int i = 0; i < 4; i++)
			enable[i] = (C>>i)&1;
		for(int i = 4; i < 8; i++)
			trigger[i - 4] = (C>>i)&1;
		
		int result[4] = {};
		int now_time = 0, L, R;
		scanf("%d", &K);
		while(K--) {
			scanf("%d %d", &time, &temp);
			L = now_time;
			R = now_time + time;
			if(R < S) {
				
			} else {
				int last_read = R / M * M;
				if(L <= last_read && last_read <= R && last_read >= S) {
					for(int i = 0; i < 4; i++) {
						if(trigger[i] == 0) {
							result[i] |= (temp < threshold[i])&enable[i];
						} else {
							result[i] |= (temp > threshold[i])&enable[i];
						}
					}
				}
			}
			now_time = R;
		}
		printf("Case %d:", ++cases);
		for(int i = 0; i < 4; i++)
			printf(" %s", result[i] ? "yes" : "no");
		puts("");
	}
	return 0;
}
Read More +