Problem

The Department of Recreation has decided that it must be more profitable, and it wants to sell advertising space along a popular jogging path at a local park. They have built a number of billboards (special signs for advertisements) along the path and have decided to sell advertising space on these billboards. Billboards are situated evenly along the jogging path, and they are given consecutive integer numbers corresponding to their order along the path. At most one advertisement can be placed on each billboard.

A particular client wishes to purchase advertising space on these billboards but needs guarantees that every jogger will see it’s advertisement at least K times while running along the path. However, different joggers run along different parts of the path.

Interviews with joggers revealed that each of them has chosen a section of the path which he/she likes to run along every day. Since advertisers care only about billboards seen by joggers, each jogger’s personal path can be identified by the sequence of billboards viewed during a run. Taking into account that billboards are numbered consecutively, it is sufficient to record the first and the last billboard numbers seen by each jogger.

Unfortunately, interviews with joggers also showed that some joggers don’t run far enough to see K billboards. Some of them are in such bad shape that they get to see only one billboard (here, the first and last billboard numbers for their path will be identical). Since out-of-shape joggers won’t get to see K billboards, the client requires that they see an advertisement on every billboard along their section of the path. Although this is not as good as them seeing K advertisements, this is the best that can be done and it’s enough to satisfy the client.

In order to reduce advertising costs, the client hires you to figure out how to minimize the number of billboards they need to pay for and, at the same time, satisfy stated requirements.

Input

The first line of the input consist of an integer indicating the number of test cases in theinput. Then there’s a blank line and the test cases separated by a blank line.

The first line of each test case contains two integers K and N (1 ≤ K, N ≤ 1000) separated by a space. K is the minimal number of advertisements that every jogger must see, and N is the total number of joggers.

The following N lines describe the path of each jogger. Each line contains two integers Ai and Bi (both numbers are not greater than 10000 by absolute value). Ai represents the first billboard number seen by jogger number i and Bi gives the last billboard number seen by that jogger. During a run, jogger i will see billboards Ai, Bi and all billboards between them.

Output

On the first line of the output fof each test case, write a single integer M. This number gives the minimal number of advertisements that should be placed on billboards in order to fulfill the client’s requirements. Then write M lines with one number on each line. These numbers give (in ascending order) the billboard numbers on which the client’s advertisements should be placed. Print a blank line between test cases.

Sample input

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

1
5 10
1 10
20 27
0 -3
15 15
8 2
7 30
-1 -10
27 20
2 9
14 21

Sample output for the sample input

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

19
-5
-4
-3
-2
-1
0
4
5
6
7
8
15
18
19
20
21
25
26
27

Solution

題目描述：

現在有 N 個慢跑者，每位慢跑者每天都會在固定的區間 [l, r] 中慢跑，廣告商希望每位跑者都能在跑的過程中見到 K 次廣告。

請問至少要在幾個整數點座標上放置廣告，才能使得每個跑者看到 K 次廣告。

題目解法：

貪心思維，對於右端點進行升排序，然後由左至右掃描，依序從其右端點開始放置需求的廣告數量。

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

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int testcase, N, K, l, r;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &K, &N);
        vector< pair<int, int> > D;
        for(int i = 0; i < N; i++) {
            scanf("%d %d", &l, &r);
            if(l > r)	swap(l, r);
            D.push_back(make_pair(r, l));
        }
        sort(D.begin(), D.end());
        
        int used[20005] = {}, ret = 0;
        const int shift = 10000;
        for(int i = 0; i < N; i++) {
            int has = 0, l = D[i].second, r = D[i].first;
            for(int j = l; j <= r; j++)
                has += used[j + shift];
            for(int j = r; j >= l && has< K; j--)
                if(!used[j + shift])
                    has++, used[j + shift] = 1, ret++;
        }
        printf("%d\n", ret);
        for(int i = 0; i < 20005; i++)
            if(used[i])
                printf("%d\n", i - shift);
        if(testcase)
            puts("");
    }
    return 0;
}

Problem

As Archimedes famously observed, if you put an object on a lever arm, it will exert a twisting force around the lever’s fulcrum. This twisting is called torque and is equal to the object’s weight multiplied by its distance from the fulcrum (the angle of the lever also comes in, but that does not concern us here). If the object is to the left of the fulcrum, the direction of the torque is counterclockwise; if the object is to the right, the direction is clockwise. To compute the torque around a support, simply sum all the torques of the individual objects on the lever.

The challenge is to keep the lever balanced while adjusting the objects on it. Assume you have a straight, evenly weighted board, 20 meters long and weighing three kilograms. The middle of the board is the center of mass, and we will call that position 0. So the possible positions on the board range from -10 (the left end) to +10 (the right end). The board is supported at positions -1.5 and +1.5 by two equal fulcrums, both two meters tall and standing on a flat floor. On the board are six packages, at positions -8, -4, -3, 2, 5 and 8, having weights of 4, 10, 10, 4, 7 and 8 kilograms, respectively as in the picture below.

Your job is to remove the packages one at a time in such a way that the board rests on both supports without tipping. The board would tip if the net torque around the left fulcrum (resulting from the weights of the packages and the board itself) were counterclockwise or if the net torque around the right fulcrum were clockwise. A possible solution to this problem is: first remove the package at position -4, then the package at 8, then -8, then 5, then -3 and finally 2.

