Problem

The sequence of n - 1 consecutive composite numbers (positive integers that are not prime and not equal to 1) lying between two successive prime numbers p and p + n is called a prime gap of length n . For example, 〈24, 25, 26, 27, 28〉 between 23 and 29 is a prime gap of length 6.

Your mission is to write a program to calculate, for a given positive integer k , the length of the prime gap that contains k . For convenience, the length is considered 0 in case no prime gap contains k .

Input

The input is a sequence of lines each of which contains a single positive integer. Each positive integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709. The end of the input is indicated by a line containing a single zero.

Output

The output should be composed of lines each of which contains a single non-negative integer. It is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or `0’ otherwise. No other characters should occur in the output.

Sample Input

1
2
3
4
5
6

10 
11 
27 
2 
492170 
0

Sample Output

1
2
3
4
5

4 
0 
6 
0 
114

Solution

題目描述：

找該數字左右相鄰的兩個質數差值。

題目解法：

線性篩法 (sieve)。

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

#include <stdio.h>
#include <stdlib.h>
#define LL long long
#define maxL (1300000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
int anaP[30], at = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1300000;
    for(i = 2; i < n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
        }
    }
}
main() {
    sieve();
    int n;
    while(scanf("%d", &n) == 1 && n) {
    	int ret = 0;
    	for(int i = n; GET(i); i++, ret++);
    	for(int i = n; GET(i) && i > 0; i--, ret++);
    	printf("%d\n", ret);
    }
    return 0;
}

Problem

Numbers of the form a±bi are called complex numbers (Where i = √(-1)). In this problem you will have to find all the values of (a±bi)^1/n.

Input

The input file contains several lines of input. Each line has two parts. The first part will contain a complex number of the form a±bi and the second part will contain an integer n (0 < n <=100). Here a and b are integer numbers and 0 <= |a|, |b|<100. Input is terminated by end of file.

Output

For each line of input you should produce n+2 lines of output. The description of output for each line of input is given in the next paragraph:

First line contains the case number as shown in the sample output. Next n lines should contain the n-th roots of the input complex number. The printed complex numbers should be of the form x±yi, where x and y are floating point numbers rounded upto three digits after the decimal point. Note that there is no space between the operators and operands. The roots are sorted according to descending order of their real part and then according to the descending order of their imaginary part. When the printed value of x or y is 0.000, it should be interpreted as positive zero. So you should never print something like “-0.000”. After all these outputs print a blank line.

Sample Input

1
2

3+4i 2
5-4i 3

Sample Output

1
2
3
4
5
6
7
8

Case 1:
2.000+1.000i
-2.000-1.000i
Case 2:
1.810-0.414i
-0.546+1.775i
-1.264-1.361i

Solution

題目描述：

問虛數 a+bi 的 n 次根號的結果，並且根據實數由大至小、虛數由大至小的字典順序輸出。

題目解法：

先算出 a+bi 所占有的角度 theta，得到 (theta + 2 * pi * i / n) 是每一個根的角度，因為根據角度疊加原理得到 (theta + 2 * pi * i / n) ^ n = theta + 2 * pi * i ＝ theta，但是這題的困難是在於 如何避免 -0.000 的輸出。

原本錯誤排序的寫法

1
2
3
4
5

bool cmp(Point a, Point b) {
    if(fabs(a.x - b.x) > eps)
        return a.x < b.x;
    return a.y < b.y;
}

應更正為如下代碼，如果要問我為什麼，現在還沒有仔細地理解，照理來說應該是差不多的。

1
2
3
4
5
6
7

bool cmp(Point a, Point b) {
    if(fabs(a.x - b.x) > eps)
        return a.x < b.x;
    if(fabs(a.y - b.y) > eps)
        return a.y < b.y;
    return false;
}

之前是想利用 sprintf(buffer, "%+.3lf%+.3lf", a, b); 去檢查 +0.000 和 -0.000，這種寫法有點太過了，不過應該也是可行的。

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
bool cmp(pair<double, double> a, pair<double, double> b) {
    if(fabs(a.first - b.first) > eps)
        return a.first > b.first;
    if(fabs(a.second - b.second) < eps)
        return false;
    return a.second > b.second;
}
int main() {
    char s[50];
    const double pi = acos(-1);
    int n, i, cases = 0;
    double a, b;
    while(scanf("%s %d", s, &n) == 2) {
        if(sscanf(s, "%lf+%lfi", &a, &b) == 2)
            {}
        else
            sscanf(s, "%lf-%lfi", &a, &b), b = -b;
        double theta = atan2(b, a);
        double k = pow(sqrt(a*a+b*b), 1.0/n);
        double px, py;
        pair<double, double> D[128];
        for(i = 0; i < n; i++) {
            px = k*cos((theta + i*2*pi)/n);
            py = k*sin((theta + i*2*pi)/n);
            D[i] = make_pair(px, py);
        }
        sort(D, D+n, cmp);
        printf("Case %d:\n", ++cases);
        for(i = 0; i < n; i++) {
        	if(fabs(D[i].first) < 0.0005)	D[i].first = 0;
        	if(fabs(D[i].second) < 0.0005)	D[i].second = 0;
        	printf("%.3lf%+.3lfi\n", D[i].first, D[i].second);
        }
        puts("");
    }
    return 0;
}

Problem

Automatic Chemical Manufacturing is experimenting with a process called self-assembly. In this process, molecules with natural asonity for each other are mixed together in a solution and allowed to spon-taneously assemble themselves into larger structures. But there is one problem: sometimes molecules assemble themselves into a structure of unbounded size, which gums up the machinery.

You must write a program to decide whether a given collection of molecules can be assembled into a structure of unbounded size. You should make two simplifying assumptions: 1) the problem is restricted to two dimensions, and 2) each molecule in the collection is represented as a square. The four edges of the square represent the surfaces on which the molecule can connect to other compatible molecules.

In each test case, you will be given a set of molecule descriptions. Each type of molecule is described by four two-character connector labels that indicate how its edges can connect to the edges of other molecules. There are two types of connector labels:

• An uppercase letter ( A, …, Z ) followed by + or . Two edges are compatible if their labels have the same letter but different signs. For example, A+ is compatible with A but is not compatible with A+ or B.
• Two zero digits 00. An edge with this label is not compatible with any edge (not even with
  another edge labeled 00).

Assume there is an unlimited supply of molecules of each type, which may be rotated and reected.
As the molecules assemble themselves into larger structures, the edges of two molecules may be adjacent to each other only if they are compatible. It is permitted for an edge, regardless of its connector label, to be connected to nothing (no adjacent molecule on that edge). Figure A.1 shows an example of three molecule types and a structure of bounded size that can be assembled from them (other bounded structures are also possible with this set of molecules).

Input

The input consists of several test cases. A test case consists of two lines. The rst contains an integer n (1 < n < 40000) indicating the number of molecule types. The second line contains n eight-character strings, each describing a single type of molecule, separated by single spaces. Each string consists of four two-character connector labels representing the four edges of the molecule in clockwise order.

Output

For each test case, display the word unbounded if the set of molecule types can generate a structure of unbounded size. Otherwise, display the word bounded.

Sample Input

1
2
3
4

3
A+00A+A+ 00B+D+A- B-C+00C+
1
K+K-Q+Q-

Sample Output

1
2

bounded
unbounded

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

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
int g[64][64];
int node(char a, char b) {
    return (a - 'A') + (b == '+' ? 0 : 26);
}
int rnode(char a, char b) {
    return (a - 'A') + (b == '+' ? 26 : 0);
}
int exist_cycle;
int main() {
    int n;
    char s[50];
    while(scanf("%d", &n) == 1) {
        memset(g, 0, sizeof(g));
        for(int i = 0; i < n; i++) {
            scanf("%s", s);
            for(int j = 0; j < 4; j++)	 {
                for(int k = 0; k < 4; k++) {
                    if(j == k || s[2 * j] == '0' || s[2 * k] == '0')
                        continue;
                    int x = node(s[2 * j], s[2 * j + 1]);
                    int y = rnode(s[2 * k], s[2 * k + 1]);
                    g[x][y] = 1;
                }
            }
        }
        exist_cycle = 0;
        n = 52;
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    g[i][j] |= g[i][k]&g[k][j];
        }
        for(int i = 0; i < n; i++)
            exist_cycle |= g[i][i];
        puts(exist_cycle ? "unbounded" : "bounded");
    }
    return 0;
}
/*
3
A+00A+A+ 00B+D+A- B-C+00C+
1
K+K-Q+Q-
*/

Description

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

|-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
    A            B            C    
|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F    
|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

(Figure 1)

There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o’clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90’ (degrees) clockwise on those clocks which are affected according to figure 2 below.

(Figure 2)

Input

Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o’clock, 1=3 o’clock, 2=6 o’clock, 3=9 o’clock.

Output

Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o’clock. You are convinced that the answer is unique.

Sample Input

1
2
3

3 3 0
2 2 2
2 1 2

Sample Output

1

4 5 8 9

Solution

原來之前寫過這一題，請參閱 d730: 升旗典礼 ——加强版

用 BFS 從 0 0 0 0 0 0 0 0 0 開始倒推回去，在 mark 的部份，用 4 進制 bitmask。

這題在 POJ 似乎只有一組測資，在 Zerojudge 則有非常多筆測資。

而事實上網路上還有另外一個高斯消去法，先預求反矩陣，之後直接帶入計算即可。沒有仔細去研究，不過聽說那解法限定一定有合法解，如何判定不合法解又是另外一個問題。總之，用了 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

#include <stdio.h>
#include <queue>
using namespace std;
char mark[1<<18] = {}, ans[1<<18], best[1<<18];
char dirp[4] = {-3, 1, 1, 1};
int next[1<<18] = {};
int pow4[10] = {1};
int move[10][7] = { {},
                 	{1, 2, 4, 5, 0},
                 	{1, 2, 3, 0},
                 	{2, 3, 5, 6, 0},
                 	{1, 4, 7, 0},
                 	{2, 4, 5, 6, 8, 0},
                 	{3, 6, 9, 0},
                 	{4, 5, 7, 8, 0},
                 	{7, 8, 9, 0},
                 	{5, 6, 8, 9, 0}
                   };
void trans(int N, char s[]) {
    int i = 0;
    while(N) {
        s[i++] = N%4, N /= 4;
    }
}
void build() {
    int a, b, c, qt = 0, t, p;
    queue<int> Q;
    best[0] = 0, mark[0] = 1;
    Q.push(0);
    while(!Q.empty()) {
    	int state = Q.front();
    	Q.pop();
    	char buf[10] = {};
    	trans(state, buf);
    	for(int i = 1; i < 10; i++) {
    		int nstate = state;
    		for(int j = 0; move[i][j]; j++)
    			nstate -= pow4[move[i][j] - 1] * dirp[buf[move[i][j] - 1]];
    		if(mark[nstate] == 0) {
    			mark[nstate] = 1;
    			next[nstate] = state;
                best[nstate] = best[state] + 1;
                ans[nstate] = i + '0';
    			Q.push(nstate);
    		}
    	}
    }
}
int print_f = 0;
void Print(int state) {
    if(state) {
        Print(next[state]);
        if(print_f)
            putchar(' ');
        print_f = 1;
        putchar(ans[state]);
    }
}
int main() {
    for(int i = 1; i < 10; i++)
        pow4[i] = pow4[i-1] * 4;
    build();
    while(true) {
    	int state = 0, x;
        for(int i = 0; i < 9; i++) {
            if(scanf("%d", &x) != 1)
            	return 0;
            state |= x * pow4[i];
        }
        print_f = 0;
        Print(state);
        puts("");
    }
    return 0;
}  

Background

Ouroboros was a mythical snake in Ancient Egypt. It has its tail inside its mouth and continuously devours itself.

Problem

Ouroboros numbers are binary numbers of 2n bits that have the property of generating the whole set of numbers from 0 to 2n-1 as follows: To produce all of them we place the 2n bits wrapped in a circle so that the last bit goes before the first one. Then we can denote all 2n different strings with n bits starting each time with the next bit in the circle.

For example, for n=2 there are only four Ouroboros numbers. These are 0011, 0110, 1100 and 1001. For 0011, the following diagram and table depicts the process of finding all the bitstrings:

1
2
3
4
5

k 	00110011... 	o(n=2,k)
0 	00 	0
1 	 01 	1
2 	  11 	3
3 	   10 	2

Your program will compute the function o(n,k), where n > 0 and $0 \leq k < 2^n$. This function calculates the k-th number inside the smallest Ouroboros number of size n-bits.

Input

The input starts with a line containing the number of test cases. For each test case you will be given a line with two integers n (0 < n <22) and k ( 0 <= k < 2^n).

Output

For every test case your output must evaluate the function o(n,k) and print the result on a line by itself.

Sample Input

1
2
3
4
5

4 
2 0
2 1
2 2
2 3

Sample Output

1
2
3
4

0
1
3
2

Solution

題目描述：

有一個 2^n 個 bits 的環，而這個環恰好任取連續 n 個會湊滿 [0, 2^n - 1]，現在找一個字典順序最小的環，接著詢問這個環的某一個位置開始的數值。

題目解法：

當詢問 n bits 的結果時，可以把圖建成 2^(n-1) 個節點，每一個節點有兩條邊，邊上分別為 0, 1，也就是說只要繞過所有的邊，相當於產生所有 2^n 個數字。

由於每一個點的 indegree = outdegree 一定存在尤拉迴路，接著在有向圖中找到一條尤拉迴路即可。

至於找字典順序最小環，使用 周源最小表示法 來找，如果可以的話希望能在搜尋時順便找到字典順序最小的。這裡就沒有系不去探究了。

以下是一個最簡單的版本，但這個版本在生成尤拉迴路時會遭遇到 stackoverflow。

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

#include <stdio.h>
#include <string.h>
char g[1<<21][2] = {};
int n, mask, highbit;
char order[2][1<<21], *p;
void dfs(int node) {
    int prefix = node;
    prefix <<= 1;
    for(int i = 0; i < 2; i++) {
        if(g[node][i]) {
            g[node][i]--;
            dfs((prefix|i)&mask);
    		*p = (i) +'0', p++;
        }
    }
}
int MinExp(const char *s, const int slen) {
    int i = 0, j = 1, k = 0, x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)    x -= slen;
        if(y >= slen)    y -= slen;
        if(s[x] == s[y]) {
            k++;
        } else if(s[x] > s[y]) {
            i = j+1 > i+k+1 ? j+1 : i+k+1;
            k = 0;
            tmp = i, i = j, j = tmp;
        } else {
            j = i+1 > j+k+1 ? i+1 : j+k+1;
            k = 0;
        }
    }
    return i;
}
int main() {
    int testcase, K;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &K);
        mask = (1<<(n-1)) - 1;
        for(int i = (1<<(n-1)) - 1; i >= 0; i--) {
            g[i][0]++;
            g[i][1]++;
        }
        p = order[0];
        dfs(0);
        *p = '\0', p++;
        int len = strlen(order[0]);
        for(int i = len - 1, j = 0; i >= 0; i--, j++)
            order[1][i] = order[0][j];
        order[1][len] = '\0';
        int o1 = MinExp(order[0], len);
        int o2 = MinExp(order[1], len);
        int f = 0;
        for(int i = 0; i < len; i++) {
            if(order[0][(o1 + i)%len] != order[1][(o2 + i)%len]) {
                f = order[0][(o1 + i)%len] > order[1][(o2 + i)%len];
                break;
            }
        }
        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret = ret << 1;
            if(f == 0) {
                ret |= order[0][(o1 + i + K)%len] - '0';
            } else {
                ret |= order[1][(o2 + i + K)%len] - '0';
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

由於上述程式在走訪尤拉迴路時，由於深度過深而造成 stackoverflow 因此需要局部改寫成手動的 stack。通常主機只支持 10 萬到 20 萬之間的深度，這題最慘會到 100 萬。

並且將答案預建出來，如果沒有預建表會導致 Time limit，我以為只有少數幾筆，真是大錯特錯了。

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

#include <stdio.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
char g[1<<21][2] = {};
int n, mask;
char order[2][1<<21], *p;
char ouroboros[22][1<<21];
int olen[22];
void dfs(int node) {
    stack< pair<int, int> > stk;
    pair<int, int> state;
    int line;	
    stk.push(make_pair(node, 0));
    while(!stk.empty()) {
        state = stk.top(), stk.pop();
        node = state.first, line = state.second&3;
        if(line == 0) {
            int prefix = node << 1;
            if(g[node][0]) {
                g[node][0]--;
                stk.push(make_pair(node, 1|8));
                stk.push(make_pair((prefix|0)&mask, 0));
            } else {
                stk.push(make_pair(node, 1));
            }
        } else if(line == 1) {
            if(state.second&8) {
    			*p = (0) +'0', p++;
            }
            int prefix = node << 1;
            if(g[node][1]) {
                g[node][1]--;
                stk.push(make_pair(node, 2|8));
                stk.push(make_pair((prefix|1)&mask, 0));
            } else {
                stk.push(make_pair(node, 2));
            }
        } else {
            if(state.second&8) {
    			*p = (1) +'0', p++;
            }
        }
    }
}
int MinExp(const char *s, const int slen) {
    int i = 0, j = 1, k = 0, x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)    x -= slen;
        if(y >= slen)    y -= slen;
        if(s[x] == s[y]) {
            k++;
        } else if(s[x] > s[y]) {
            i = j+1 > i+k+1 ? j+1 : i+k+1;
            k = 0;
            tmp = i, i = j, j = tmp;
        } else {
            j = i+1 > j+k+1 ? i+1 : j+k+1;
            k = 0;
        }
    }
    return i;
}
void build() {
    for(int n = 1; n < 22; n++) {
        mask = (1<<(n-1)) - 1;
        for(int i = (1<<(n-1)) - 1; i >= 0; i--) {
            g[i][0]++;
            g[i][1]++;
        }
        p = order[0];
        dfs(0);
        *p = '\0', p++;
        int len = strlen(order[0]);
        for(int i = len - 1, j = 0; i >= 0; i--, j++)
            order[1][i] = order[0][j];
        order[1][len] = '\0';
        int o1 = MinExp(order[0], len);
        int o2 = MinExp(order[1], len);
        int f = 0;
        for(int i = 0; i < len; i++) {
            if(order[0][(o1 + i)%len] != order[1][(o2 + i)%len]) {
                f = order[0][(o1 + i)%len] > order[1][(o2 + i)%len];
                break;
            }
        }
        for(int i = 0; i < len; i++) {
            if(f == 0) {
                ouroboros[n][i] = order[0][(o1 + i)%len];
            } else {
                ouroboros[n][i] = order[1][(o2 + i)%len];
            }
        }
        olen[n] = len;
    }
}
int main() {
    int testcase, K;
    build();
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &K);
        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret = ret << 1;
            ret |= ouroboros[n][(i + K)%olen[n]] - '0';
        }
        printf("%d\n", ret);
    }
    return 0;
}

儘管如此世界依舊美麗 (Still world is beautiful それでもせかいはうつくしい 插曲) ，比預期中的還要好看，可能是人物屬性的關係讓我欲罷不能啊！順帶附了劇中歌曲，詳細請等待 OST，

Problem

Coffee cups of three different sizes (identified as size 1, size 2 and size 3 cups) are produced in factories under ACM (Association of Cup Makers) and are sold in various packages. Each type of package is identified by three positive integers (S1, S2, S3) where Si (1 <= i <= 3) denotes the number of size i cups included in the package. There is no package with S1 = S2 = S3.

But recently it has been discovered that there is a great demand for packages containing equal number cups of all three sizes. So, as an emergency step to meet the demand ACM has decided to unpack the cups from some of the packages stored in its (unlimited) stock of unsold products and repack them in packages having equal number of cups of all three sizes. For example, suppose ACM has the following four types of packages in its stock: (1, 2, 3), (1, 11, 5), (9, 4, 3) and (2, 3, 2). So, one can unpack three (1, 2, 3) packages, one (9, 4, 3) package and two (2, 3, 2) packages and repack the cups to produce sixteen (1, 1, 1) packages. One can even produce eight (2, 2, 2) packages or four (4, 4, 4) packages or two (8, 8, 8) packages or one (16, 16, 16) package or even different combination of packages each containing equal number of size 1, size 2 and size 3 cups. Note that all the unpacked cups are used to produce the new packages, i.e., no unpacked cup is wasted.

ACM has hired you to write a program that will decide whether it is possible to produce packages containing equal number of all three types of cups using all the cups that can be found by unpacking any combination of existing packages in the stock.

Input

The input may contain multiple test cases. Each test case begins with a line containing an integer N (3 <= N <= 1000) indicating the number of different types of packages that can be found in the stock. Each of the next N lines contains three positive integers denoting respectively the number of size 1, size 2 and size 3 cups in a package. No two packages in a test case will have the same specification.

A test case containing a zero for N in the first line terminates the input.

Output

For each test case in the input print a line containing “Yes” if packages can be produced as desired, print “No” otherwise.

Sample Input

1
2
3
4
5
6
7
8
9
10
11

4
1 2 3
1 11 5
9 4 3
2 3 2
4
1 3 3
1 11 5
9 4 3
2 3 2
0

Sample Output

1
2

Yes
No

Solution

題目描述：

咖啡杯有三種不同大小，出售的時候每一包三者都有不同個數，表示成 (S1, S2, S3) = (小, 中, 大)。

現在要將其重新包裝，每一種包假設有無限個數，問有沒有拆包的方式，滿足

x1 * (a1, b1, c1) + ... + xn * (an, bn, cn) = (k, k, k)

其中 x[i] >= 0 的非負整數, k 為非負整數，也就是重新包裝後要產生 k 個 (1, 1, 1)，以方便出售。

題目解法：

整數線性規劃就別來了，畢竟連 k 都沒有確定，解方程也不曉得解集合是否符合條件。

最後，重新考量 (S1, S2, S3)，如果以 S1 為基準，則產生 (S2 - S1, S3 - S1) 的向量。(因為最後還是要跟 S1 的總個數去計算，利用相對數量方式去降維。)，轉換原本的滿足方程

x1 * (y1, z1) + ... + xn * (yn, zn) = (0, 0)

• 如果兩個二維向量 (a, b) 和 (c, d)，對於任意 p (a, b) + q (c, d) 的結果可以產生兩個向量間任意角度(<= 180 deg)的向量 (不考慮向量長度，p, q 是非負整數)。

明白了上述條件後，將所有包分配至以原點拉出的向量，只要能產生兩個反向向量就可以相消找到 (0, 0) 向量。相消的條件很簡單，使用極角排序，相鄰兩個角度差全小於 pi 即有存在相消情況。

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

#include <stdio.h> 
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
    int n, S1, S2, S3;
    const double pi = acos(-1);
    while(scanf("%d", &n) == 1 && n) {
        double A[1024];
        for(int i = 0; i < n; i++) {
            scanf("%d %d %d", &S1, &S2, &S3);
            A[i] = atan2(S2 - S1, S3 - S1);
        }
        sort(A, A + n);
        double gap = 0;
        for(int i = 1; i < n; i++) {
            gap = max(gap, A[i] - A[i-1]);
        }
        gap = max(gap, 2 * pi - (A[n-1] - A[0]));
        puts(gap > pi ? "No" : "Yes");
    }
    return 0;
}

Problem

Bees are one of the most industrious insects. Since they collect nectarand pollen from owers, they have to rely on the trees in the forest. For simplicity they numbered the n trees from 0 to n - 1. Instead of roaming around all over the forest, they use a particular list of paths. A path is based on two trees, and they can move either way i.e. from one tree to another in straight line. They don’t use paths thatare not in their list.

As technology has been improved a lot, they also changed their working strategy. Instead of hovering over all the trees in the forest, they are targeting particular trees, mainly trees with lots of owers. So, they planned that they will build some new hives in some targeted trees. After that they will only collect their foods from these trees. They will also remove some paths from their list so that they don’t have to go to a tree with no hive in it.

Now, they want to build the hives such that if one of the paths in their new list go down (some
birds or animals disturbs them in that path) it’s still possible to go from any hive to another using the existing paths.

They don’t want to choose less than two trees and as hive-building requires a lot of work, they need to keep the number of hives as low as possible. Now you are given the trees with the paths they use, your task is to propose a new bee hive colony for them.

Input

Input starts with an integer T( T < 50), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers n (2 <= n <= 500) and m (0 < m< 20000), where n denotes the number of trees and m denotes the number of paths. Each of the next m lines contains two integers uv (0 < u , v < n), u = v) meaning that there is a path between tree u and v. Assume that there can be at most one path between tree u to v, and needless to say that a path will not be given more than once in the input.

Output

For each case, print the case number and the number of beehives in the proposed colony or impossible if its impossible to find such a colony.
NOTE:
Dataset is huge. Use faster I/O methods.

Sample Input

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

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

Sample Output

1
2
3

Case 1: 3
Case 2: impossible
Case 3: 3

Solution

題目描述：

在一個無向圖中，找到一個成本最小環。

題目解法：

Floyd 解法：
先來附一個錯誤版本，可以在 O(n^3) 解決，核心思路在於討論路徑上經過編號小於等於 k 時，同時探討最小環上經過編號 k 個所有環。但由於 n = 500 在此題中效率不好，但也不知道為什麼拿了 Runtime Error

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 <string.h>
#include <algorithm> 
using namespace std;
int g[512][512], w[512][512];
int main() {
    int testcase, cases = 0;
    int n, m, x, y;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                g[i][j] = w[i][j] = 0xf3f3f3f;
        while(m--) {
            scanf("%d %d", &x, &y);
            w[x][y] = w[y][x] = g[x][y] = g[y][x] = 1;
        }
        int ret = 0xf3f3f3f;
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    if(i != j)
                        ret = min(ret, w[k][i] + g[i][j] + w[j][k]);
                }
            }
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
        printf("Case %d: ", ++cases);
        if(ret == 0xf3f3f3f)
            puts("impossible");
        else
            printf("%d\n", ret);
    }
    return 0;
}

BFS 作法：
Floyd 用在成本不同的路徑上是有效的，但是在成本都是 1 的時候就有點太過了，使用 BFS 對於每一個點進行最短路徑，查看路徑樹上是否有 back edge。整體可以在 O(n^2) 完成，這個 back edge 可能會造成有重複走過點的環，但是不影響我們去找到最小成本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <stdio.h> 
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm> 
using namespace std;
vector<int> g[512];
int dist[512], parent[512];
int bfs(int st, int &ret) {
    memset(dist, 0, sizeof(dist));
    dist[st] = 1, parent[st] = -1;
    queue<int> Q;
    Q.push(st);
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if(v == parent[u])	continue;
            if(dist[v] == 0) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                Q.push(v);
            } else {
                ret = min(ret, dist[u] + dist[v] - 1);
            }
        }
    }
}
int main() {
    int testcase, cases = 0;
    int n, m, x, y;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            g[i].clear();
        while(m--) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int ret = n + 1;
        for(int i = 0; i < n; i++)
            bfs(i, ret);
        printf("Case %d: ", ++cases);
        if(ret == n + 1)
            puts("impossible");
        else
            printf("%d\n", ret);
    }
    return 0;
}

Problem

There are three jugs with a volume of a, b and c liters. (a, b, and c are positive integers not greater than 200). The first and the second jug are initially empty, while the third

is completely filled with water. It is allowed to pour water from one jug into another until either the first one is empty or the second one is full. This operation can be performed zero, one or more times.

You are to write a program that computes the least total amount of water that needs to be poured; so that at least one of the jugs contains exactly d liters of water (d is a positive integer not greater than 200). If it is not possible to measure d liters this way your program should find a smaller amount of water d’ < d which is closest to d and for which d’ liters could be produced. When d’ is found, your program should compute the least total amount of poured water needed to produce d’ liters in at least one of the jugs.

Input

The first line of input contains the number of test cases. In the next T lines, T test cases follow. Each test case is given in one line of input containing four space separated integers - a, b, c and d.

Output

The output consists of two integers separated by a single space. The first integer equals the least total amount (the sum of all waters you pour from one jug to another) of poured water. The second integer equals d, if d liters of water could be produced by such transformations, or equals the closest smaller value d’ that your program has found.

Sample Input

1
2
3

2
2 3 4 2
96 97 199 62

Sample Output

1
2

2 2
9859 62

Solution

題目描述：

有三個桶子，它們各能裝 a ， b ， 和 c 公升。（a , b , c 都為正整數而且不超過200。）第一，第二個桶子最剛開始是空的，但是第三個桶子卻是裝滿水的。你可以從 X 桶子把水倒入 Y 桶子裡並且把 Y 桶子裝滿，要不然就是把 X 桶子倒乾。倒水的步驟可以執行很多次。

你要寫一個程式去計算整個過程中至少要倒多少水才能達成目標，即這三個桶子中有一個桶子剩 d 公升的水。（d 為正整數而且不超過200。）但是如果你沒有辦法達成目標，也就是沒有辦法讓任何一個桶子剩下 d 公升的水，那麼請達成 d’ 公升，d’ 比 d小但是最接近 d。當 d’ 找到了，請你輸出整個過程至少要倒多少水才能達成 d’ 公升。

題目解法：

這題重新測試，導致之前寫的 DFS 方式直接 TLE 炸掉，只要改寫成 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

#include <stdio.h>
#include <queue>
using namespace std;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define oo 0xfffffff
int A, B, C, D, JUG[3];
int dp[201][201][201], res[201];
queue<int> QA, QB, QC, QTOT;
void pushNode(int a, int b, int c, int tot) {
    QA.push(a), QB.push(b), QC.push(c), QTOT.push(tot);
}
void update(int a, int b, int c, int tot) {
    if(tot >= res[D])   return;
    if(tot >= dp[a][b][c])  return;
    dp[a][b][c] = tot;
    res[a] = min(res[a], tot);
    res[b] = min(res[b], tot);
    res[c] = min(res[c], tot);
    if(a < B-b) pushNode(0, b+a, c, tot+a);
    else        pushNode(a-(B-b), B, c, tot+(B-b));
    if(a < C-c) pushNode(0, b, c+a, tot+a);
    else        pushNode(a-(C-c), b, C, tot+(C-c));
    if(b < A-a) pushNode(a+b, 0, c, tot+b);
    else        pushNode(A, b-(A-a), c, tot+(A-a));
    if(b < C-c) pushNode(a, 0, c+b, tot+b);
    else        pushNode(a, b-(C-c), C, tot+(C-c));
    if(c < A-a) pushNode(a+c, b, 0, tot+c);
    else        pushNode(A, b, c-(A-a), tot+(A-a));
    if(c < B-b) pushNode(a, b+c, 0, tot+c);
    else        pushNode(a, B, c-(B-b), tot+(B-b));
}
void bfs(int a, int b, int c, int tot) {
    QA.push(a), QB.push(b), QC.push(c), QTOT.push(tot);
    while (!QA.empty()) {
        a = QA.front(), QA.pop();
        b = QB.front(), QB.pop();
        c = QC.front(), QC.pop();
        tot = QTOT.front(), QTOT.pop();
        update(a, b, c, tot);
    }
    
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int i, j, k;
        scanf("%d %d %d %d", &A, &B, &C, &D);
        for(i = 0; i <= A; i++)
            for(j = 0; j <= B; j++)
                for(k = 0; k <= C; k++)
                    dp[i][j][k] = oo;
        JUG[0] = A, JUG[1] = B, JUG[2] = C;
        for(i = 0; i <= D; i++)
            res[i] = oo;
        bfs(0, 0, C, 0);
        while(res[D] == oo) D--;
        printf("%d %d\n", res[D], D);
    }
    return 0;
}

Problem

Carl is right now the happiest child in the world: he has just learned this morning what the binary system is. He learned, for instance, that the binary representation of a positive integer k is a string a[n], a[n-1], …, a[0] where each a[i] is a binary digit 0 or 1, starting with a[n] = 1, and such that k = \sum{i = 0, n} a[i] * 2^ i. It is really nice to see him turning decimal numbers into binary numbers, and then adding and even multiplying them.

Caesar is Carl’s older brother, and he just can’t stand to see his little brother so happy. So he has prepared a challenge: \Look Carl, I have an easy question for you: I will give you two integers A and B, and you have to tell me how many 1’s there are in the binary representation of all the integers from A to B, inclusive. Get ready”. Carl agreed to the challenge. After a few minutes, he came back with a list of the binary representation of all the integers from 1 to 100. \Caesar, I’m ready”. Caesar smiled and said: \Well, let me see, I choose A = 10^15 and B = 10^16. Your list will not be useful”.

Carl hates loosing to his brother so he needs a better solution fast. Can you help him ?

Input

The input file contains several test cases, each of them as described below.
A single line that contains two integers A and B (1 <= A <= B <= 10^16).

Output

For each test case, output a line with an integer representing the total number of digits 1 in the binary representation of all the integers from A to B, inclusive.

Sample Input

1
2
3

1000000000000000 10000000000000000
2 12
9007199254740992 9007199254740992

Sample Output

1
2
3

239502115812196372
21
1

Solution

題目描述：
計算 A 到 B 之間的二進制數出現了幾次 1。

題目解法：
將問題轉換成計算 0 到 A 出現了幾次 1，接著討論在相同長度下 1 出現的次數，之後再遞歸求解。

討論的時候，考慮長度為 n 時，每一位的填法，計算要看切割位置的前半和後半數字，詳細查閱代碼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long mpow(int n, int m) {
    long long ret = 1;
    for(int i = 1; i <= m; i++)
        ret *= n;
    return ret;
}
void ito2(long long n, char buf[]) {
    if(n == 0) {
        buf[0] = '0';
        buf[1] = '\0';
        return;
    }
    int i, j, f;
    for(i = 63, j = f = 0; i >= 0; i--) {
        if((n>>i)&1)	f = 1;
        if(f) {
            buf[j++] = ((n>>i)&1) + '0';
        }
    }
    buf[j] = '\0';
}
void a2toi(long long &r, char buf[]) {
    r = 0;
    for(int i = 0; buf[i]; i++)
        r = r<<1 | (buf[i] - '0');
}
void calc(long long n, long long cnt[]) {
    if(n <= 0)
        return;
    //printf("%d\n", n);
    char buf[105];
    ito2(n, buf);
    int len = strlen(buf);
    long long prev = 0;
    long long suffix;
    calc(mpow(2, len-1)-1, cnt);
    //for(int i = 0; i < 10; i++)
    //	cnt[i] = 0;
    long long prev10 = 1;
    for(int i = 0; i < len; i++) {
        int d = buf[i] - '0';
        a2toi(suffix, buf + i + 1);
        
        if(i != len-1)
            cnt[d] += suffix + 1;
        else
            cnt[d]++;
        if(i != 0)
            cnt[d] += (prev - prev10/2) * mpow(2, len-i-1);
        for(int j = i == 0; j < 2; j++) {
            if(j == d)	continue;
            if(j < d) {
                if(prev > 0) {
                    cnt[j] += (prev - prev10/2 + 1) * mpow(2, len-i-1);
                } else {
                    cnt[j] += mpow(2, len-i-1);
                }
            } else {
                if(prev > 0 && prev - prev10/2 > 0) {
                    cnt[j] += (prev - prev10/2) * mpow(2, len-i-1);
                }
            }
        }
        prev10 *= 2;
        prev = prev * 2 + d;
    }
}
int main() {
    long long A, B;
    while(scanf("%lld %lld", &A, &B) == 2) {
        long long cntA[2] = {}, cntB[2] = {};
        calc(A - 1, cntA);
        calc(B, cntB);
        printf("%lld\n", cntB[1] - cntA[1]);
    }
    return 0;
}

Problem

The archaeologists are going to decipher a very mysterious ``language”. Now, they know many language patterns; each pattern can be treated as a string on English letters (only lower case). As a sub string, these patterns may appear more than one times in a large text string (also only lower case English letters).

What matters most is that which patterns are the dominating patterns. Dominating pattern is the pattern whose appearing times is not less than other patterns.

It is your job to find the dominating pattern(s) and their appearing times.

Input

The entire input contains multi cases. The first line of each case is an integer, which is the number of patterns N, 1$\le$N$\le$150. Each of the following N lines contains one pattern, whose length is in range [1, 70]. The rest of the case is one line contains a large string as the text to lookup, whose length is up to 106.

At the end of the input file, number `0’ indicates the end of input file.

