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$

最後得到

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

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
*/

Problem

You are given an integer sequence of length N and another value X. You have to find a contiguous subsequence of the given sequence such that the sum is greater or equal to
X. And you have to find that segment with minimal length.

Sample Input

1
2
3
4
5
6
7

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

Sample Output

1
2
3

3
-1
3

Solution

題目描述：

找一段長度最小，且該區間總和大於等於指定 X。

題目解法：

離散化後，利用掃描線的思路進行維護。

利用前綴和 SUM[i]，查找小於等於 SUM[i] - X 的最大值。

隨後更新 SUM[i] 位置的值 i。

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

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
#define MAXN 5024288
#define INF 0x3f3f3f3f
long long A[MAXN], SM[MAXN], SB[MAXN];
// binary index tree
int BIT[MAXN<<1];
void modify(int x, int v, int L) {
	while(x <= L) {
		BIT[x] = max(BIT[x], v);
		x += x&(-x);
	}
}
int query(int x) {
	int ret = - INF;
	while(x) {
		ret = max(ret, BIT[x]);
		x -= x&(-x);
	}
	return ret;
}
int main() {
	int testcase, N, X;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d", &N, &X);
		for(int i = 1; i <= N; i++)
			scanf("%lld", A+i);
		
		for(int i = 1; i <= N; i++)
			SM[i] = SM[i-1] + A[i];
		for(int i = 0; i <= N; i++)
			SB[i] = SM[i];
		for(int i = 1; i <= N + 1; i++)
			BIT[i] = - INF;
		sort(SB, SB + N + 1);
		int M = unique(SB, SB + N + 1) - SB;		
		int ret = INF;
		for(int i = 0; i <= N; i++) {
			long long v = SM[i] - X;
			int pos = upper_bound(SB, SB + M, v) - SB;
			if(pos - 1 >= 0 && i)  {
				ret = min(ret, i - query(pos));
//				printf("query %d\n", i - query(pos));
			}
			pos = upper_bound(SB, SB + M, SM[i]) - SB;
			modify(pos, i, M);
//			printf("%lld %d\n", v, pos);
		}
		
		printf("%d\n", ret == INF ? -1 : ret);
	}
	return 0;
}
/*
3
5 4
1 2 1 2 1
6 -2
-5 -6 -7 -8 -9 -10
5 3
-1 1 1 1 -1
*/

Problem

The Swamp County Environmental Office is concerned about the number of structures in the county. They have a theory that all the rain water landing on roofs of buildings, parking lots, roads, and highways is going down the sewage system instead of draining to the ecologically sensitive and historically important swamp land the county is famous for.

Your team has been hired to do the analysis of rain water captured by building roofs. The Planning Commission, which processes all building permits, and hence knows the plans of every structure in the county, will provide the data. Their database contains a set of measurements for the roofs of every building on every lot in the county.

The Engineering staff of the Planning Commission has determined that all the roofs in the county can be represented by one or more quadrilaterals. Each quadrilateral has the following characteristics:

length of baseline, in feet;
length of ridgeline, in feet;
distance between baseline and ridgeline, in feet;
and inclination of the roof segment, in degrees. 

The baseline is always parallel to the ridgeline. A roof segment is always flat, but may be inclined. The inclination of the segment occurs along the baseline or ridgeline axis. A roof segment that is inclined 90 degrees is a wall that is assumed to have negligible thickness, and hence gathers no rain—such a segment will not appear in the data. Assume that the buildings are on level land, and that no roof segment overlaps any other. A roof segment may have either a baseline or ridgeline length of zero (such a segment is actually a triangle). A lot may contain one or more buildings, but your program need only compute the area covered by roofs on a lot-by-lot basis.

Input

Each lot is represented by a series of numbers separated from each other by white space and/or new-lines. The lot size, in square feet, is followed by a list of roof segments. Each roof segment will consist of the length of the baseline, the length of the ridgeline, the distance between the baseline and the ridgeline, and the inclination. Each lot description including the last will end with a blank line.

Output

For each lot compute and print the following statistics: the total roof surface area of buildings in square feet, the total floor space covered by roofs in square feet, and the percentage of rain intercepted by roofs. Print these values in labeled columns, one lot per line, with two digits after the decimal point. Print percent signs after the percentage of rain figures.

At the end of the run compute and print the following statistics: the total roof surface area of all roofs in the county, the total floor space covered by roofs in the county, the overall percentage of rain intercepted by roofs, the average roof surface area on a lot, and the average floor space covered by roofs on a lot. Skip a line after the per-lot listing and print these values on separate lines with appropriate labels.

Print each value with two digits after the decimal point. Print a percent sign after the overall percentage of rain value. Use a report format similar to that of the sample output below.

One of the reasons Swamp County has remained so is the relative lack of wind in the county—you may therefore assume that all rain falls vertically.

Sample Input

1
2
3
4

100 10 10 10 60
10 10 10 60
200 5 10.5 5 30  10 10 7.5 45

Sample Output

1
2
3
4
5
6
7
8
9
10

Roof Area     Floor Area     % Covered
---------     ----------     ---------
   200.00         100.00       100.00%
   113.75          86.59        43.30%
 
Total surface area of roofs      313.75
Total area covered by roofs      186.59
Percentage of total area covered by roofs   62.20%
Average roof surface area per lot          156.88
Average floor space covered per lot         93.30

Solution

題目描述：

屋頂為一個三維空間的平面，假想成梯形也可以，頃角就是單純地將梯形與平面 x-y 夾角 theta。

分別算出梯形面積和陰影面積。

題目解法：