You are to write a program which solves problems like the one described above. The input contains multiple cases. Each case starts with three integers: the length of the board (in meters, at least 3), the weight of the board (in kilograms) and n the number of packages on the board (n <= 20). The board is supported at positions -1.5 and +1.5 by two equal fulcrums, both two meters tall and standing on a flat floor. The following n lines contain two integers each: the position of a package on board (in meters measured from the center, negative means to the left) and the weight of the package (in kilograms). A line containing three 0’s ends the input. For each case you are to output the number of the case in the format shown below and then n lines each containing 2 integers, the position of a package and its weight, in an order in which the packages can be removed without causing the board to tip. If there is no solution for a case, output a single line Impossible. There is no solution if in the initial configuration the board is not balanced.

Sample input

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

20 3 6
-8 4
-4 10
-3 10
2 4
5 7
8 8
20 3 15
1 10 
8 5
-6 8
5 9
-8 4
8 10
-3 10
-4 5
2 9
-2 2
3 3
-3 2
5 1
-6 1
2 5
30 10 2
-8 100
9 91
0 0 0

Possible Output for sample input

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

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

Solution

題目描述：

給定一個木板，有兩個支撐點位於 -1.5 和 1.5 上，現在還附加了許多物件在木板上，要如何依序將物件拿起，同時不會讓木板因為不平衡而倒塌。

題目解法：

如何才能算是不平衡？

對於左支持點失去平衡為－其左力矩大於右力矩，因此向左傾斜
對於右支持點失去平衡為－其右力矩大於左力矩，因此向右傾斜

因此，根據貪婪的想法，中間 [-1.5, 1.5] 之間的物件肯定是最後才移走 (移走將減少力矩，因為它們貢獻給左支撐點的右力矩和右支持點的左力矩)。

之後，窮舉其他沒辦法判定的物件，依照產生的力矩由小到大依序窮舉，每一次決策要拿走左方還是右方最小力矩的物件，考慮較大力矩物件是沒有意義的。

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

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
int L, W, N, M;
vector< pair<int, int> > LEFT, RIGHT, D;
int find_flag; 
pair<int, int> path[128], pick[128];
int check(int n) {
    double LL, LR, RL, RR;
    LL = LR = RL = RR = 0;
    LL = RR = (L/2.0 - 1.5) * (L/2.0 - 1.5) * W / (double)L / 2;
    LR = RL = (L/2.0 + 1.5) * (L/2.0 + 1.5) * W / (double)L / 2;
    for(int i = 0; i < M; i++) {
        if(pick[i].first < -1.5) {
            LL += fabs(pick[i].first - (-1.5)) * pick[i].second;
        } else {
            LR += fabs(pick[i].first - (-1.5)) * pick[i].second;
        }
        if(pick[i].first < 1.5) {
            RL += fabs(pick[i].first - (1.5)) * pick[i].second;
        } else {
            RR += fabs(pick[i].first - (1.5)) * pick[i].second;
        }
    }
    for(int i = 0; i <= n; i++) {
        if(path[i].first < -1.5) {
            LL += fabs(path[i].first - (-1.5)) * path[i].second;
        } else {
            LR += fabs(path[i].first - (-1.5)) * path[i].second;
        }
        if(path[i].first < 1.5) {
            RL += fabs(path[i].first - (1.5)) * path[i].second;
        } else {
            RR += fabs(path[i].first - (1.5)) * path[i].second;
        }
    }
    return LL <= LR && RR <= RL;
}
void dfs(int l, int r, int dep) {
    if(l == LEFT.size() && r == RIGHT.size()) {
        find_flag = 1;
        for(int i = dep-1; i >= 0; i--)
            printf("%d %d\n", path[i].first, path[i].second);		
        for(int i = 0; i < M; i++)
            printf("%d %d\n", pick[i].first, pick[i].second);
        return;
    }
    if(l < LEFT.size()) {
        path[dep] = D[LEFT[l].second];
        if(check(dep))
            dfs(l+1, r, dep+1);
        if(find_flag)	return;
    }
    if(r < RIGHT.size()) {
        path[dep] = D[RIGHT[r].second];
        if(check(dep))
            dfs(l, r+1, dep+1);
        if(find_flag)	return;
    }
}
int main() {
    int cases = 0, p, q;
    while(scanf("%d %d %d", &L, &W, &N) == 3 && L + W + N) {
        LEFT.clear(), RIGHT.clear(), D.clear();
        M = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d %d", &p, &q);
            D.push_back(make_pair(p, q));
            if(abs(p) < 1.5) {
                pick[M++] = make_pair(p, q);
                continue;
            }
            if(p < 0) {
                LEFT.push_back(make_pair((fabs(2*p) - 3) * q, i));
            } else {
                RIGHT.push_back(make_pair((fabs(2*p) - 3) * q, i));
            }
        }
        sort(LEFT.begin(), LEFT.end());
        sort(RIGHT.begin(), RIGHT.end());
        find_flag = 0;
        printf("Case %d:\n", ++cases);
        dfs(0, 0, 0);
        if(!find_flag)
            puts("Impossible");
    }	
    return 0;
}

Problem

Some time the programmers have very strange ways to hide their passwords. See for example how Billy “Hacker” Geits hide his password. Billy chooses a string S composed of small Latin letters with length L. Then he makes all L- 1 one-letter left cyclic shifts of the string and takes as a password one prefix of the lexicographically first of the obtained strings (including S). For example let consider the string alabala. The cyclic one-letter left shifts (including the initial string) are:

alabala
labalaa
abalaal
balaala
alaalab
laalaba
aalabal

and lexicographically first of them is the string aalabal. The first letter of this string is in position 6 in the initial string (the positions in the string are counted from 0).

Write a program that for given string S finds the start position of the smallest lexicographically one-letter left cyclic shift of this string. If the smallest lexicographically left shift appears more than once then the program have to output the smallest initial position.

Input

Your program has to be ready to solve more than one test case. The first line of the input file will contains only the number T of the test cases. Each of the following T lines will describe one test case - first the length L of the string (5 <= L <= 100000) and then, separated by one space, the string S itself.

Output

The output file have to contain exactly T lines with a single number each - the initial position found by your program.

Sample Input

1
2
3

2
6 baabaa
7 alabala

Sample Output

1
2

1
6

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

#include <stdio.h>
#include <string.h>
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, n;
    char s[100005];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %s", &n, s);
        printf("%d\n", MinExp(s, n));
    }
    return 0;
}

Problem

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.

There are two machines A and B . Machine A has n kinds of working modes, which is called mode0 , mode1 , … , moden-1 , likewise machine B has m kinds of working modes, mode0 , mode1 , … , modem-1 . At the beginning they are both work at mode0 .

For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode3 or in machine B at mode4 , job 1 can either be processed in machine A at mode2 or in machine B at mode4 , and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y) , which means it can be processed either in machine A at modex , or in machine B at modey .

Obviously, to accomplish all the jobs, we need to change the machine’s working mode from time to time, but unfortunately, the machine’s working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.

Input

The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n , m (n, m < 100) and k (k < 1000) . The following k lines give the constrains of the k jobs, each line is a triple: i, x, y .

The input will be terminated by a line containing a single zero.

Output

The output should be one integer per line, which means the minimal times of restarting machine.

Sample Input

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

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

Sample Output

1

3

Solution

題目描述：

有兩台機器 A, B，各自擁有 n 和 m 個模式，在 k 個工作中，每一個工作可以在 A 機器的 a 模式或者是 B 機器的 b 模式下完成。

一開始兩台機器皆處於模式 0，而轉換模式是很費時間，希望轉換次數越少越好來完成所有工作。

題目解法：

由於一開始處於模式 0，所以工作在模式 0 下可以完成的全部忽略！

接著考慮建二分圖，分別對每一個工作所需要的模式 a, b 拉邊，最後會採用最少點集覆蓋所有條邊即可。