Output

For each of the input cases, output the appearing times of the dominating pattern(s). If there are more than one dominating pattern, output them in separate lines; and keep their input order to the output.

Sample Input

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

2 
aba 
bab 
ababababac 
6 
beta 
alpha 
haha 
delta 
dede 
tata 
dedeltalphahahahototatalpha 
0

Sample Output

1
2
3
4
5

4 
aba 
2 
alpha 
haha

Solution

題目描述：

給 N 個字串，問在 S 字串中哪些字串出現最多次。

題目解法：

對 N 個字串建造 AC 自動機，將 S 丟入自動機去計算給一個單詞出現次數。

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

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define maxKind 26
using namespace std;
struct Node{
    Node *fail;
    Node *next[maxKind];
    int cnt;
    int who;
    Node() {
        fail = NULL;
        cnt = 0;
        who = 0;
        memset(next, 0, sizeof(next));
    }
};
void build_Trie(const char* str, Node *root, int who) {
    Node *p = root;
    int i = 0, idx;
    while(str[i]) {
        if(str[i] >= 'a' && str[i] <= 'z')
            idx = str[i] - 'a';
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
        }
        p = p->next[idx];
        i++;
    }
    p->cnt++;
    p->who = who;
}
void build_AC_automation(Node *root) {
    root->fail = NULL;
    queue<Node*> Q;
    Q.push(root);
    Node *tn, *p;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(int i = 0; i < maxKind; i++) {
            if(tn->next[i] == NULL)
                continue;
            Q.push(tn->next[i]);
            p = tn->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                tn->next[i]->fail = root;
            else
                tn->next[i]->fail = p->next[i];
        }
    }
}
void free_AC_automation(Node *root) {
    queue<Node*> Q;
    Q.push(root);
    Node *tn, *p;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        for(int i = 0; i < maxKind; i++) {
            if(tn->next[i] != NULL) {
                Q.push(tn->next[i]);
            }
        }
        free(tn);
    }
}
void query(const char* str, Node *root, int cnt[]) {
    int i = 0, idx;
    Node *tn, *p;
    tn = root;
    while(str[i]) {
        if(str[i] >= 'a' && str[i] <= 'z')
            idx = str[i] - 'a';
        while(tn->next[idx] == NULL && tn != root)
            tn = tn->fail;
        tn = tn->next[idx];
        tn = (tn == NULL) ? root : tn;
        p = tn;
        while(p != root) {
        	if(p->cnt > 0)
            	cnt[p->who]++;
            p = p->fail;
        }
        i++;
    }
}
char buf[1048576], pattern[256][256];
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        Node *root = new Node();
        for(int i = 0; i < n; i++) {
        	scanf("%s", pattern[i]);
            build_Trie(pattern[i], root, i+1);
        }
        
        build_AC_automation(root);
        
        scanf("%s", buf);
        int cnt[256] = {};
        query(buf, root, cnt);
        free_AC_automation(root);
        int maxMatch = cnt[0];
        for(int i = 0; i < n; i++) {
        	maxMatch = max(maxMatch, cnt[i+1]);
        }
        printf("%d\n", maxMatch);
        for(int i = 0; i < n; i++) {
        	if(cnt[i+1] == maxMatch)
        		printf("%s\n", pattern[i]);
        }
    }
    return 0;
}