最坑的就是輸入，其實看了很久都沒有明白到底是怎麼區隔每一組。
查閱了討論區給的測資才湊出 AC 代碼。

想辦法讀到每一組測資是 4n + 1 個數字，否則繼續將空白行讀入。

brianfry713’s Input:

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

100 10 10 10 60
10 10 10 60
200 5 10.5 5 30  10 10 7.5 45
100
10 10 10
60 10
10 10 60
200 5 10.5 5 30  10 10 7.5 45
100 0 10 7.5 45 10
0 7.5 -135
300

brianfry713’s Output:

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

Roof Area     Floor Area     % Covered
---------     ----------     ---------
   200.00         100.00       100.00%
   113.75          86.59        43.30%
     0.00           0.00         0.00%
   600.00         590.88      5908.85%
  7701.25        7133.96     71339.57%
     0.00           0.00         0.00%
Total surface area of roofs     8615.00
Total area covered by roofs     7911.43
Percentage of total area covered by roofs 1098.81%
Average roof surface area per lot         1435.83
Average floor space covered per lot       1318.57

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 <sstream>
#include <iostream>
#include <math.h>
using namespace std;
const double pi = acos(-1);
double A, B, C, N;
char* getLot() {
	char line[1024], *v;
	string ret = "", token;
	int tokenCnt = 0;
	while(tokenCnt%4 != 1) {
		while((v = gets(line)) && line[0] != '\0') {
			ret += " ", ret += line;
			stringstream ss(line);
			while(ss >> token)
				tokenCnt++;
		}
		if(!v)
			return v;
	}
	stringstream sin(ret);
	double lotsize, baseline, ridgeline, dist, theta;
	double a = 0, b = 0;
	sin >> lotsize;
	while(sin >> baseline >> ridgeline >> dist >> theta) {
		a += (baseline + ridgeline) * dist/2.0;
		b += (baseline + ridgeline) * dist/2.0 * cos(theta / 180.0 * pi);	
	}
	printf("%9.2lf     %10.2lf     %8.2lf%%\n", a, b, b * 100 /lotsize);
	A += a, B += b, C += lotsize, N++;
	return v;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
	
	puts("Roof Area     Floor Area     % Covered");
	puts("---------     ----------     ---------");
	char line[1024];
	while(true) {
		if(getLot()) {
		} else {
			break;
		}
	}
	puts("");
	printf("Total surface area of roofs  %10.2lf\n", A);
	printf("Total area covered by roofs  %10.2lf\n", B);
	printf("Percentage of total area covered by roofs  %6.2lf%%\n", B*100/C);
	printf("Average roof surface area per lot      %10.2lf\n", A/N);
	printf("Average floor space covered per lot    %10.2lf\n", B/N);
	return 0;
}

Problem

The word the is the most common three-letter word. It even shows up inside other words, such as “other” and “mathematics”. Sometimes it hides, split between two words, such as “not here”. Have you ever wondered what the most common words of lengths other than three are?

Your task is the following. You will be given a text. In this text, find the most common word of length one. If there are multiple such words, any one will do. Then count how many times this most common word appears in the text. If it appears more than once, output how many times it appears. Then repeat the process with words of length 2, 3, and so on, until you reach such a length that there is no longer any repeated word of that length in the text.

Input Specification

The input consists of a sequence of lines. The last line of input is empty and should not be processed. Each line of input other than the last contains at least one but no more than one thousand uppercase letters and spaces. The spaces are irrelevant and should be ignored.

Sample Input

1
2

THE OTHER MATHEMATICS NOT HERE
AA

Note that the last line of the sample input is a blank line.

Output Specification

For each line of input, output a sequence of lines, giving the number of repetitions of words of length 1, 2, 3, and so on. When you reach a length such that there are no repeated words of that length, output one blank line, do not output anything further for that input line, and move on to the next line of input.

Output for Sample Input

1
2
3
4
5
6
7

5
4
4
2
2
2

Solution

題目描述：

依序將長度為 1, 2, 3, 4 … 其重複出現次數最高的字串次數輸出，只考慮重複次數大於 1 的所有情況。

題目解法：

由於題目只查看大寫字母，忽略空白不計，若存在有空白的行時特別處理，否則在隨後的 trim() 會有輸出錯誤。

直接套上 Suffix Array，使用 Double algorithm 建造法，並且建出高度數組。

建造在 O(n log n)，但是輸出處理最慘會到 O(n^2)。

在其他的做法中，可以看到有人使用 hash function 進行比較 (將每一組單詞丟到同一個欄中，之後在進行比較)，這也是個挺不錯的做法，但是風險還是存在。

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 <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct SuffixArray {
    int sa[1005], h[1005], n;
    int w[1005], ta[1005], tb[1005];
    char str[1005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
int main() {
    SuffixArray in;
    while(gets(in.str) && in.str[0] != '\0') {
    	int n = 0;
    	for(int i = 0; in.str[i]; i++)
    		if(in.str[i] != ' ')
    			in.str[n++] = in.str[i];
    	in.str[n] = '\0';
    	
        in.build();
        in.build_h();
        
        if(n == 0)
        	puts("0");
        for(int i = 1; i <= in.n; i++) {
        	int cnt = 0, ret = 0;
        	for(int j = 0; j < in.n; j++) {
        		if(in.h[j] >= i)
        			cnt++;
        		else
        			ret = max(ret, cnt), cnt = 0;
        	}
        	ret = max(ret, cnt);
        	if(ret <= 0)
        		break;
        	printf("%d\n", ret + 1);
        }
        puts("");
    }
    return 0;
}