解題區/解題區 - UVa

UVa 172 - Calculator Language

Problem

Calculator Language (CL) supports assignment, positive and negative integers and simple arithmetic. The allowable characters in a CL statement are thus:

All operators have the same precedence and are right associative, thus 15 - 8 - 3 = 15 - (8 - 3) = 10. As one would expect, brackets will force the expression within them to be evaluated first. Brackets may be nested arbitrarily deeply. An expression never has two operators next to each other (even if separated by a bracket), an assignment operator is always immediately preceded by a variable and the leftmost operator on a line is always an assignment. For readability, spaces may be freely inserted into an expression, except between a negative sign and a number. A negative sign will not appear before a variable. All variables are initialised to zero (0) and retain their values until changed explicitly.

Write a program that will accept and evaluate expressions written in this language. Each expression occupies one line and contains at least one assignment operator, and maybe more.

Input

Input will consist of a series of lines, each line containing a correct CL expression. No line will be longer than 100 characters. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each line of the input. Each line will consist of a list of the final values of all variables whose value changes as a result of the evaluation of that expression. If more than one variable changes value, they should be listed in alphabetical order, separated by commas. If a variable changes value more than once in an expression, only the final value is output. A variable is said to change value if its value after the expression has been evaluated is different from its value before the expression was evaluated. If no variables change value, then print the message `No Change’. Follow the format shown below exactly.

Sample input

1
2
3
4
5
6
7
A = B = 4
C = (D = 2)*_2
C = D = 2 * _2
F = C - D
E = D * _10
Z = 10 / 3
#

Sample output

1
2
3
4
5
6
A = 4, B = 4
C = -4, D = 2
D = -4
No Change
E = 40
Z = 3

Solution

題目描述：

給一個六則運算，並且所有運算由右往左，也就是題目提及的 right associative，並且在每一個運算式之後輸出有改變值的變數結果。

題目解法：

要處理的問題相當多，按照一般的思路要做出 right associative 還不打緊，就像冪次的定義一樣，也就是把 stack 的嚴格遞增改成非嚴格遞增。

但是查閱討論區給定的數據後，如下所示

範例輸入

1
2
B=(A=1)+(A=2)
#

範例輸出

1
A = 1, B = 3

這表示著連括弧運算順序都是 right associative，這一點相當苦惱，於是最後建造 tree，然後先拜訪右子樹、再拜訪左子樹來解決這些問題。

中間誤把 No Change 寫成 No change，因此卡了不少 Wrong Answer。

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A = B = 4
B=B-6+B=100
C = (D = 2) * _2
C = D = 2 * _2
E = D * _10
F = 15 - 8 - 3
F = 15 - 8 + _3
F=1+F=F-1
A=((3))
Z=Y=X=A=B=C=1+D=E=F=G=2-H=K=J=I=L=M=O=N=P=Q=R=S=T=V=U=W=3
A=100/2
A=100/_2
B=(_1+A*2)/2
B=(1+A*_2)/2
A=(((1-2)*3)+4)
A=((1-(2*3))+4)
A=((1-2)*(3+4))
A=(1-(2*(3+4)))
A=1+2+1+1+1+1+1+1+1+1+1+1+1+1+1+11+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+3
#

AC Sample Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A = 4, B = 4
B = -6
C = -4, D = 2
D = -4
E = 40
F = 10
No Change
No Change
A = 3
A = 0, B = 0, C = 0, D = -1, E = -1, F = -1, G = -1, H = 3, I = 3, J = 3, K = 3, L = 3, M = 3, N = 3, O = 3, P = 3, Q = 3, R = 3, S = 3, T = 3, U = 3, V = 3, W = 3
A = 50
A = -50
B = -50
B = 50
A = 1
A = -1
A = -7
A = -13
A = 62

一開始還在想為什麼當 B = 4 時，B=B-6+B=100 會產出 B = -6，由右往左運算。

  • B = 100
  • 6 + B = 106
  • B - (6 + B) = 100 - 106 = -6
  • B assign(=) -6
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
// Accepted
#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <sstream>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return -1;
        case '=':return 3;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    puts("ERROR");
    return -1;
}
void trans(char infix[], char buffer[]) {
    int len = strlen(infix);
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
        if(infix[i] == '_' || isdigit(infix[i]) || isalpha(infix[i])) {
        	while(infix[i] == '_' || isdigit(infix[i]) || isalpha(infix[i])) {
        		if(infix[i] == '_')
        			sprintf(ptr, "-");
        		else
            		sprintf(ptr, "%c", infix[i]);	
            	while(*ptr)    ptr++;
            	i++;
        	}
            sprintf(ptr, " ");	
            while(*ptr)    ptr++;
        	i--;
        }else {
        	if(infix[i] == ' ')	continue;
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(') {
                	if(infix[i] == '=') {
                		while(!op.empty() && priority_op(op.top()) > priority_op(infix[i])) {
                    		sprintf(ptr, "%c ", op.top()), op.pop();
                    		while(*ptr) ptr++;
                		}
                	} else {
                		while(!op.empty() && priority_op(op.top()) > priority_op(infix[i]) && op.top() != '=') {
                    		sprintf(ptr, "%c ", op.top()), op.pop();
                    		while(*ptr) ptr++;
                		}
                	}
                }
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
int Variable[26] = {}, oldVal[26] = {};
string to_string(int number) {
   stringstream ss;//create a stringstream
   ss << number;//add number to the stream
   return ss.str();//return a string with the contents of the stream
}
struct TreeNode {
    string 	A, B, OP;
    int 	l, r;
    TreeNode(string a="", string b="", string op=""):
        A(a), B(b), OP(op) {}
};
TreeNode node[1024];
int runTree(int label) {
    string 	A = node[label].A;
    string	B = node[label].B;
    int 	a, b;
    if(node[label].OP == "LEAF") {
        if(isalpha(A[0]))
           	a = Variable[A[0] - 'A'];
        else
           	a = atoi(A.c_str());
        return a;	
    }
    b = runTree(node[label].r);
    a = runTree(node[label].l);
//	printf("%d %d\n", a, b);
    //cout << A << ", " << B << ", " << node[label].OP << endl;
    switch(node[label].OP[0]) {
    	case '+': a = a + b; break;
        case '-': a = a - b; break;
        case '*': a = a * b; break;
        case '/': a = a / b; break;
        case '=': 
        	a = b;
        	if(isalpha(A[0])) {
        		Variable[A[0] - 'A'] = a;
        		//cout << A << " -- " << a << endl;
        	}
        	break;
    }
    return a;
}
void buildTree(char postfix[]) {
    
    stringstream	sin(postfix);
    string 			token, A, B;
    stack<string>	stk;
    stack<int>		nodeLabel;
    int 			treeSize = 0;
    
    while(sin >> token) {
    	if(isalpha(token[0])) {
    		stk.push(token);
    		nodeLabel.push(treeSize);
    		node[treeSize++] = TreeNode(token, "", "LEAF");
    		
    	} else if(isdigit(token[token.length() - 1])) {
    		stk.push(token);
    		nodeLabel.push(treeSize);
    		node[treeSize++] = TreeNode(token, "", "LEAF");
    	} else {
            B = stk.top(), stk.pop();
            A = stk.top(), stk.pop();
            int a, b;
            b = nodeLabel.top(), nodeLabel.pop();
            a = nodeLabel.top(), nodeLabel.pop();
            nodeLabel.push(treeSize);
            node[treeSize] = TreeNode(A, B, token);
            node[treeSize].l = a, node[treeSize].r = b;
            treeSize++;
            stk.push("INNER");
    	}
    }
    runTree(nodeLabel.top());
}
char infix[262144], postfix[262144];
int main() {
    while(gets(infix) && infix[0] != '#') {
        trans(infix, postfix);
        
        for(int i = 0; i < 26; i++)
        	oldVal[i] = Variable[i];
        	
        buildTree(postfix);
        
        int f = 0;
        for(int i = 0; i < 26; i++) {
        	if(oldVal[i] != Variable[i]) {
        		if(f)	printf(", ");
        		f = 1;
        		printf("%c = %d", i + 'A', Variable[i]);
        	}
        }
        if(f == 0)
        	puts("No Change");
        else
        	puts("");
        //printf("%s\n", postfix);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 177 - Paper Folding

Problem

If a large sheet of paper is folded in half, then in half again, etc, with all the folds parallel, then opened up flat, there are a series of parallel creases, some pointing up and some down, dividing the paper into fractions of the original length. If the paper is only opened half-way'' up, so every crease forms a 90 degree angle, then (viewed end-on) it forms adragon curve’’. For example, if four successive folds are made, then the following curve is seen (note that it does not cross itself, but two corners touch):

UVa 177

Write a program to draw the curve which appears after N folds. The exact specification of the curve is as follows:

  • The paper starts flat, with the ``start edge’’ on the left, looking at it from above.
  • The right half is folded over so it lies on top of the left half, then the right half of the new double sheet is folded on top of the left, to form a 4-thick sheet, and so on, for N folds.
  • Then every fold is opened from a 180 degree bend to a 90 degree bend.
  • Finally the bottom edge of the paper is viewed end-on to see the dragon curve.

From this view, the only unchanged part of the original paper is the piece containing the start edge, and this piece will be horizontal, with the start edge on the left. This uniquely defines the curve. In the above picture, the start edge is the left end of the rightmost bottom horizontal piece (marked s). Horizontal pieces are to be displayed with the underscore character _, and vertical pieces with the | character.

Input

Input will consist of a series of lines, each with a single number N (1 <= N <= 13). The end of the input will be marked by a line containing a zero.

Output

Output will consist of a series of dragon curves, one for each value of N in the input. Your picture must be shifted as far left, and as high as possible. Note that for large N, the picture will be greater than 80 characters wide, so it will look messy on the screen. The pattern for each different number of folds is terminated by a line containing a single `^’.