二分圖最少點集覆蓋 = 二分圖最大匹配數

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 <math.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
    int y;
    int next;
} edge[10005];
int e, head[105];
void addEdge(int x, int y) {
    edge[e].y = y;
    edge[e].next = head[x], head[x] = e++;
}
int mx[105], my[105], used[105];
int dfs(int now) {
    int i, x;
    for(i = head[now]; i != -1; i = edge[i].next) {
        x = edge[i].y;
        if(!used[x]) {
            used[x] = 1;
            if(my[x] == -1 || dfs(my[x])) {
                mx[now] = x, my[x] = now;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    int N, M, K, u, v;
    while(scanf("%d %d %d", &N, &M, &K) == 3 && N) {
        e = 0;
    	memset(head, -1, sizeof(head));	
    	for(int i = 0; i < K; i++) {
    		scanf("%*d %d %d", &u, &v);
    		if(u > 0 && v > 0)
    			addEdge(u, v);
    	}
    	memset(mx, -1, sizeof(mx));
        memset(my, -1, sizeof(my));
        int match = 0;
        for(int i = 0; i < N; i++) {
            if(mx[i] == -1) {
                memset(used, 0, sizeof(used));
                if(dfs(i))
                    match++;
            }
        }
        printf("%d\n", match);
    }
    return 0;
}

Problem

Wars have played a significant role in world history. Unlike modern wars, armies in the middle ages were principally concerned with capturing and holding castles, the private fortified residences of lords and nobles. The size of the attacking army was an important factor in an army’s ability to capture and hold one of these architectural masterpieces.

\epsfbox{p4788.eps}

A certain minimum number of soldiers were required to capture a castle. Some soldiers were expected to die during the attack. After capturing the castle, some soldiers were required to remain in the castle to defend it against attacks from another enemy. Of course, those numbers were different for different castles. Commanders of the armies were obliged to consider the number of soldiers required for victory. For example, there are five castles in the region map shown in Figure 2. The castle at the lower right requires at least 20 soldiers to wage a winning attack. None are expected to perish during the attack, and 10 soldiers must be left in the castle when the army moves on.

In this problem you must determine the minimum size of an army needed to capture and hold all the castles in a particular region. For reasons of security, there is exactly one (bi-directional) route between any pair of castles in the region. Moving into the neighborhood of an uncaptured castle begins an attack on that castle. Any castle can serve as the first castle to be attacked, without regard for how the army got there. Once any castle has been captured, the requisite number of soldiers is left in the castle to defend it, and the remainder of the army moves on to do battle at another castle, if any remain uncaptured. The army may safely pass through the neighborhood of a castle that it has already captured. But because of the potential for attacks, the army may traverse the route between a pair of castles no more than twice (that is, at most once in each direction).

Input

The input contains multiple test cases corresponding to different regions. The description of the castles in each region occupies several lines. The first line contains an integer n$\le$100 that is the number of castles in the region. Each of the next n lines contains three integers a, m, and g (1$\le$a$\le$1000, 0$\le$m$\le$a, 1$\le$g$\le$1000), that give the minimum number of soldiers required to successfully attack and capture a particular castle, the number of soldiers that are expected to die during the attack, and the number of soldiers that must be left at the castle to defend it. The castles are numbered 1 to n, and the input lines describing them are given in increasing order of castle numbers. Each of the remaining n - 1 lines in a test case has two integers that specify the castle numbers of a pair of castles that are connected by a direct route.

A line containing 0 follows the description of the last region.

Output

For each test case, display the case number and the minimum number of soldiers in the army needed to conquer all the castles in the region. Follow the format shown in the sample output.

Sample Input

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

3 
5 5 5 
10 5 5 
5 1 1 
1 3 
2 3 
5 
10 5 10 
20 10 5 
10 10 5 
5 5 5 
20 0 10 
1 2 
1 3 
1 4 
3 5 
0

Sample Output

1
2

Case 1: 22 
Case 2: 65

Solution

題目描述：

攻略一個城堡會有幾個需求，第一，戰爭時最少的士兵數，第二，在這場戰爭中犧牲的士兵，第三，離開此城堡時，必須留下多少士兵駐守。

題目特別說明到，要用最少數量的士兵佔領所有的城堡，而每一座城堡之間都有路徑，必且佔領過程中每一條路徑的單一方向只能經過一次，所有城堡構成的圖恰好為一棵樹，每一條路徑為雙向道。

題目解法：

由於給定圖為樹，同時每一個方向只能經過一次，也就是說從某一點當作根開始走訪，一旦選擇一個子樹進行探訪，就必須完整地將子樹的城堡都佔領，才能去佔領其他子樹中的城堡，意味著，每個子樹的最優解將可以合併成整棵樹的最優解。

因此，對於子樹紀錄狀態為 (戰爭時最少士兵數量，佔領後遺失士兵數量)，在做最優解合併的時，採用貪婪的作法。

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

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> g[105];
pair<int, int> D[105];
bool cmp(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first)
        return a.first > b.first;
    return a.second < b.second;
}
pair<int, int> dfs(int u, int p) {
    vector< pair<int, int> > branch;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v != p)
            branch.push_back(dfs(v, u));
    }
    sort(branch.begin(), branch.end(), cmp);
    int a, b;
    a = D[u].first, b = D[u].second;
    for(int i = 0; i < branch.size(); i++) {
        a = max(a, b + branch[i].first);
        b += branch[i].second;
    }
    return make_pair(max(a, b), b);
    
}
int main() {
    int cases = 0, a, m, gg, u, v;
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf("%d %d %d", &a, &m, &gg);	
            D[i] = make_pair(max(a, m+gg), m + gg);
        }
        for(int i = 1; i <= N; i++)
            g[i].clear();
        for(int i = 1; i < N; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        pair<int, int> ret = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
        for(int i = 1; i <= N; i++) 
            ret = min(ret, dfs(i, -1));
        printf("Case %d: %d\n", ++cases, ret.first);
    }
    return 0;
}

Problem

A simple solitaire card game called 10-20-30 uses a standard deck of 52 playing cards in which suit is irrelevant. The value of a face card (king, queen, jack) is 10. The value of an ace is one. The value of each of the other cards is the face value of the card (2, 3, 4, etc.). Cards are dealt from the top of the deck. You begin by dealing out seven cards, left to right forming seven piles. After playing a card on the rightmost pile, the next pile upon which you play a card is the leftmost pile.

For each card placed on a pile, check that pile to see if one of the following three card combinations totals 10, 20, or 30.

1. the first two and last one,

2. the first one and the last two, or

3. the last three cards.

If so, pick up the three cards and place them on the bottom of the deck. For this problem, always check the pile in the order just described. Collect the cards in the order they appear on the pile and put them at the bottom of the deck. Picking up three cards may expose three more cards that can be picked up. If so, pick them up. Continue until no more sets of three can be picked up from the pile.

For example, suppose a pile contains 5 9 7 3 where the 5 is at the first card of the pile, and then a 6 is played. The first two cards plus the last card (5 + 9 + 6) sum to 20. The new contents of the pile after picking up those three cards becomes 7 3. Also, the bottommost card in the deck is now the 6, the card above it is the 9, and the one above the 9 is the 5.

If a queen were played instead of the six, 5 + 9 + 10 = 24, and 5 + 3 + 10 = 18, but 7 + 3 + 10 = 20, so the last three cards would be picked up, leaving the pile as 5 9.

If a pile contains only three cards when the three sum to 10, 20, or 30, then the pile “disappears” when the cards are picked up. That is, subsequent play skips over the position that the now-empty pile occupied. You win if all the piles disappear. You lose if you are unable to deal a card. It is also possible to have a draw if neither of the previous two conditions ever occurs.

Write a program that will play games of 10-20-30 given initial card decks as input.

Input

Each input set consists of a sequence of 52 integers separated by spaces and/or ends of line. The integers represent card values of the initial deck for that game. The first integer is the top card of the deck. Input is terminated by a single zero (0) following the last deck.

Output