Sample input

1
2
3
4
2
4
1
0

Sample output

1
2
3
4
5
6
7
8
9
10
|_
 _|
^
   _   _
  |_|_| |_
   _|    _|
|_|
^
_|
^

Solution

題目描述：

將一個長條紙水平擺放，接著將右手邊的紙摺疊到左上邊的紙上面，接著又再重複做幾次，直到 N 次 ( 若將其攤平則會有 2N 個折疊區塊 )。摺疊完後，依序將其攤開，攤開的方式為：將前一次摺疊的 (想像與 s 重疊的那一片) 從 180 度旋轉到 90 度位置，依序攤開 N 次。

題目解法：

這一題就是題目理解麻煩點，但是不難發現肯定是有遞迴需要處理的。

假設我們定義展開的每一根，分別為往上下左右的射線，會發現其對應關係，新的尾會跟舊的頭對照，依序對照到中間部分。

最後得到關係

  • 上 變成 左
  • 下 變成 右
  • 左 變成 下
  • 右 變成 上

輸出處理方面，利用一個 map 結構去完成。

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
#include <stdio.h> 
#include <map>
#include <set>
#include <algorithm>
using namespace std;
map<int, set< pair<int, int> > > P;
void build(int n) {
    int A[1<<15];
    // 0 up, 1 down, 2 left, 3 right
    int trans[] = {2, 3, 1, 0};
    int m = 1;
    A[0] = 3;
    for(int i = 1; i <= n; i++) {
        for(int j = m - 1, k = m; j >= 0; j--, k++)
            A[k] = trans[A[j]];
        m = m << 1;
    }
    int x = -1, y = 0, px = 0, py = 0;
    P.clear();
    for(int i = 0; i < m; i++) {
        if(A[i] == 0)		x = px<<1, y = py;
        else if(A[i] == 1)	x = px<<1, y = py - 1;
        else if(A[i] == 2)	x = (px<<1)-1, y = py;
        else				x = (px<<1)+1, y = py;
        //printf("%d %d %d - %d %d\n", px, py, A[i], x, y);
        if(A[i] == 0) {
            P[y].insert(make_pair(x, 0));
        } else if(A[i] == 1) {
            P[y].insert(make_pair(x, 1));
        } else if(A[i] == 2) {
            P[y].insert(make_pair(x, 2));
        } else {
            P[y].insert(make_pair(x, 3));
        }
        if(A[i] == 0)		py++;
        else if(A[i] == 1)	py--;
        else if(A[i] == 2)	px--;
        else				px++;
    }
}
int main() {
    for(int n; scanf("%d", &n) == 1 && n; ) {
        build(n);
        int mxy = -0x3f3f3f3f, mnx = 0x3f3f3f3f;
        for(map<int, set< pair<int, int> > >::iterator it = P.begin();
        it != P.end(); it++) {
            mxy = max(mxy, it->first);
            for(set< pair<int, int> >::iterator jt = it->second.begin();
                jt != it->second.end(); jt++) {
                mnx = min(mnx, jt->first);
            }
        }
        for(map<int, set< pair<int, int> > >::reverse_iterator it = P.rbegin();
        it != P.rend(); it++) {
            int i = mnx;
            for(set< pair<int, int> >::iterator jt = it->second.begin();
                jt != it->second.end(); jt++) {
                while(i < jt->first)	putchar(' '), i++;
                i++;
                if(jt->second == 0 || jt->second == 1)
                    putchar('|');
                else
                    putchar('_');
            }
            puts("");
        }
        //printf("%d %d\n", mxy, mnx);
        puts("^");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 132 - Bumpy Objects

Problem

132img1

Consider objects such as these. They are polygons, specified by the coordinates of a centre of mass and their vertices. In the figure, centres of mass are shown as black squares. The vertices will be numbered consecutively anti-clockwise as shown.

An object can be rotated to stand stably if two vertices can be found that can be joined by a straight line that does not intersect the object, and, when this line is horizontal, the centre of mass lies above the line and strictly between its endpoints. There are typically many stable positions and each is defined by one of these lines known as its base line. A base line, and its associated stable position, is identified by the highest numbered vertex touched by that line.

Write a program that will determine the stable position that has the lowest numbered base line. Thus for the above objects, the desired base lines would be 6 for object 1, 6 for object 2 and 2 for the square. You may assume that the objects are possible, that is they will be represented as non self-intersecting polygons, although they may well be concave.

Input and Output

Successive lines of a data set will contain: a string of less than 20 characters identifying the object; the coordinates of the centre of mass; and the coordinates of successive points terminated by two zeroes (0 0), on one or more lines as necessary. There may be successive data sets (objects). The end of data will be defined by the string ‘#’.

Output will consist of the identification string followed by the number of the relevant base line.

Sample input

1
2
3
4
5
6
7
Object2
4 3
3 2  5 2  6 1  7 1  6 3  4 7  1 1  2 1  0 0
Square 
2 2
1 1  3 1  3 3  1 3  0 0
#

Sample output

1
2
Object2             6
Square              2

Solution

題目描述：

給定一個多邊形，將會給予這個多邊形的質心和頂點。在圖中，質心表示成黑色正方形的小點，而頂點將會使用連續編號逆時針給點。

多邊形可以藉由旋轉放置於水平，並且穩定立起。這時可以發現，會有兩個頂點拉起的水平線，並且質心會位於水平線上的兩個端點之間。

通常一個多邊形具有多個這種水平放置方法，對於一個水平放置方式，可以用在水平線上最大編號的頂點描述。

請輸出最小水平放置的編號。

題目解法：

對多邊形著手凸包計算，這裡使用單調鍊去完成凸包。接著利用內積找到質心是否在兩個水平線端點 (segment 的上方) 之間。

可以利用外積判斷是否在線 (line) 上。

好好利用數學運算，將可以在簡短的代碼完成。

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
#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 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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m - 1;
}
int main() {
    char testcase[105];
    Pt P[1024], CH[1024], IN[1024];
    while(scanf("%s", testcase) == 1) {
        if(!strcmp(testcase, "#"))
            break;
        double 	x, y;
        int 	n = 0, m;
        Pt mc;
        scanf("%lf %lf", &mc.x, &mc.y);
        while(scanf("%lf %lf", &x, &y) == 2) {
            if(x == 0 && y == 0)
                break;
            IN[n] = P[n] = Pt(x, y);
            n++;
        }
        m = monotone(n, P, CH);
        int ret = 0x3f3f3f3f;
        for(int i = 0, j = m - 1; i < m; j = i++) {
            if(between(CH[i], CH[j], mc)) {
                int mn = 0;
                for(int k = 0; k < n; k++)
                    if(onSeg(CH[i], CH[j], IN[k]))
                        mn = max(mn, k);
                ret = min(ret, mn);
            }
        }
        printf("%-20s%d\n", testcase, ret + 1);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 134 - Loglan-A Logical Language

Problem

Loglan is a synthetic speakable language designed to test some of the fundamental problems of linguistics, such as the Sapir Whorf hypothesis. It is syntactically unambiguous, culturally neutral and metaphysically parsimonious. What follows is a gross over-simplification of an already very small grammar of some 200 rules.

Loglan sentences consist of a series of words and names, separated by spaces, and are terminated by a period (.). Loglan words all end with a vowel; names, which are derived extra-linguistically, end with a consonant. Loglan words are divided into two classes–little words which specify the structure of a sentence, and predicates which have the form CCVCV or CVCCV where C represents a consonant and V represents a vowel (see examples later).

The subset of Loglan that we are considering uses the following grammar:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
A             →  a | e | i | o | u
MOD           →  ga | ge | gi | go | gu
BA            →  ba | be | bi | bo | bu
DA            →  da | de | di | do | du
LA            →  la | le | li | lo | lu
NAM           →  {all names}
PREDA         →  {all predicates}
<sentence>    →  <statement> | <predclaim>
<predclaim>   →  <predname> BA <preds> | DA <preds>
<preds>       →  <predstring> | <preds> A <predstring>
<predname>    →  LA <predstring> | NAM
<predstring>  →  PREDA | <predstring> PREDA
<statement>   →  <predname> <verbpred> <predname> | <predname> <verbpred>
<verbpred>    →  MOD <predstring>

Write a program that will read a succession of strings and determine whether or not they are correctly formed Loglan sentences.

Input and Output

Each Loglan sentence will start on a new line and will be terminated by a period (.). The sentence may occupy more than one line and words may be separated by more than one whitespace character. The input will be terminated by a line containing a single `#’. You can assume that all words will be correctly formed.

Output will consist of one line for each sentence containing either Good' orBad!’.

Sample input

1
2
3
4
la mutce bunbo mrenu bi ditca.
la fumna bi le mrenu.
djan ga vedma le negro ketpi.
#

Sample output

1
2
3
Good
Bad!
Good

Solution

其實這一題有比較好的解法，但是在正在學編譯器，因此把 LL(1) parser 運用在此題
，所以代碼會稍微長一點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<sentence>    ->  <common_pre>
<sentence>    ->  DA <preds>
<common_pre>  ->  <predname> <suffix>
<suffix>      ->  <predclaim>
<suffix>      ->  <statement>
<predclaim>   ->  BA <preds>
<preds>       ->  <preds_head> <preds_tail>
<preds_head>  ->  <predstring>
<preds_tail>  ->  A <predstring> <preds_tail>
<preds_tail>  ->  l
<predname>    ->  LA <predstring>
<predname>    ->  NAM
<predstring>  ->  PREDA <predstr_tail>
<predstr_tail> -> PREDA <predstr_tail>
<predstr_tail> -> l
<statement>   ->  <verbpred> <statement_s>
<statement_s> ->  <predname>
<statement_s> ->  l
<verbpred>    ->  MOD <predstring>

為了要符合 LL(1) 的形式，要想辦法將 Grammar 符合規格，也就是每一條 production rule 的 predict set 不會有模稜兩個的情況，也就是說當我看到某個 non-terminal 在 stack 上，在去看下一個 token，然後可以對於 (non-terminal, token) 只找到一條規則去匹配。

predict set 是根據每一條 production rule 所產生的，也就是說這個推論可以產生的第一個 token 是什麼，假使有相同的前綴時，則必須拉出做調整。// 因為這將會造成模稜兩可的情況。

遇到

1
2
A -> BCx
A -> BCy

應調整成

1
2
3
A -> BCW
W -> x
W -> y

在 parsing 問題上，應避免替換的無限迴圈。
遇到

1
2
3
A -> AC
A -> X
A -> Y

應調整成

1
2
3
4
5
A -> WD
D -> CD
D -> lambda
W -> X
W -> Y

發現對照課本的 parsing function 撰寫起來才發現有些不完善的地方，對於 lldriver() 會沒有辦法應對輸入結束，要吐出 lambda 的問題。

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
#include <stdio.h> 
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <ctype.h>
#include <assert.h>
using namespace std;
class Production {
    public:
        string 			LHS;
        vector<string> 	RHS;
        int 			label;
        
        Production(string L = "", vector<string> R = vector<string>()) {
            LHS = L;
            RHS = R;
        }
        
        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:
        static const string 		lambda;
        string 						start_symbol;
        vector<Production> 			rules;
        map<string, set<string> > 	first_set;
        map<string, set<string> > 	follow_set;
        map<string, bool> 			derives_lambda;
        map<string, map<string, Production> >	lltable;
        
        map<string, bool> mark_lambda();
        void fill_first_set();
        void fill_follow_set();
        bool isNonterminal(string token);
        set<string> compute_first(vector<string> rhs);
        set<string> get_predict_set(Production p);
        void fill_lltable();
        void lldriver(queue<string> tokens);
};
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;
        }
    }
    
}
bool Grammar::isNonterminal(string token) {
    
    if(token[0] == '<' && token[token.length() - 1] == '>')
        return true;
    return false;
}
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;
}
int aVowel(char c) {
    switch(c) {
        case 'a':case 'e':case 'i':case 'o':case 'u':
            return 1;
    }
    return 0;
}
string token2symbol(const string &str) {
    int n = str.length();
    if (!islower(str[n - 1]) || !aVowel(str[n - 1])) {
        return "NAM";
    }
    switch (n) {
    	case 1: return "A";
    	case 5:
        n = aVowel(str[4]);
        n |= ((aVowel(str[0]) << 4) | (aVowel(str[1]) << 3));
        n |= ((aVowel(str[2]) << 2) | (aVowel(str[3]) << 1));
        return (n == 5 || n == 9) ? "PREDA" : "UN";
    	case 2:
        	switch (str[0]) {
        		case 'g': return "MOD";
        		case 'b': return "BA";
        		case 'd': return "DA";
        		case 'l': return "LA";
        	}
    }
    return "UN";
}
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);
} 
int main() {
    Grammar g;
    parsingProduction("<sentence>    ->  <common_pre>", g);
    parsingProduction("<sentence>    ->  DA <preds>", g);
    parsingProduction("<common_pre>  ->  <predname> <suffix>", g);
    parsingProduction("<suffix>      ->  <predclaim>", g);
    parsingProduction("<suffix>	  	 ->  <statement>", g);
    parsingProduction("<predclaim>   ->  BA <preds>", g);
    parsingProduction("<predclaim>   ->  DA <preds>", g);
    parsingProduction("<preds>       ->  <preds_head> <preds_tail>", g);
    parsingProduction("<preds_head>  ->  <predstring>", g);
    parsingProduction("<preds_tail>  ->  A <predstring> <preds_tail>", g);
    parsingProduction("<preds_tail>  ->  l", g);
    parsingProduction("<predname>    ->  LA <predstring>", g);
    parsingProduction("<predname>    ->  NAM", g);
    parsingProduction("<predstring>  ->  PREDA <predstr_tail>", g);
    parsingProduction("<predstr_tail> -> PREDA <predstr_tail>", g);
    parsingProduction("<predstr_tail> -> l", g);
    parsingProduction("<statement>   ->  <verbpred> <statement_s>", g);
    parsingProduction("<statement_s> ->  <predname>", g);
    parsingProduction("<statement_s> ->  l", g);
    parsingProduction("<verbpred>    ->  MOD <predstring>", g);
    
    g.start_symbol = "<sentence>";
        
    g.fill_first_set();
    g.fill_follow_set();
    g.fill_lltable();
    
    queue<string> SYMBOL;
    for(string token; cin >> token && token != "#";) {
        size_t pos = token.find('.');
        if(pos == string::npos) {
            SYMBOL.push(token2symbol(token));
            //cout << token2symbol(token) << " ";
            continue;
        }
        token.erase(token.length() - 1);
        //cout << token2symbol(token) << endl;
        if(token.length() > 0)
            SYMBOL.push(token2symbol(token));
        g.lldriver(SYMBOL);
        
        while(!SYMBOL.empty())
            SYMBOL.pop();
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

ICPC 4020 - Hard Rode

Problem

The road to Shu is hard, even harder than climbing to the blue sky. A poem by Li Po from Tang Dynasty 1,200 years ago described the difficulty in travelling into Sichuan.

\epsfbox{p4020.eps}

However the above old saying is no longer true as a convenient communication network of railway, highway, waterway and air transport has come into being. Railways cover a total mileage of 2,693 km, consisting of five trunk lines including the BaojiChengdu and Chengdu-Chongqing railways, eight feeder lines and four local railways. The total mileage of highways stretches to nearly 80,000 km, ranking at the forefront in China. Now a highway network with the provincial capital of Chengdu as the center radiating to all cities in the province has been formed. A total of 500 km of expressways have been built. It is very easy to transfer passengers and freights between Sichuan and other provinces. After a nationwide railway speed acceleration launched in last year, trains can be allowed to run at a speed above 120 km per hour. However, the average speed of a train depends on its make-up. There is only single railway track between stations from Baoji to Chengdu, A primary task for dispatchers is to arrange for trains to meet and pass each other. You are requested to write a program to make the arrangement for a series of trains of different speeds from one station to its next station in the least amount of time.

What you should pay attention to while writing this program is that since there is a single railway track from Baoji to Chengdu, two trains are not allowed to pass the same spot at the same time, or they would be collision, and that because of the limited staff, there should be a fixed interval time between two trains out of the station, what’s more, the trains could pull into the station at the same time, but never get out at the same time.

Input

The input consists of several test cases. Each test case begins with a line containing 3 integers L (1 <= L <= 100000) , N (1 <= N <= 8) and T (1 < T < 10000) which indicate the distance between two stations (unit is meter), the number of trains, as well as the interval time of adjacent trains when trains leave the start (unit is second).

The next N lines contain average speeds of N trains (unit is m/s).

A single line with L = 0 indicates the end of input file and should not be processed by your program.

Output

For each test case, your output should be in one line with the minimum time(round to integer) needed by the trains pulling into the terminal as indicated in the sample output.

Sample Input

1
2
3
4
5
6
7
8
100000 6 300 
3 
4 
5 
6 
2 
1 
0

Sample Output

1
Case 1: 101500

Solution

題目描述：

從 陝西省寶雞市 到 四川省成都市 有一條鐵軌，而這一條鐵軌一次有好幾台火車在運行，但是不會發生追撞事件，然而每台火車的速度不一樣，而且站務人員會每隔固定時間發一班車，在不發生碰撞的情況下，最後一台火車到達成都市的最少時間為何？

題目解法：

在這樣的情況，有可能慢車先出發，然在在 T 秒之後，快車恰好追到慢車，這樣的情況會更好。但是實際數據應該長成什麼樣子沒有仔細考慮。

如果使用慢車最後出發，這樣能確保一定不會產生碰撞，但不確定是否是最佳解。

所以使用 O(n!) 的窮舉來計算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h> 
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
    int L, N, T, cases = 0;
    long long speed[10];
    while(scanf("%d %d %d", &L, &N, &T) == 3 && L) {
        int p[10] = {};
        for(int i = 0; i < N; i++) {
            scanf("%lld", &speed[i]);
            p[i] = i;
        }
        sort(speed, speed + N);
        long long ret = 0x3f3f3f3f;
        do {
            double start = T, lastTime = L / speed[p[0]];
            for(int i = 1; i < N; i++) {
                double time = L / speed[p[i]] + start;
                if(time >= lastTime) {
                    start += T;
                    lastTime = time;
                } else {
                    lastTime = 0x3f3f3f3f;
                    break;
                    // start += T + (lastTime - time);
                }
            }
            ret = min(ret, (long long) ceil(lastTime));
        } while (next_permutation(p, p + N));
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10320 - Cow Trouble! Help Please

Problem

There are many classic problem with cows/goats and grass field in the world of mathematics. One of such problems is shown in the picture (left one) below. A goat is tied at point C which is on the edge of a round field with a rope of length R. One has to determine the length R when the cow can eat 50% grass of the round field. But in this problem we will consider a slightly different scenario which is shown in the second figure. In a field of infinite area there is a house ABDC. A cow is tied with pillar B of the house with a rope of length R. The length and width of the house is l and w. If the house was not there the cow could eat all the grass in the round green field (The round green field is a circle of radius R). But the presence of the house will certainly reduce his ability as the cow cannot enter the house nor can any part of the rope. You will have to determine the area the cow can now roam around and eat grass.

Fig 1: A classic Problem with a Goat

Fig 2: The Current Classic Problem with Cow

Input

The input file contains several lines of input. Each line contains three floating point numbers l, w and R as described in the problem statement. All numbers are less than 10000. Input is terminated by end of file.

Output

For each line of input produce one line of output. This output denotes the area that the cow can cover by not entering the house. This value should contain ten digits after the decimal point. Output will be checked with special judge. So you should not worry about very small precision errors.

Sample Input

1
2
10 5 5
10 4 8

Sample Output

1
2
58.9048622548
163.3628179867

Solution

題目描述：
有一頭牛被一根長度 R 的繩子拴在一棟建築物 ABCD 的 B 點上，草地的範圍為無限大，求牛可以吃到的草的範圍。Input 會給l, w 和 R 表示建築物長寬和繩長；l, w, R < 10000。Output 要輸到小數點第 10 位。

題目解法：

就是根據 R 的四種情況去討論，其中最麻煩的是對於 R > l + w，這種情況會需要討論重疊的區域，算出三角形夾角然後分別算兩個扇形面積，再弄回重疊區域三角形中的哪一塊有草。

其實這一題的題解網路上是有的，但是 PO 出來是因為自己卡在 WA，原因是這樣子的，假使 A = 0.5 * B 和 A = B / 2，這兩者寫法並無不同，但是後者的精準度比較好，很多次的 WA 都掛在這一點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int main() {
    double w, l, r;
    const double pi = acos(-1);
    while(scanf("%lf %lf %lf", &l, &w, &r) == 3) {
        if(w > l)
            swap(w, l);
        double area;
        if(r <= w)
            area = r * r * pi * 3 / 4.0;
        else if(r <= l)
            area = r * r * pi * 3 / 4.0 + (r - w) * (r - w) * pi / 4.0;
        else if(r <= l + w)
            area = r * r * pi * 3 / 4.0 + (r - w) * (r - w) * pi / 4.0 
                    + (r - l) * (r - l) * pi / 4.0;
        else {
            double a = atan2(l, w), b, c;
            double la, lb, lc;
            
            la = hypot(w, l);
            lb = r - w;
            lc = r - l;
            b = acos((la*la + lb*lb - lc*lc)/(2*la*lb)) + a;
            c = acos((la*la + lc*lc - lb*lb)/(2*la*lc)) + (pi /2) - a;
                        
            area = r * r * pi * 3 / 4.0;
            area += (r - w) * (r - w) * (pi - b) / 2;
            area += (r - l) * (r - l) * (pi - c) / 2;
            area += lb * la * sin(b - a) / 2;
            area -= w * l / 2;
        }
        printf("%0.10lf\n", area);			
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12717 - Fiasco

Problem

Natasha always mixes up things in her algorithm classes. Last week Prof. Chhaya Murthy gave the class a classical problem -finding shortest path to all nodes from a special node of a weighted graph. Before that in another class, the professor taught them Prim’s and Dijkstra’s algorithms which are similar looking but does very different things. Always confused, poor Natasha submitted something
very similar to the Prim’s algorithm (actually we should call it Natasha’s lgorithm), she didn’t test it properly. Pseudocode of her algorithm looks as follows

uva 12717

After submission, she showed the code to a friend who is good at algorithms. That friend immediately found the aw. Natasha was really terrifed and started to cry. Then there came the guys, the guys who liked her. They jumped at the opportunity and got hold of the dataset to be used to test the solutions. Your friend Rehan is one of those guys. He really wanted to impress Natasha. He asked you to change the dataset in such a way that Natasha’s algorithm gives the right result. After the change, Rehan will somehow be able to put the modified data with the old timestamp. Rehan told you that:

  1. The dataset has T test cases.
  2. Each case contains a connected weighted undirected graph with n nodes and
    m edges.
  3. Each case will contain a source node source.
  4. Edge weights are positive and distinct.

To avoid suspicion, Rehan asked you not to change which vertices the edges connect, or the overall set of edge weights. You may only reorder which weights are assigned to which edges

Input

The first line of the input denotes the number of datasets T (1 < T <= 15). T sets of case will follow. Each case will start with a triplet of numbers n (2 <= n <= 2500), m (1 <= m <= 25000) and source (1 <= source <= n) | the number of nodes, the number of edges and the starting node respectively.

Each of the next m lines will contain a triplet of numbers (u, v, w) meaning that there is an edge between node u and node v with weight w (1 <= w <= m). Nodes are numbered from 1 to n.

It is guaranteed that there is no duplicate or self-edges in the input and the graph is connected. In each given graph, all edge weights will be distinct.

Output

For each set of input, print one set of output. First line of a set should be of the format, Case X: where X is the case number. Then print each edge triplet | one triplet (u, v, w) in each line separated by a single space. The edges should be printed in the order given in the input. If there is more than one solution to a dataset, any one of them will do.

Sample Input

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

Sample Output

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

Solution

題目描述：
// 給一個錯誤代碼，修改測資，使錯誤代碼輸出正確。
在一門演算法課程中，上到了最短路徑算法，教授指出了 Prim 和 Dijkstra 算法之間的不同，課堂上有個妹子很不小心搞混了這兩個算法，甚至弄出了更奇怪的程序，這代碼其中有缺陷，她和朋友分享代碼後，沒想到朋友瞬間戳出輸出錯誤的測資，妹子一時之間哭了出來。

現在為了擄獲芳心，請修改測資，使得錯誤代碼有一樣的正確輸出。

題目解法：
這個妹子錯的地方在於，更新的時候，沒有將為探訪點的情況加以考慮，直接以 BFS 的方式丟入，那麼在隨後更新的路徑長就不會被丟入 Priority Queue，這樣在 Dijkstra 的更新順序上就會出錯。也就是說，只要 Graph 的權重依據 BFS 順序 符合由小到大，不會出現隨後更新的問題即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h> 
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
vector<int> g[2505];
int used[25005];
int in_x[25005], in_y[25005], in_w[25005];
map< pair<int, int>, int> shortest_tree;
void bfs(int source) {
    queue<int> 	Q;
    int 		u, v, e = 0;
    Q.push(source), used[source] = 1;
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(used[v])	continue;
            used[v] = 1;
            shortest_tree[make_pair(u, v)] = in_w[e], e++;
            Q.push(v);
        }
    }
}
int main() {
    int testcase, cases = 0;
    int n, m, source;
    int x, y, w;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &n, &m, &source);
        
        for(int i = 1; i <= n; i++) {
            g[i].clear();
            used[i] = 0;
        }
        shortest_tree.clear();
        
        for(int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(y);
            g[y].push_back(x);
            in_x[i] = x, in_y[i] = y, in_w[i] = w;
        }
        
        for(int i = 1; i <= n; i++)
            sort(g[i].begin(), g[i].end());
        sort(in_w, in_w + m);
        bfs(source);
        
        printf("Case %d:\n", ++cases);
        map< pair<int, int>, int>::iterator it, jt, kt;
        int e = m - 1;
        kt = shortest_tree.end();
        for(int i = 0; i < m; i++) {
            it = shortest_tree.find(make_pair(in_x[i], in_y[i]));
            jt = shortest_tree.find(make_pair(in_y[i], in_x[i]));
            if(it != kt)
                w = it->second;
            else if(jt != kt)
                w = jt->second;
            else
                w = in_w[e], e--;
            printf("%d %d %d\n", in_x[i], in_y[i], w);
        }
    }
    return 0;
}
/*
1
7 9 5
2 4 2
1 4 8
7 2 6
3 4 7
5 7 5
7 3 9
6 1 1
6 3 4
5 6 3
*/
Read More +
解題區/解題區 - UVa

UVa 12716 - GCD XOR

Problem

Given an integer N, Find how many pairs (A, B) are there such that gcd(A, B) = A xor B where 1 < B < A <= N. Here gcd(A, B) means the greatest common divisor of the numbers A and B. And A xor B is the value of the bitwise xor operation on the binary representation of A and B.

Input

The First line of the input contains an integer T (T < 10000) denoting the number of test cases. The following T lines contain an integer N (1 <= N <= 30000000).

Output

For each test case, print the case number first in the format, Case X: (here, X is the serial of the input) followed by a space and then the answer for that case.
There is no new-line between cases.

Explanation
Sample 1:
For N = 7, there are four valid pairs: (3, 2), (5, 4), (6, 4) and (7, 6).

Sample Input

1
2
3
2
7
20000000

Sample Output

1
2
Case 1: 4
Case 2: 34866117

Solution

首先，嘗試把 N <= 1000 的情況列下來，列出 gcd(A, B) = C = A xor B

其中滿足 B < A and A mod C = 0，然後我們又觀察到 A&C == C，也就是說看 bitmask 的話，C 是 A 的 subset。

經由這一點，我們可以先寫出一個不會過 (TLE) 的做法，對 A 找到所有因子 C，查看是否符合 A&C == C，但是這樣的做法很容易知道時間效率不夠好。

下面是一個最簡單的版本。

TLE version
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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define maxL (30000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int P[5500], Pt = 0;
int F[30000005] = {};
void sieve() {
    register int i, j, k, l;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(j = i + i; j <= n; j += i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
vector< pair<int, int> > factor(int n) {
    int on = n;
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {		
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void make(int idx, int n, int m, vector< pair<int, int> > &v) {
    if(idx == v.size()) {
        if((n&m) == m)
            F[n]++;
        return;
    }
    int a = m, b = v[idx].first;
    for(int i = v[idx].second; i >= 0; i--)
        make(idx + 1, n, a, v), a *= b;
}
int main() {
    sieve();
    vector< pair<int, int> > ff;
    for(int i = 1; i <= 30000000; i++) {
        ff = factor(i);
        make(0, i, 1, ff);
    }
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        int ret = 0;
        for(int i = 1; i <= n; i++)
            ret += F[i];
        printf("%d\n", ret - n);
    }
    return 0;
}

接著，使用其他的考慮方式，既然 (n, n + 1) 是已知解，其倍數解 (kn, k(n + 1))也是考量的一部分。

總歸一句，觀察 orz。

accepted
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
using namespace std;
int F[30000005] = {};
int main() {
    for(int i = 1; i <= 30000000; i++) {
        for(int j = i << 1; i + j <= 30000000; j += i) {
            if(((i + j)&(j)) == j)
                F[i + j]++;
        }
    }
    for(int i = 1; i <= 30000000; i++)
        F[i] += F[i-1];
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        printf("Case %d: %d\n", ++cases, F[n]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

Yacc 與 Lex 練習 - UVa 11291

Problem

詳細題目請參考 UVa 11291 - Smeech

語法

1
2
<E[x]> -> <Integer> | (p <E[x]> <E[x]>)
<Integer> -> #number

目標計算出 E[X] = p * (e1 + e2) + (1 - p) * (e1 - e2)

Yacc

Yacc 主要是根據 CFG 進行解析。

其中，要對於 Yacc 語法的回傳值明白操作情況。

對於語法回傳值，我們來個最簡單的範例：

1
2
expression -> LEFT_P NUMBER expression expression RIGHT_P
    $$          $1     $2       $3         $4       $5

其中 $$ 是回傳值，其中的 $1、$2 … 等，都是得到的回傳值。

對於 yylval 形態處理：

1
2
3
4
%union {
    float 	floatVal;
    int 	intVal;
}

通常使用 union 的方式來共用記憶體，在 lex 那邊就可以根據 yylval.floatVal 進行操作。

當然，我們也要對於每一個 nonterminal 定義回傳的型態

1
2
3
%type <floatVal> NUMBER
%type <floatVal> expression
%type <floatVal> startsymbol

基本上就大功告成了。

接著要考慮如何去完成多組測資組的問題，在這裡可以利用 kleene star 來完成。

但是對於輸出順序，使用 input -> input startsymbol 跟 input -> startsymbol input 輸出順序是不同的，如果要順著輸出，請選擇前者。

file: a.y
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
%{
#include <stdio.h>
int yylex();
double ans = 0;
void yyerror(const char* message) {
    ans = -2147483647;
    printf("Invaild format\n");
};
%}
%union {
    float 	floatVal;
    int 	intVal;
}
%type <floatVal> NUMBER
%type <floatVal> expression
%type <floatVal> startsymbol
%token LEFT_P RIGHT_P NUMBER
%%
input
    : input startsymbol {
        ans = $2;
        printf("%.2f\n", ans);
    }
    | {
    }
startsymbol
    : expression {
        $$ = $1;
    }
    ;
expression
    : NUMBER {
        $$ = $1;
    } 
    | LEFT_P NUMBER expression expression RIGHT_P {
        $$ = $2 * ($3 + $4) + (1.0f - $2) * ($3 - $4);
    }
    ;
%%
int main() {
    yyparse();
    return 0;
}

Lex

Lex 主要是扮演切出所有的 token 的角色，相當於 Scanner。同時要將值紀錄再 yylval 中，在 Yacc 那邊則會在 $NUMBER 中得到變數值。

在 Lex 語法上要特別小心，如果兩條的前綴 (prefix) 相同時 (解析上會產生相同的 token)，則會選擇長的那一條為優先。如果長度仍相同的話，請自行測試，這裡無法給予解答。而為什麼要這麼設計？為了保證後綴不會塞入奇怪的字符，因此可以先檢查隨後接的字符情況。

file: a.l
1
2
3
4
5
6
7
8
9
10
11
12
13
%{
#include "a.tab.h"
#include <stdio.h>
%}
%%
([-]?)[0-9]*\.[0-9]*		{sscanf(yytext, "%f", &yylval.floatVal); return NUMBER;}
([-]?)[0-9]+				{sscanf(yytext, "%f", &yylval.floatVal); return NUMBER;}
"("					{return LEFT_P;}
")"					{return RIGHT_P;}
\n					{}
.					{}
%%

make file

請用以下方法建造

1
morris $ sh make.sh

代碼如下

file: make.sh
1
2
3
4
5
bison -d a.y
flex a.l
gcc -c a.tab.c
gcc -c lex.yy.c
gcc lex.yy.o a.tab.o -lfl

產生的結果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ tree 
. ├── a.l
  ├── a.out 
  ├── a.tab.c 
  ├── a.tab.h 
  ├── a.tab.o 
  ├── a.y 
  ├── input~ 
  ├── lex.yy.c 
  ├── lex.yy.o 
  ├── make.sh 
  ├── make.sh~ 
  ├── testdata 
  │   ├── ac_output 
  │   └── input

執行

執行的時候就跟標準輸入串流一樣。

1
morris $ ./a.out <input

參考範例輸入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
7
(.5 3 9)
(0.3 2 (1 1 -10))
(1.0 (1.0 (1.0 -1 -2) (1.0 -1 -2)) (1.0 (1.0 1 2) 2))
(0.99 82 (0.76 50 (0.85 (0.07 (0.88 28 (0.98 79 (0.09 77 51))) (0.30 (0.29 36 (0.36 (0.51 27 (0.68 (0.47 87 35) (0.25 85 59))) 31)) 64)) (0.14 (0.84 (0.77 29 71) (0.50 (0.99 (0.81 (0.78 (0.87 50 7) 71) 72) 14) (0.30 (0.50 9 37) (0.67 21 (0.73 86 (0.08 31 14)))))) (0.94 (0.96 (0.50 27 (0.94 (0.54 62 (0.63 89 29)) (0.81 24 (0.94 20 72)))) 4) (0.44 9 (0.59 (0.70 48 40) (0.64 (0.27 97 71) 43))))))))
(0.15 12 60)
(0.55 18 (0.95 (0.79 95 (0.97 (0.11 (0.96 (0.70 (0.38 73 66) (0.38 (0.06 (0.02 88 66) (0.39 35 37)) 69)) (0.81 3 (0.45 5 61))) (0.44 (0.67 (0.23 82 7) 38) (0.24 49 74))) 76)) (0.46 19 44)))
(0.56 62 77)
(0.03 (0.90 19 35) (0.17 50 (0.13 (0.96 74 (0.07 (0.51 78 (0.77 (0.78 (0.84 64 (0.41 7 59)) 21) (0.73 (0.95 (0.13 2 85) (0.08 29 50)) (0.24 (0.12 43 99) 71)))) 84)) (0.31 69 (0.82 31 24)))))
(0.78 73 44)
(0.09 (0.80 14 62) (0.57 (0.57 95 (0.33 94 31)) (0.70 (0.92 32 (0.13 20 (0.44 87 (0.45 83 26)))) (0.43 40 (0.51 (0.57 29 (0.65 13 (0.40 74 56))) 56)))))
(0.96 (0.96 (0.65 (0.01 (0.98 (0.34 86 (0.68 87 21)) 27) (0.26 68 68)) (0.42 28 29)) 9) 99)
(0.99 (0.60 53 27) (0.35 23 (0.15 (0.50 85 (0.73 56 (0.34 (0.44 (0.10 (0.62 (0.20 58 15) 56) (0.57 74 (0.23 20 78))) 62) (0.92 (0.72 (0.82 75 (0.08 35 93)) 43) (0.55 10 (0.45 (0.25 52 91) 71)))))) (0.61 39 (0.49 (0.92 87 (0.13 52 (0.69 (0.46 (0.82 27 72) 96) (0.27 51 99)))) (0.36 99 (0.60 68 (0.49 (0.25 (0.92 54 7) (0.48 47 32)) (0.08 (0.69 97 11) 34)))))))))
(0.87 (0.32 (0.42 (0.66 69 (0.98 0 (0.46 94 (0.25 (0.57 (0.72 25 59) (0.35 91 (0.42 29 28))) 3)))) 19) 81) (0.72 (0.06 (0.66 (0.07 22 87) 44) (0.18 33 14)) 49))
(0.72 (0.01 67 (0.13 (0.22 (0.88 11 86) (0.04 40 (0.41 (0.86 (0.81 (0.08 84 95) (0.88 19 67)) 8) 96))) 13)) (0.13 45 (0.19 (0.83 85 (0.77 (0.37 78 (0.44 44 59)) 37)) 56)))
(0.51 (0.36 2 72) 25)
(0.32 51 87)
(0.06 (0.23 (0.70 93 47) (0.22 20 (0.90 (0.03 (0.48 (0.84 18 (0.29 (0.02 (0.06 52 49) 67) (0.49 (0.69 60 74) (0.59 92 0)))) 32) 80) (0.76 78 (0.66 8 94))))) 31)
(0.29 (0.54 70 (0.64 (0.48 (0.50 25 (0.38 (0.07 (0.14 (0.44 (0.76 44 45) 67) 41) (0.15 (0.86 (0.89 87 42) (0.43 85 58)) (0.98 44 (0.48 34 28)))) (0.84 81 60))) 28) 16)) (0.84 (0.21 34 (0.78 (0.76 (0.51 82 (0.07 (0.78 (0.52 (0.65 51 58) 12) (0.05 52 (0.98 0 30))) (0.01 27 3))) (1.00 15 (0.53 (0.91 (0.38 62 (0.75 92 69)) (0.85 53 (0.84 92 83))) (0.70 (0.12 (0.24 23 83) 58) (0.62 56 38))))) 36)) (0.66 41 13)))
(0.94 (0.47 30 56) (0.78 6 (0.45 (0.45 15 94) (0.77 (0.57 25 (0.33 66 12)) (0.66 74 (0.82 (0.14 75 50) (0.22 45 43)))))))
(0.66 (0.58 (0.85 75 26) 45) (0.04 (0.94 82 (0.59 34 (0.02 (0.09 11 (0.31 (0.05 (0.92 (0.14 51 45) (0.47 25 46)) 6) 5)) 33))) (0.81 (0.09 15 (0.91 (0.77 (0.59 44 (0.57 (0.39 (0.81 18 75) (0.37 41 67)) 18)) (0.77 (0.68 (0.71 (0.31 87 94) 85) (0.00 35 (0.55 81 22))) 56)) 3)) (0.43 7 (0.98 94 3)))))
(0.13 22 80)
(0.77 45 81)
(0.61 (0.21 (0.32 (0.32 (0.81 8 60) 78) (0.19 (0.92 68 (0.56 (0.22 79 32) (0.32 72 63))) 41)) (0.30 94 31)) (0.80 59 33))

參考範例輸出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
7.00
3.00
5.60
-1.00
241.55
-30.00
32.05
71.24
25.80
97.64
-37.98
153.38
67.92
35.81
-10.21
-17.66
19.68
60.84
92.20
30.61
157.62
-37.20
88.74
-48.46

Reference

Yacc 与 Lex 快速入门

指導

Inker

Read More +
解題區/解題區 - UVa

UVa 1636 - Headshot

Problem

You have a revolver gun with a cylinder that has n chambers. Chambers are located in a circle on a cylinder. Each chamber can be empty or can contain a round. One chamber is aligned with the gun’s barrel. When trigger of the gun is pulled, the gun’s cylinder rotates, aligning the next chamber with the barrel, hammer strikes the round, making a shot by firing a bullet through the barrel. If the chamber is empty when the hammer strikes it, then there is no shot but just a click.

You have found a use for this gun. You are playing Russian Roulette with your friend. Your friend loads rounds into some chambers, randomly rotates the cylinder, aligning a random chamber with a gun’s barrel, puts the gun to his head and pulls the trigger. You hear click and nothing else – the chamber was empty and the gun did not shoot.

Now it is your turn to put the gun to your head and pull the trigger. You have a choice. You can either pull the trigger right away or you can randomly rotate the gun’s cylinder and then pull the trigger. What should you choose to maximize the chances of your survival?

Input

The input file contains several datasets. A dataset contains a single line with a string of n digits 0 and 1 ( 2 <= n <= 100). This line of digits represents the pattern of rounds that were loaded into the gun’s chambers. 0 represent an empty chamber, 1 represent a loaded one. In this representation, when cylinder rotates before a shot, the next chamber to the right gets aligned with the barrel for a shot. Since the chambers are actually located on a circle, the first chamber in this string follows the last one. There is at least one 0 in this string.

Output

For each dataset, write to the output file one of the following words (without quotes):

  • SHOOT – if pulling the trigger right away makes you less likely to be actually shot in the head with the bullet (more likely that the chamber will be empty).
  • ROTATE – if randomly rotating the cylinder before pulling the trigger makes you less likely to be actually shot in the head with the bullet (more likely that the chamber will be empty).
  • EQUAL – if both of the above choices are equal in terms of probability of being shot.

Sample Input

1
2
3
0011
0111
000111

Sample Output

1
2
3
EQUAL
ROTATE
SHOOT

Solution

題目描述：

俄羅斯輪盤，現在與一位朋友一起玩這場遊戲，然而我們已經知道左輪手槍中的填彈資訊，剛聽到朋友按下扣板，但是沒有死。現在輪到你，請問要直接按？還是隨機轉一圈再按？

題目解法：

不外乎地，我們要找到哪個機率高。

由於朋友按下沒死，也就是要考慮連續 2 個 0 的情況，下一個是 0 的機率為 czero / zero

// 在前提為 0 的情況下，下一個為 0 的機率為何，也就是考慮 00 和 01 的情況下，00 的機率為何。
// czero 是連續為 0 的個數，zero 是 0 的個數 (同時也是 00 01 的個數。)，n 是全部個數。

隨機轉一圈得到 0 的概率為 zero / n。

不小心把題目想太難，事實上這問題很簡單的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <string.h>
int main(){
    char s[1024];
    while(scanf("%s", s) == 1){
        int n = strlen(s);
        int zero = 0, one = 0, czero = 0;
        for(int i = 0 ; i < n ; i++ ){
            if(s[i] == '1') 
                continue;
            zero++;
            if(s[(i+1)%n] == '0') czero++;
        }
        // czero - zero * (zero / n)
        if(czero * n == zero * zero) 
            puts("EQUAL");
        else if(czero * n > zero * zero)
            puts("SHOOT");
        else 
            puts("ROTATE");
    }
    return 0;
}
Read More +