For each input set, print whether the result of the game is a win, loss, or a draw, and print the number of times a card is dealt before the game results can be determined. (A draw occurs as soon as the state of the game is repeated.) Use the format shown in the ``Sample Output” section.

Sample Input

1
2
3
4
5
6
7

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

Sample Output

1
2
3

Win : 66
Loss: 82
Draw: 73

Solution

給一副牌，按照順序發成七疊
在發了一張牌後，若有
(1) 下面一張與最上面兩張
(2) 下面兩張與最上面一張
(3) 最上面連續三張加起來點數為
10、20 或 30，則把這三張牌收進手牌(J, Q, K, 10)
依 (1)(2)(3) 順序檢查

若某疊牌拿起三張後仍符合上述條件，則一直拿到不符合條件為止，若有某一疊牌被完全拿光，則以後不在往這疊發牌。

請輸出最後結果
(1) win 七疊牌都清空了
(2) lose 手牌空了
(3) draw 進入無窮迴圈

簡單地說，一開始盤面上有七疊牌組，一開始都有兩張牌，接著依序從左邊至右開始發牌，發的同時依序檢查是否可以將牌組的牌符合 10-20-30 的規則收回手牌 (發牌者手上) 中。

最麻煩的地方在於迴圈判斷，在這裡使用一個最簡單的 binary tree 方式。

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

#include <stdio.h> 
#include <string.h>
#include <deque>
#include <queue>
#include <set>
using namespace std;
struct state {
    int v[64];
    state() {
        memset(v, 0, sizeof(v));
    }
    bool operator<(const state &x) const {
        return memcmp(v, x.v, sizeof(state)) < 0;
    }
};
deque<int> pile[7];
queue<int> hand;
set<state> record;
void reduce(deque<int> &pile) {
    while(pile.size() >= 3) {
        int n = pile.size();
        if((pile[0] + pile[1] + pile[n-1])%10 == 0) {
            hand.push(pile[0]), hand.push(pile[1]), hand.push(pile[n-1]);
            pile.pop_front();
            pile.pop_front();
            pile.pop_back();
        } else if((pile[0] + pile[n-2] + pile[n-1])%10 == 0) {
            hand.push(pile[0]), hand.push(pile[n-2]), hand.push(pile[n-1]);
            pile.pop_front();
            pile.pop_back();
            pile.pop_back();
        } else if((pile[n-3] + pile[n-2] + pile[n-1])%10 == 0) {
            hand.push(pile[n-3]), hand.push(pile[n-2]), hand.push(pile[n-1]);
            pile.pop_back();
            pile.pop_back();
            pile.pop_back();
        } else {
            break;
        }
    }
}
int main() {
    int x;
    while(true) {
        while(!hand.empty())
            hand.pop();
        for(int i = 0; i < 7; i++) 
            pile[i].clear();
            
        for(int i = 0; i < 52; i++) {
            scanf("%d", &x);
            if(x == 0)	return 0;
            hand.push(x);
        }
        for(int i = 0; i < 7; i++)
            pile[i].push_back(hand.front()), hand.pop();
        
        for(int i = 0; i < 7; i++)
            pile[i].push_back(hand.front()), hand.pop();
        
        int end = 0, loop = 14;
        while(!end) {
            for(int i = 0; i < 7; i++) {
                if(pile[i].size() == 0)
                    continue;
                loop++;
                pile[i].push_back(hand.front()), hand.pop();
                reduce(pile[i]);
                if(hand.size() == 52) {
                    printf("Win : %d\n", loop);
                    end = 1;
                    break;
                }
                if(hand.size() == 0) {
                    printf("Loss: %d\n", loop);
                    end = 1;
                    break;
                }
                state s;
                int m = 0;
                for(int j = 0; j < 7; j++) {
                    for(int k = 0; k < pile[j].size(); k++)
                        s.v[m++] = pile[j][k];
                    s.v[m++] = 15;
                }
                queue<int> q = hand;
                while(!q.empty())
                    s.v[m++] = q.front(), q.pop();
                s.v[m++] = 15;
                if(record.find(s) != record.end()) {
                    printf("Draw: %d\n", loop);
                    end = 1;
                    break;
                }
                record.insert(s);
            }
        }
    }
    return 0;
}

題目描述

求 k < 20 的所有情況，並且把方程式列出。

Solution

當初在推倒$\sum_{i = 1}^{n} i^{2}$ 的時候，採用的方式如下：

首先，升一次觀察：

整理，將$i^{2}$ 移到單獨項

此時特別計算$\sum_{i = 1}^{n} (i + 1)^{3} - i^{2}$，易見答案為$(n+1)^{3} - 1$

最後得到
$$\begin{align*} & \Rightarrow \sum_{i = 1}^{n} i^{2} = \frac{1}{3} ((n+1)^{3} - 1 + \sum_{i = 1}^{n} (-3i-1)) \end{align*}$$

藉由上述的推倒過程，可以擴充至更高維度的計算。

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

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
long long C[25][25] = {};
long long M[25] = {}, A[25][25] = {};
long long llabs(long long v) {
    return v < 0 ? -v : v;
}
void init() {
    C[0][0] = 1;
    for(int i = 1; i < 25; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
    // sum of powers
    M[0] = 1, A[0][1] = 1; // sigma(k^0) = n
    for(int i = 1; i <= 20; i++)  {
        M[i] = i + 1;
        long long val = 1;
        for(int j = 0; j <= i - 1; j++)
            val = val / __gcd(val, M[j]) * M[j];
        M[i] *= val;
//		printf("%lld %lld\n", M[i], val);
        for(int j = 0; j <= i - 1; j++)
            for(int k = 0; k <= j + 1; k++)
                A[i][k] -= A[j][k] * val / M[j] * C[i + 1][j];
        for(int j = 0; j <= i + 1; j++)
            A[i][j] += val * C[i+1][j];
        A[i][0] -= val * 1;
        long long g = M[i];
        for(int j = 0; j <= i + 1; j++)
            g = __gcd(g, llabs(A[i][j]));
        M[i] /= g;
        for(int j = 0; j <= i + 1; j++)
            A[i][j] /= g;
    }
}
/*
find sigma(i^2)
(i + 1)^3 - (i)^2 = 3*(i)^2 + 3i + 1
=> i^2 = 1/3 * ((i + 1)^3 - (i)^2 - 3i - 1)
=> sigma(i^2) = sigma(1/3 * ((i + 1)^3 - (i)^2 - 3i - 1))
=>            = 1/3 (sigma((i + 1)^3 - (i)^2) + sigma(-3i - 1)) 
=> // sigma((i + 1)^3 - (i)^3) = (n + 1)^3 - 1
=>            = 1/3 ((n + 1)^3 - 1 + sigma(-3i - 1)) 
... so
 */
int main() {
    init();
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        printf("%lld", M[n]);
        for(int i = n + 1; i >= 0; i--)
            printf(" %lld", A[n][i]);
        puts("");
        if(testcase)
            puts("");
    }
    return 0;
}

題目描述

對於任一區間 [l, r] 找到一個最小值 a[m] 其中 l <= m <= r，計算

並且把所有 f(l, r) 加總起來。

Solution

要將所有情況加總，因此會有 C(n, 2) 個對。

反過來思考，對於每一個最小值 a[m] 來說，有多少區間會使用到它進行計算。也就是說，找到一個最大的區間 [l, r] 包含 a[m]，同時這個區間內的數字皆大於等於 a[m]。

則對於 a[m] 而言，會找到一個最大的區間 [l, m, r]，會有 (m - l + 1) * (r - m + 1) 個區間會認定 a[m] 是該區間的最小值，則直接計算即可。

但這裡也存有一個很大的問題，會有兩個相同小的數字，特別處理它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 65536
#define INF 0x3f3f3f3f
long long sum[MAXN], ssum[MAXN], isum[MAXN], issum[MAXN];
// binary indexed tree
int BIT[MAXN<<1];
int query(int x) {
    int ret = 0;
    while(x) {
        ret = max(ret, BIT[x]);
        x -= x&(-x);
    }
    return ret;
}
void modify(int x, int v, int L) {
    while(x <= L) {
        BIT[x] = max(BIT[x], v);
        x += x&(-x);
    }
}
int query2(int x) {
    int ret = INF;
    while(x) {
        ret = min(ret, BIT[x]);
        x -= x&(-x);
    }
    return ret;
}
void modify2(int x, int v, int L) {
    while(x <= L) {
        BIT[x] = min(BIT[x], v);
        x += x&(-x);
    }
}
int cases = 0, preA[MAXN], sufA[MAXN], start[MAXN], cover[MAXN<<1];
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int testcase, n, A[MAXN];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &A[i]), start[i] = 0, cover[A[i] + MAXN] = -1;
        
        int L = 50000 + MAXN;
        for(int i = 0; i <= L; i++)
            BIT[i] = 0;
        for(int i = 1; i <= n; i++) {
            preA[i] = query(A[i] + MAXN);
            modify(A[i]+MAXN, i, L);
            if(preA[i] <= cover[A[i] + MAXN])
                start[i] = cover[A[i] + MAXN] + 1;
            cover[A[i] + MAXN] = i;
        }
        for(int i = 0; i <= L; i++)
            BIT[i] = n + 1;
        for(int i = n; i >= 1; i--) {
            sufA[i] = query2(A[i] + MAXN);
            modify2(A[i]+MAXN+1, i, L);
        }
        
        for(int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + A[i];
        for(int i = 1; i <= n; i++)
            ssum[i] = ssum[i-1] + sum[i];
            
        isum[n+1] = issum[n+1] = 0;
        for(int i = n; i >= 1; i--)
            isum[i] = isum[i+1] + A[i];
        for(int i = n; i >= 1; i--)
            issum[i] = issum[i+1] + isum[i];
        
        long long ret = 0;
        for(int i = 1; i <= n; i++) {
            long long suma, a, sumb, b;
            if(start[i]) {
                suma = issum[start[i]] - issum[i], a = i - start[i];
                sumb = ssum[sufA[i]-1] - ssum[i], b = sufA[i] - i - 1;
                suma -= isum[i] * a;
                sumb -= sum[i] * b;
            } else {
                suma = issum[preA[i]+1] - issum[i], a = i - preA[i] - 1;
                sumb = ssum[sufA[i]-1] - ssum[i], b = sufA[i] - i - 1;
                suma -= isum[i] * a;
                sumb -= sum[i] * b;
            }
//			printf("index %d\n", i);
//			printf("%lld %lld\n", ssum[sufA[i]-1], ssum[i]);
//			printf("%lld %lld %lld %lld -- %lld\n", suma, a, sumb, b, (suma - A[i]*a*(a+1)/2) * (b + 1) + (sumb - A[i]*b*(b+1)/2) * (a + 1));
            ret += (suma - A[i]*a*(a+1)/2) * (b + 1) + (sumb - A[i]*b*(b+1)/2) * (a + 1);
//			long long test = 0;
//			for(int j = i; j >= 1; j--) {
//				if(A[j] < A[i])
//					break;
//				for(int k = i; k <= n; k++) {
//					if(A[k] < A[i])	break;
//					for(int l = j; l <= k; l++)
//						test += A[l] - A[i];
//				}
//			}
//			printf("DEBUG %lld\n", test);
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
1
5
1 2 3 4 5
10
10
-7 2 -6 7 -9 5 -5 -3 9 3 
10
1 -7 9 2 4 7 -10 8 0 0 
10
-8 9 4 -8 1 2 -3 2 8 8 
10
-3 -4 0 -2 5 9 -3 -4 2 1 
10
3 -8 -9 -4 8 -9 -7 6 -10 -9 
10
-7 0 -2 8 -6 6 9 -5 -1 -3 
10
1 -10 7 -1 7 -10 5 -1 -10 9 
10
-2 9 -8 8 -7 0 -1 -8 7 -9 
10
-9 2 3 -8 -10 9 7 9 1 3 
10
3 5 1 -4 -6 -3 0 2 -5 -5 
*/

Input

The input will contain several test cases. First line of the input is the an integer which indicate the number of test case followed by a blank line. Each consecutive test case will also separated by a blank line.

Each test case gets 25 cards, 5 cards per line. Each card consists of two characters. The first represents the rank of the card: A',2’, 3',4’, 5',6’, 7',8’, 9',X’, J',Q’, K'. The second represents the suit of the card:S’, H',D’, `C’.

The cards are dealt into a tex2html_wrap_inline44 square. Each row and column is evaluated to determine the highest hand type for which its 5 cards qualify. The hand types, from low to high, are Nothing, Pair, Two Pair, Three of a Kind, Straight, Flush, Full House, Four of a Kind, Straight Flush. A hand qualifies only once, and then only for its highest type. For example, a Four of a Kind does not count as two pair or three of a kind.

Output

For each test case output a list of 9 integers, telling how many hands of each handtype were found. from lowest to highest, being:

Nothing: does not qualify as any of the following. Example: AC, 3H, QS, JD, 7D.

One Pair: contains two cards of the same rank and does not qualify for any of the following. Example: 2C, 3H, 4H, 2H, KD.

Two Pair: contains two cards of one rank and two cards of another and does not qualify for any of the following. Example: 2C, 3H, 4H, 2H, 4D.

Three of a Kind: contains three cards of the same rank and does not qualify for any of the following. Example: QS, KH, 2C, QD, QC.

Straight: the five cards of the hand may be sorted on rank so that an unbroken sequence of 5 ranks is formed and the hand does not qualify for any of the following. There can be cycle through Ace. That is AC, 2H, 4D, 3H, 5S forms a straight, as does JH, XD,QC, KD, AS and QC, KD, AS, 2H, 3D.

Flush: the five cards are all of the same suit and the hand does not qualify for any of the following. Example: 5D, AD, KD, 7D, QD.

Full House: the hand contains three cards of one rank and two cards of another. Example: 3C, QS, QD, 3H, 3S.

Four of a kind: the hand contains four cards of the same rank. Example: AS, AD, AH, 7C, AC.

Straight Flush: the hand meets the criteria for being both a straight and a flush. 

Two consecutive output will separated by a blank line.

For the example below, the five rows evaluate to Straight Flush, Straight, Pair, Flush, Three of a Kind. The Five columns evaluate to Four of A Kind, Full House, Two Pair, Nothing, and Two Pair.

Sample Input

1
2
3
4
5
6
7

1
AS 2S 3S 4S 5S
AC 2H 3H 5C 4C
AH 2D KC KH 5D
AD 3D KD 9D 8D
XH 3C XC XS 8C

Sample Output

1

1, 1, 2, 1, 1, 1, 1, 1, 1

Solution

一張撲克牌有花色（Clubs, Diamonds, Hearts, Spades，分別以C，D，H，S來代表）及點數（2,3,4,5,6,7,8,9,10, jack, queen, king, ace，分別以2,3,4,5,6,7,8,9,X,J,Q,K,A來代表）。有一種常見的撲克牌遊戲叫”梭哈”（就是你在電影賭神中常見的那種遊戲），每個人手上有5張牌，並且依照以下的規則給予每手牌1-9的整數值。注意：每手牌只能有一個值（高的那一個），例如：Four of a kind就不能算為two pairs 或 three of a kind.

1. Nothing:（中文翻譯：不知道，就是最爛的就是了）沒有以下任何情況就屬於nothing。例如：AH 9D 7C 3H 2D
2. One pair:（中文翻譯：1對）有2張牌同一個點數，另3張牌皆不同點數。例如：8H 8D KC 5H 2D
3. Two pairs:（中文翻譯：2對）有2組2張牌同一個點數，另1張牌不同點數。例如：8H 8D 5C 5H 9D
4. Three of a kind:（中文翻譯：3條）3張牌同一個點數，另2張牌不同點數。例如：8H 8D 8C AH 9D
5. Straight:（中文翻譯：順子）5張牌的點數為連續的並且可以A連接2成一圈。（所以：點數T J Q K A是順子，A 2 3 4 5是順子，Q K A 2 3也是順子）例如：8H 9H TH JH QD
6. Flush:（中文翻譯：同花）5張牌同一花色。例如：6H 9H TH JH QH
7. Full House:（中文翻譯：葫蘆）3張同一點數，另2張同一點數。例如：8H 8D 8C 7S 7D
8. Four of a kind:（中文翻譯：4條或鐵枝）4張牌同一個點數。例如：8H 8D 8C 8S 9D
9. Straight flush: （中文翻譯：同花順）5張牌同一花色，並且形成一個順子。例如：8H 9H TH JH QH

給你25張牌排成5*5的樣子。你的任務就是算出5列（橫的）及5欄（直的）這10手牌所形成的統計結果。

依序判斷，只能硬暴。

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

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
int getSuit(char c) {
    switch(c) {
        case 'C': return 0;
        case 'D': return 1;
        case 'H': return 2;
        case 'S': return 3;
    }
}
int getRank(char c) {
    switch(c) {
        case '0' ... '9': return c - '0';
        case 'A': return 1;
        case 'X': return 10;
        case 'J': return 11;
        case 'Q': return 12;
        case 'K': return 13;
    } 
}
bool suitCmp(pair<int, int> x, pair<int, int> y) {
    if(x.first != y.first)
        return x.first < y.first;
    return x.second < y.second;
}
bool rankCmp(pair<int, int> x, pair<int, int> y) {
    if(x.second != y.second)
        return x.second < y.second;
    return x.first < y.first;
}
int getType(vector< pair<int, int> > cards) {
    vector< pair<int, int> >::iterator it;
    
    sort(cards.begin(), cards.end(), suitCmp);
    if(cards[0].first == cards[4].first) { // all same suit
        for(int i = 0; i < 13; i++) {
            int ok = 1;
            for(int j = 0; j < 5; j++) {
                int r = (i + j)%13 + 1;
                it = find(cards.begin(), cards.end(), make_pair(cards[0].first, r));
                ok &= it != cards.end();
            }
            if(ok)
                return 9;
        }
    }
    
    sort(cards.begin(), cards.end(), rankCmp);
    if(cards[0].second == cards[3].second ||
        cards[1].second == cards[4].second)
            return 8;
            
    sort(cards.begin(), cards.end(), rankCmp);
    if(cards[0].second == cards[2].second &&
        cards[3].second == cards[4].second)
            return 7;
    if(cards[0].second == cards[1].second &&
        cards[2].second == cards[4].second)
            return 7;
            
    sort(cards.begin(), cards.end(), suitCmp);
    if(cards[0].first == cards[4].first)
        return 6;
        
    sort(cards.begin(), cards.end(), suitCmp);
    for(int i = 0; i < 13; i++) {
        int ok = 1;
        for(int j = 0; j < 5; j++) {
            int r = (i + j)%13 + 1;
            for(int k = 0; k < 4; k++) {
                it = find(cards.begin(), cards.end(), make_pair(k, r));
                if(it != cards.end())
                    break;
            }
            ok &= it != cards.end();
        }
        if(ok)
            return 5;
    }
    
    sort(cards.begin(), cards.end(), rankCmp);
    if(cards[0].second == cards[2].second ||
        cards[1].second == cards[3].second ||
         cards[2].second == cards[4].second)
            return 4;
    
    sort(cards.begin(), cards.end(), rankCmp);
    if(cards[0].second == cards[1].second &&
        cards[2].second == cards[3].second)
            return 3;
    if(cards[0].second == cards[1].second &&
        cards[3].second == cards[4].second)
            return 3;
    if(cards[1].second == cards[2].second &&
        cards[3].second == cards[4].second)
            return 3;
            
    sort(cards.begin(), cards.end(), rankCmp);
    for(int i = 1; i < 5; i++)
        if(cards[i].second == cards[i-1].second)
            return 2;
    return 1;
}
int main() {
    int testcase;
    char grid[5][5][5];
    scanf("%d", &testcase);
    while(testcase--) {
        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                scanf("%s", grid[i][j]);
        int cnt[10] = {};
        for(int i = 0; i < 5; i++) {
            vector< pair<int, int> > cc;
            for(int j = 0; j < 5; j++)
                cc.push_back(make_pair(getSuit(grid[i][j][1]), getRank(grid[i][j][0])));
            int f = getType(cc);
            cnt[f]++;
        }
        
        for(int i = 0; i < 5; i++) {
            vector< pair<int, int> > cc;
            for(int j = 0; j < 5; j++)
                cc.push_back(make_pair(getSuit(grid[j][i][1]), getRank(grid[j][i][0])));
            int f = getType(cc);
            cnt[f]++;
        }
        
        for(int i = 1; i <= 9; i++) {
            if(i > 1)	printf(", ");
            printf("%d", cnt[i]);
        }
        puts("");
        if(testcase)
            puts("");
    }
    return 0;
}
/*
2
AS 2S 3S 4S 5S
AC 2H 3H 5C 4C
AH 2D KC KH 5D
AD 3D KD 9D 8D
XH 3C XC XS 8C
AS 2S 3S 4S 6S
AC 2H 3H 5C 4C
AH 2D KC KH 5D
AD 3D KD 9D 8D
XH 3C XC XS 8C
*/