Problem

At least it’s not a sudoku problem

The puzzle Nurikabe is played on a grid. Initially, each grid space is either blank or contains a single number. The goal is to shade in some of the blank spaces to satisfy the following constraints:

• Any two shaded spaces are connected by some sequence of adjacent shaded spaces. Two spaces are called adjacent if they share a side.
• For each of the unshaded spaces b, let Wb be the collection of all unshaded spaces that can be reached from b by a sequence of adjacent unshaded spaces. Then, Wb contains exactly one numbered space and that number is exactly the number of spaces in Wb.
• For any unshaded space b, there is a sequence of unshaded spaces starting at b and ending at a space on the edge of the grid where consecutive spaces in this sequence share a side or a corner.
• Finally, in every 2 x 2 subsquare there is at least one unshaded space.

The image shows an example of a Nurikabe puzzle and its solution. Take care to verify all four constraints are satisfied in the solution. To help you understand the third constraint, note that the middle cell containing the number 1 can reach the edge of the grid since it shares a corner with a group of unshaded spaces containing the number 2.

It is known that the problem of determining if a Nurikabe grid can be shaded to satisfy the constraints is NP-complete. Your task is much easier. Given an initial grid and a proposed shading, determine if the shading satisfies the constraints of the Nurikabe puzzle.

Input begins with a single integer t that indicates the number of grids to verify. The first line of each case contains three integers r,c,d where the grid has r rows and c columns (1 ≤ r,c ≤ 100). Then, d lines follow, each containing three integers r’,c’,n meaning the grid cell at location (r’,c’) contains the positive number n. The upper-left grid space has coordinates (0,0), no space receives more than one number, and no two numbered grid spaces will share an edge. Finally, the shading data is specified by r strings of c characters each (one string per line). The j’th character in the i’th row of the shading data is ‘#’ if the cell with coordinates (i,j) is shaded and ‘.’ if that cell is not shaded. Each test case is preceded by a blank line.

For each input case, output a line containing either solved or not solved to indicate whether or not the shading represents a solution to the puzzle.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

5
5 5 6
0 0 3
0 2 1
0 4 2
2 2 1
3 4 2
4 0 2
.#.#.
.###.
.#.##
###..
..###
5 5 6
0 0 3
0 2 1
0 4 2
2 2 1
3 4 3
4 0 2
.#.#.
.###.
.#.##
####.
..#..
2 3 1
0 0 2
.##
.##
2 2 1
0 0 1
..
##
2 2 2
0 0 1
1 1 1
.#
#.

Sample output

1
2
3
4
5

solved
not solved
not solved
not solved
not solved

Solution

題目描述：

• 所有陰影區域會相連 (上下左右)
• 每一個區域的數字，會恰好等於該區域的非陰影個數。
• 所有非陰影的區域，皆可以連到遊戲盤面的四邊 (九宮格連接)
• 任意 2x2 區域，至少有一個非陰影的區域。

題目解法：

能剪枝就剪枝，不然很容易 TLE。討論版面上說 DFS 比 BFS 快一些。但這裡還是用 BFS 完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int g[205][205], ug[205][205];
char pattern[205][205];
int cond1(int x, int y, int r, int c, int cellcnt) {
/* 
 Any two shaded spaces are connected by some sequence 
 of adjacent shaded spaces. Two spaces are called 
 adjacent if they share a side. 
*/
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    queue<int> X, Y;
    int i, tx, ty;
    char used[205][205] = {};
    X.push(x), Y.push(y);
    used[x][y] = 1;
    cellcnt--;
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        for(i = 0; i < 4; i++) {
            tx = x+dx[i], ty = y+dy[i];
            if(tx < 0 || ty < 0 || tx >= r || ty >= c)
                continue;
            if(used[tx][ty] == 0 && pattern[tx][ty] == '#') {
                used[tx][ty] = 1;
                cellcnt--;
                if(cellcnt < 0)	return 0;
                X.push(tx), Y.push(ty);
            }
        }
    }
    return cellcnt == 0;
}
int cond2(int x, int y, int r, int c) {
/*
 For each of the unshaded spaces b, let Wb be the 
 collection of all unshaded spaces that can be 
 reached from b by a sequence of adjacent unshaded 
 spaces. Then, Wb contains exactly one numbered 
 space and that number is exactly the number of 
 spaces in Wb. 
*/
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    queue<int> X, Y;
    int Wb = g[x][y], i, tx, ty;
    char used[205][205] = {};
    if(pattern[x][y] == '.') {
        X.push(x), Y.push(y);
        used[x][y] = 1;
    } else
        return 0;
    Wb--;
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        for(i = 0; i < 4; i++) {
            tx = x+dx[i], ty = y+dy[i];
            if(tx < 0 || ty < 0 || tx >= r || ty >= c)
                continue;
            if(used[tx][ty] == 0 && pattern[tx][ty] == '.') {
                // if(ug[tx][ty]) return 0; // other Wb
                used[tx][ty] = 1;
                Wb--;
                if(Wb < 0) return 0;
                X.push(tx), Y.push(ty);
            }
        }
    }
    return Wb == 0;
}
int cond3(int x, int y, int r, int c) {
/*
  For any unshaded space b, there is a sequence 
  of unshaded spaces starting at b and ending 
  at a space on the edge of the grid where 
  consecutive spaces in this sequence share a 
  side or a corner. 
*/
    int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
    int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
    queue<int> X, Y;
    int i, tx, ty;
    char used[205][205] = {};
    if(pattern[x][y] != '.')
        return 1;
    X.push(x), Y.push(y);
    used[x][y] = 1;
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        if(x == 0 || x == r-1 || y == 0 || y == c-1)
            return 1;
        for(i = 0; i < 8; i++) {
            tx = x+dx[i], ty = y+dy[i];
            if(tx < 0 || ty < 0 || tx >= r || ty >= c)
                continue;
            if(used[tx][ty] == 0 && pattern[tx][ty] == '.') {
                used[tx][ty] = 1;
                X.push(tx), Y.push(ty);
            }
        }
    }
    return 0;
}
int cond4(int r, int c) {
    int i, j;
    for(i = 0; i < r-1; i++) {
        for(j = 0; j < c-1; j++) {
            bool flag = (pattern[i][j] == '.' || pattern[i][j+1] == '.' ||
                         pattern[i+1][j] == '.' || pattern[i+1][j+1] == '.');
            if(flag == false)
                return 0;
        }
    }
    return 1;
}
int main() {
	// freopen("in.txt", "r+t", stdin);
	// freopen("out.txt", "w+t", stdout); 
    int testcase;
    int r, c, n;
    int x, y, v, i, j, k;
    scanf("%d", &testcase);
    while(testcase--) {
        if(scanf("%d %d %d", &r, &c, &n) != 3)
            return 0;
        memset(g, 0, sizeof(g));
        memset(ug, 0, sizeof(ug));
        int tot = 0;
        int ret = 1;
        for(i = 0; i < n; i++) {
            scanf("%d %d %d", &x, &y, &v);
            g[x][y] = v;
            ug[x][y] = 1;
            tot += v;
        }
        for(i = 0; i < r; i++)
            scanf("%s", &pattern[i]);
        int cellcnt = 0;
        int unshaded = 0;
        for(i = 0; i < r; i++)
            for(j = 0; j < c; j++)
                if(pattern[i][j] == '#')
                    cellcnt++, x = i, y = j;
                else
                    unshaded++;
        if(tot != unshaded) {
            puts("not solved");
            continue;
        }
        if(cellcnt && !cond1(x, y, r, c, cellcnt)) {
            puts("not solved");
            continue;
        }
        for(i = 0; i < r && ret; i++) {
            for(j = 0; j < c && ret; j++) {
                if(ug[i][j]) {
                    ret &= cond2(i, j, r, c);
                }
            }
        }
        if(!ret) {
            puts("not solved");
            continue;
        }
        for(i = 0; i < r && ret; i++) {
            for(j = 0; j < c && ret; j++) {
                if(ug[i][j]) {
                    ret &= cond3(i, j, r, c);
                }
            }
        }
        if(!ret) {
            puts("not solved");
            continue;
        }
        ret &= cond4(r, c);
        if(!ret) {
            puts("not solved");
            continue;
        }
        puts("solved");
    }
    return 0;
}

展示

A hexo plugin that uses MathJax to render math equations.
Simple inline $a = b + c$.

1

Simple inline $a = b + c$.

This equation $\cos 2\theta = \cos^2 \theta - \sin^2 \theta = 2 \cos^2 \theta - 1$ is inline.

1

This equation <hexoescape>1</hexoescape> is inline.

$$\begin{aligned} \dot{x} & = \sigma(y-x) \\ \dot{y} & = \rho x - y - xz \\ \dot{z} & = -\beta z + xy \end{aligned}$$

更多

http://catx.me/2014/03/09/hexo-mathjax-plugin/

Problem

Some time ago, Dejan Stojanovic, a Serbian poet, said: “Words rich in meaning can be cheap in sound
effects.” Is it true? A String Processing professor at UFPE wants to test this quote with strings. For that, he defined what he calls a “cheap B-subsequence”. A cheap B-subsequence, according to his definition, is a subsequence of size B, of a string S(B <= |S|), that has the lowest associated cost. To define the cost of a string, the professor determined a series of rules to each letter of the alphabet. The alphabet that he used contains only lowercase letters. The rule of a letter is defined as a set of pairs (P_i, C_i), which indicates that if this letter appears in a position X on the subsequence, where X is a multiple of P_i, then the cost of (X/P_i) * C_i will be added to the total cost of this subsequence. Let’s show an example. Suppose we have the following rules:

1
2
3
4

[a] = {(2, 3), (4, 10)}
[b] = {(1, 4), (7, 50)}
[c] = {(1, 2), (4, 20)}
[d..z] = { } // there are no rules for the characters `d` to `z`

Suppose we have the string abaabcbc, and B = 4. If we choose the subsequence aabc (abaabcbc), we would do the following procedure to calculate the associated cost:

1. The first letter of the sequence is an a, and the position 1 is neither multiple of 2 or 4, so the cost is 0;

2. The second letter of the sequence is another a, and the position 2 is a multiple of 2, so we’ll add the cost of (2/2) * 3 = 3;

3. The third letter of the sequence is a b, and the position 3 is multiple of 1, so we will add the cost of (3/1) * 4 = 12;
4. The last letter of the sequence is a c, and the position 4 is a multiple of 1 and 4, so we will add
   the cost of (4/1) * 2 + (4/4)* 20 = 28.

The total associated cost to this subsequence is 43, which is not the lowest cost, since we could have chosen aaab (abaabcbc) and obtained an associated cost of 19 | this is indeed the cost of the cheap B-subsequence. Given the string S and the integer B, and the rules of the alphabet, your task is to create a program that tells the professor the cost of the cheap B-subsequence.

Input

The first line contains T (T < 100)－　the number of test cases, after this line T test cases follows. The first line of a test case contains a string S of lowercase letters and an integer B
(1 <= B <= |S| <= 100). Each of the next 26 lines describe the rule of each letter. The first of the 26 lines corresponds to the rule of the letter a; the following line corresponds to the rule of the letter b; the last of the 26 lines corresponds to the rule of the letter z. Each line containing a rule is described in the following way:

Q, P1, C1, P2, C2, … PQ, CQ

(1 <= Q <= 10; 1 <= Pi <= |S|; 1 <= Ci <= 50), where Q is the amount of pairs associated to this rule, and is followed by the pairs themselves.

Output

For each test case print a line containing Case #X: Y, where X is the case number, starting at 1, and Y is the cost of the cheap B-subsequence.

Sample Input

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

2
abcd 1
1 1 20
1 1 15
1 1 8
1 1 30
1 1 2
0 (21 lines)
abaabcbc 4
2 2 3 4 10
2 1 4 7 50
2 1 2 4 20
0 (23 lines)

Sample Output

1
2

Case #1: 8
Case #2: 19

Solution

題目描述：

找一個長度為 B 的 subsequence，並且每一個字符成本如題目所定義，求最小構成成本。

題目解法：

動態規劃，狀態 dp[length][subsequence_index]

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

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int dp[128][128], cost[26][128];
int main() {
	int testcase, cases = 0;
	char S[128];
	int B, P, C, N, M;
	scanf("%d", &testcase);
	while(testcase--) {		
		scanf("%s %d", S+1, &B);
		
		N = strlen(S+1);
		memset(dp, 0x3f, sizeof(dp));
		memset(cost, 0, sizeof(cost));
		
		for(int i = 0; i < 26; i++) {
			scanf("%d", &M);
			for(int j = 0; j < M; j++) {
				scanf("%d %d", &P, &C);
				int oP = P;
				while(oP <= N)
					cost[i][oP] += oP / P * C, oP += P;
			}
		}		
		dp[0][0] = 0;
		for(int i = 0; i < B; i++) {
			for(int j = 0; j <= N; j++) {
				for(int k = j + 1; k <= N; k++) {
					int c = cost[S[k] - 'a'][i + 1];
					dp[i+1][k] = min(dp[i+1][k], dp[i][j] + c);
				}
			}
		}
		int ret = 0x3f3f3f3f;
		for(int i = 1; i <= N; i++)
			ret = min(ret, dp[B][i]);
		printf("Case #%d: %d\n", ++cases, ret);
	}
	return 0;
}
/*
2
abcd 1
1 1 20
1 1 15
1 1 8
1 1 30
1 1 2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
abaabcbc 4
2 2 3 4 10
2 1 4 7 50
2 1 2 4 20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
*/

Problem

There are 52 playing cards in a pack, divided into suits, and, within suits, into denominations. The suits are (in order, lowest to highest) Clubs, Diamonds, Hearts and Spades, abbreviated C, D, H and S. The 13 denominations (or face values) are (from lowest to highest): 2, 3, 4, 5, 6, 7, 8, 9, 10 (T), Jack (J), Queen (Q), King (K) and Ace(A). A higher card will beat a lower card in the same suit, but will not usually beat any other card in a different suit. An exception to this is the trump suit—if a suit is designated to be a trump suit (by whatever means the rules of the game allow), then any card of that suit will beat any card of any other suit.

撲克共有 52 張牌，總共有 4 種花色 (C < D < H < S, 梅花 < 方塊 < 紅心 < 黑桃)，每 1 種花色有 13 張牌，由小到大的點數分別是 2, 3, 4, 5, 6, 7, 8, 9, 10 (T), Jack (J), Queen (Q), King (K) and Ace(A)，點數大的可以勝過點數小的。在遊戲中可以選定 王牌 的花色，王牌可以贏過任一其他花色的牌。

A simplified version of an old card game called Hearts is played as follows. The dealer deals cards clockwise, one by one, face downward, to four other players and himself, starting with the player on his left, who thus gets the first card, followed by the sixth, and so on, while the dealer gets the fifth card, followed by the tenth, and so on. When each player has 10 cards there will be two left—these are exposed and the suit of the one of higher denomination determines the trump suit. If there is a tie, then the highest ranking suit becomes the trump suit.

Hearts 是一款早期的簡化版卡牌遊戲，總共有 5 名玩家，發牌者將會順時針從自己的左手邊第一個玩家依序發給每一個玩家，因此發牌者自己將會拿到第 5 張、第 10 張、 … 等。最後，每名玩家將會有 10 張牌，剩下的兩張牌點數高的那張牌的花色將是王牌花色，如果點數相同，則原本由原本花色大的被選為王牌花色。

A game consists of 10 tricks, each containing 5 cards, one from each player. For each trick, one player leads, i.e. plays a card face up on the table, the rest of the players then `follow’, in clockwise order. The player to the dealer’s left leads to the first trick, thereafter the winner of each trick leads to the next trick. A player must follow suit if possible, i.e. play a card of the same suit as the one lead. If he cannot, then he must trump it (play a card of the designated trump suit). If he cannot trump it (because he has no cards in the trump suit), he discards a card. If a trick is trumped, then the person playing the highest trump wins the trick, otherwise the person playing the highest card of the correct suit wins it.

這場遊戲共計 10 輪，每一輪每名玩家各出 1 張牌，因此共計 5 張。在每一輪中，將會有一名玩家擔任 首發，首發將決定這一輪的花色，而剩餘的玩家按照順時針順序出牌。在這一輪中，獲勝者將成為下一輪的首發，並且將可以得到這一輪所有紅心的分數。每名玩家必須盡可能出這一輪所需要的花色，如果沒有所需花色，打出王牌將可以勝過其他非王牌的出牌，如果有數名玩家接打出王牌，則出點數較高王牌的玩家獲勝。

Strategies are as follows:

• Leader: The leader always plays the highest card in his hand. If there is a tie and one of the cards is a trump card, then he leads the trump, otherwise he plays the highest ranking suit.
• Follower: If possible he must play the highest card in his hand of the correct suit. If he has no cards in that suit then he plays the highest trump he has. If he cannot trump it he plays the highest card in his hand, breaking ties as previously specified.

策略如下所述：

• 首發：將會從發中挑一個最高點數的牌，如果點數相同，則會先挑王牌花色的那一張，如果沒有王牌花色，則出花色排名最高的那一張。
• 跟隨者：將打出該輪所需花色的最高點數牌。如果沒有所需花色，將會打出手上點數最高的王牌，如果還是沒有王牌，則將打出最高點數的牌，若點數相同將打出最高花色的那張。

When all the tricks have been played, each player examines the tricks he has taken and scores the face value of any Heart he has (Jack counts 11, Queen counts 12, King counts 13 and Ace counts 14). This score is recorded.

在每一輪，獲勝者將會拿到該輪出牌 5 張中紅心的點數，並且加入到自己的得分中。

Write a program to simulate the playing of this game.

Input

Input will consist of a series of decks of cards, each deck spread over four lines as shown below. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each deck in the input. Each line will consist of 5 numbers reflecting the scores of the individual players, starting with the dealer and proceeding clockwise through the rest of the players. Each score will consist of a number right justified in a field of width 3.

Sample input

1
2
3
4
5

TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C
#

Sample output

1

22  0 68  0 14

Solution

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

#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int suitW(char c) {
	switch(c) {
		case 'C':return 0;
		case 'D':return 1;
		case 'H':return 2;
		case 'S':return 3;
	}
}
int cardW(char c) {
	switch(c) {
		case '2'...'9':return c - '0';
		case 'T':return 10;
		case 'J':return 11;
		case 'Q':return 12;
		case 'K':return 13;
		case 'A':return 14;
	}
}
char decideTrump(const char c1[], const char c2[]) {
	if(cardW(c1[0]) != cardW(c2[0]))
		return cardW(c1[0]) > cardW(c2[0]) ? c1[1] : c2[1];
	return suitW(c1[1]) > suitW(c2[1]) ? c1[1] : c2[1];
}
int leaderCmp(string c1, string c2) {
	if(cardW(c1[0]) != cardW(c2[0]))
		return cardW(c1[0]) > cardW(c2[0]);
	return suitW(c1[1]) > suitW(c2[1]);
}
string leaderPlay(vector<string> &hand, char trump) {
	sort(hand.begin(), hand.end(), leaderCmp);
	int h = hand[0][0];
	for(vector<string>::iterator it = hand.begin(); 
		it != hand.end(); it++) {
		if((*it)[1] == trump && (*it)[0] == h) {
			string ret = *it;
			hand.erase(it);
			return ret;
		}
	}
	string ret = hand[0];
	hand.erase(hand.begin());
	return ret;
}
string followerPlay(vector<string> &hand, char suit, char trump) {
	sort(hand.begin(), hand.end(), leaderCmp);
	for(vector<string>::iterator it = hand.begin(); 
		it != hand.end(); it++) {
		if((*it)[1] == suit) {
			string ret = *it;
			hand.erase(it);
			return ret;
		}
	}
	for(vector<string>::iterator it = hand.begin(); 
		it != hand.end(); it++) {
		if((*it)[1] == trump) {
			string ret = *it;
			hand.erase(it);
			return ret;
		}
	}
	string ret = hand[0];
	hand.erase(hand.begin());
	return ret;
}
int main() {
	char deckCard[52][128];
	const int tricks = 10;
	do {
		for(int i = 0; i < 52; i++) {
			scanf("%s", deckCard[i]);
			if(!strcmp(deckCard[i], "#"))
				return 0;
		}
		vector<string> hand[5];
		for(int i = 0, j = 0; i < 50; i++, j = (j+1)%5) {
			hand[j].push_back(deckCard[i]);
		}
		
		char trump = decideTrump(deckCard[50], deckCard[51]);
		int leader = 0;
		int scores[5] = {};
		
		for(int i = 0; i < tricks; i++) {
			vector< pair<string, int> > desk;
			desk.push_back(make_pair(leaderPlay(hand[leader], trump), leader));
			char suit = desk[0].first[1];
			for(int j = (leader + 1)%5, k = 0; k < 4; j = (j+1)%5, k++) {
				desk.push_back(make_pair(followerPlay(hand[j], suit, trump), j));
			}
			int maxCardW = -1;
			for(int j = 0; j < desk.size(); j++) {
				// printf("PLAYER %d play %s\n", desk[j].second + 1, desk[j].first.c_str());
				if(desk[j].first[1] == trump && suit != trump) {
					suit = trump;
					maxCardW = cardW(desk[j].first[0]);
					leader = desk[j].second;
				}
				if(suit == desk[j].first[1] && cardW(desk[j].first[0]) > maxCardW) {
					maxCardW = cardW(desk[j].first[0]);
					leader = desk[j].second;
				}
			}
			/*
			printf("PLAYER %d is the winner\n", leader + 1);
			for(int j = 0; j < 5; j++) {
				for(int k = 0; k < hand[j].size(); k++)
					printf(" %2d%c ", cardW(hand[j][k][0]), hand[j][k][1]);
				puts("");
			}*/
			for(int j = 0; j < desk.size(); j++) {
				if(desk[j].first[1] == 'H') {
					// printf("GET %d\n", cardW(desk[j].first[0]));
					scores[leader] += cardW(desk[j].first[0]);
				}
			}
		}
		printf("%3d", scores[4]);
		for(int i = 0; i < 4; i++)
			printf("%3d", scores[i]);
		puts("");
	} while(true);
	return 0;
}

Problem

The executive officers of the company where you work want to send each other encrypted messages. Rather than use off-the-shelf encryption software such as PGP, they have tasked the IT staff with handling the encryption problem. The IT staff decided on a solution that requires public and private integer keys. The idea is that everyone can see your public key, but only you know your private key.

Your best friend in the company is a wonderful person but a not-so-wonderful programmer. He has created a publicprivate key scheme as follows. A public key can be any positive integer. The corresponding private key is the smallest bipartite number that is greater than and a multiple of the public key.

A bipartite number is any positive integer that contains exactly 2 distinct decimal digits s and t such that s is not 0 and all occurrences of s precede all occurrences of t. For example 44444411 is bipartite (s is 4 and t is 1), So are 41, 10000000, and 5555556. However, neither 4444114 nor 44444 are bipartite.

Notice that the large bipartite number 88888888888800000 can be nicely described as 12 8’s followed by 5 0’s. You can express any bipartite number using four numbers: m s n t. The numbers s and t are the leading and trailing digits as described above, m is the number of times the digit s appears in the bipartite number, and n is the number of times the digit t appears.

The trouble with your friend’s scheme is that it is not too difficult to compute a private key if you know the public key. You need to convince your friend that his public-private key scheme is inadequate before he loses his job over his bad decision! You must write a program that takes public keys as input and displays the corresponding private keys.

Input

The input consists of several test cases. Each test case is on a separate line, and it consists of a single public key in the range 1…99999.

The last case is followed by a line containing the integer zero.

Output

For each test case, display a line consisting of the public key, a colon, then 4 integers m s n t where m, n, s, and t are as described above.

Sample Input

1
2
3
4

125 
17502 
2005 
0

Sample Output

1
2
3

125: 1 5 2 0 
17502: 4 7 4 8 
2005: 3 2 3 5

Claimer: The data used in this problem is unofficial data prepared by Derek Kisman. So any mistake here does not imply mistake in the offcial judge data. Only Derek Kisman is responsible for the mistakes. Report mistakes to dkisman@acm.org

Solution

題目描述：

現在找一個 public key，這個 public key 符合 format xxx...xyyy...y，其中 x, y 是 0-9 構成的。

而你的 private key N 是給定的，接著找一個符合規定的 public key，是 N 的倍數且最大於 N 的最小值。

題目解法：

題目給定的最大值 88888888888800000 沒有任何意義。可能會超過好幾位，連 long long 64 bits 都裝不下。

需要廣度搜索來完成，但是要找到 public key > N 會有點麻煩。

• 一開始嘗試在最大值下面建表查找，但卡了很多 WA，後來發現不合理的測資。
• 之後採用類似最短路徑的 BFS，藉由狀態 dist[MOD][2] 找到最小長度。但是這種作法不容易處理 > N 的判斷。
• 因此，採用一個迭代窮舉，窮舉最後的 public key 長度，然後找切割的位置分配給 x, y。

但是這樣做還是很容易 TLE，我們特別對 10 的倍數作調整，這些亂做不好說明。

更多 More
可以先把輸入讀進來，然後一次做完分析的離散處理，說不定會比較快。

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

// Accepted
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
struct ELE {
	int m, s, n, t;
	ELE(int a = 0, int b = 0, int c = 0, int d = 0):
		m(a), s(b), n(c), t(d) {}
	bool operator<(const ELE &x) const {
		if(m + n != x.m + x.n)
			return m + n < x.m + x.n;
		if(s != x.s)
			return s < x.s;
		if(m != x.m)
			return s < x.t;
		return t < x.t;
	}
};
#define MAXL 9999
int M1[MAXL];
int M10[MAXL];
int largeN(int N, ELE key) {
	if(key.m + key.n > 5) // > 100000
		return 1;
	int tmp = 0;
	for(int i = 0; i < key.m; i++)
		tmp = tmp * 10 + key.s;
	for(int i = 0; i < key.n; i++)
		tmp = tmp * 10 + key.t;
	return tmp > N;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout);   
	for(int N; scanf("%d", &N) == 1 && N; ) {
		
		M1[0] = 0;
		M10[0] = 1;
		for(int i = 1; i < MAXL; i++) {
			M1[i] = (M1[i-1] * 10 + 1)%N;
			M10[i] = (M10[i-1] * 10)%N;
		}
		
		ELE key(MAXL);
		for(int len = 2; len < MAXL; len++) {
			for(int i = N%10 || len <= 20 ? 1 : len - 20; i < len; i++) {
				for(int p = 1; p < 10; p++) {
					for(int q = 0; q < 10; q++) {
						if(p == q)
							continue;
						long long m = ((long long)M1[i] * M10[len - i] * p + M1[len - i] * q)%N;
						ELE tkey(i, p, len - i, q);
						if(m == 0 && largeN(N, tkey) && tkey < key) {
							key = tkey;
						}
					}
				}
			}
			if(key.m != MAXL)
				break;
		}
		printf("%d: %d %d %d %d\n", N, 
			key.m, key.s, key.n, key.t);
	}
	return 0;
}
/*
190
24822
344
4455
*/

我說，那邊的人全都是處男嗎？

以日記型式的文章已經快四個月沒寫過，這是第一在 Github Hexo 上。

圖文無關，無須多問。

開始

這學期遇到一個很重要的事件－專題，同時也是升研究所的最後一戰，聽說不少人會少修一點課讓學期成績變高，但是這些無關緊要，至少於我的價值觀中沒有什麼交集。在思考的是，應該要讓有能力的人讀研究所，而我這種叛逆小孩只會陡增教授麻煩。

不成熟者的特徵是願意為了理想而犧牲，而成熟者的特徵是願意為了理想而苟活。

為什麼說叛逆呢？因為專題不是所偏愛的項目，做專案雖然有趣，那是因為學習是有趣的，創造對我來說還遠呢。當然，在退出專題小組時，在此之前是發生了一些問題，冗長的設計會議、不斷切換的目標、充滿希望的箴言．．．等。

最後私下被教授約談，教授對我說「你既然有經驗，為什麼不提個意見？」「這不好說，因為這樣對他們不好，因為教授您曾說『有能力的人會帶著別人走，但是他們不見得會走對的路』那這樣豈不成了罪人」當然這是一個懦弱的答覆，但是在經驗不慎滿意的情況下，說自己有能力是太過頭。

另一方面來說，對於設計一個功能協助的網站 hw-reporter-website ，設計功能、需求，這些完全沒有想法，做事情不是有沒有能力的問題，而是在於有沒有接觸過。

後來決定獨自做點事情，就這樣跟教授這麼闡明了，於是

往後的幾個星期，不是在忙其他的課程報告、就是在碩班課作業中忙碌，如：計算型智慧課程中的演算法雖然不難，但實作相當有意思。又如：計算理論的手寫作業，雖然跟正規語言類似在 DFA, CFG, PDA, TM 裡面的理論能力打轉，作業一次就是手寫五到十面，這也是相當刺激的。

當然，這學期仍相當感謝 mozilla 讓我在生不如死的情況下學用 Github，他們帶我們大學專題生沒有薪水，但卻願意花時間培養，稍微回頭思考所學的項目，是多麼愚蠢至極。

說出來就沒有價值，也不過如此簡單。想到比做到還難，就是這麼一回事。

在退出後，每周開會並沒有特別想要去。也許就如另一個退出的同學所言「不想看到這麼多憧憬。」的確，根據軟體開發中其一的敏捷開發，相互學習、團隊合作、逐步推進。對於我這種邊緣人來說，又或者對思考偏頗的我們來說都太耀眼。即使明白是惰性造成的反饋，但仍無法因理想而學習。請直接對我們這種人下命令吧。

「你是 M 嗎？好吧，你是。」
「等等 Inker，別這麼快下定論。」

雖然進度很慢，但仍在慢慢在做網頁開發，以致 mozilla 前期給予我的培養。順道把一些糟糕作品都上傳到 Github，有空可以去看看，還真是糟到不行。對於網頁不這麼熱衷是有原因的，其一，如果不了解運行原理，一直用測試來得到想要結果不是辦法，那似乎必須先從瀏覽器開始學起，哎呀，這條路可是不歸路，人生有限、能力有限，何必自虐。其二，做了一陣子，發現問題是煩，而不是難，追求達人之路，網頁的廣泛技巧領域對於我這個正反器架構的人來說，塞不下！

其實倒不如說被放棄，說不定專題被當掉，再找其他教授搞一次專題？還是乾脆大學延畢呢？負面想像不斷湧出，下學期的黑歷史就這麼展開了！

黑歷史有三，其一，上台報告有三。其二，被這世界所記錄。其三，存在。

頓悟

常會把自己投影到故事中的主人翁，殊不知自己最常扮演的卻是不起眼的配角。

有興趣的人可到這裡去看一下 日本的大型書店：漫步書林（中日雙語字幕） ，如果無法改變別人，在這裡找到改變自己的想法。看到穿梭於書店的人們在尋找的事物，在看看外面暢遊的人們所追尋的道理，這個問題又再次蒙了陰影。

我們的人生不會相同，理解追尋的目標不同，而我就是那孤單的角落，沒有什麼轉接口。

「與其拿鏟子去挖看不見的金子的人，賣鏟子的人的確賺了錢。」

這世界就是如此地殘酷，看到學長們在意未來薪水有多少時，不經會思考「為什麼會認為自己有能力拿那些錢」這個問題也許毫無意義，單純跟個人價值有關。再看看 RD 部門(研究開發 research development) 「比起薪水，我們更在意自己的作品是否能上市」，有錢有名譽是人生雙收，但是苦過來、開創過來的都是一群傻子。

這學期歷經了硬碟壞掉、CPU 風扇壞掉、主機板淋水掛掉 … 等，那時人生還真是停頓相當長的時間，還真會有種衣食父母不見得感覺。

女朋友啊，別這麼離開我，妳我共同交織的記憶，在上千上萬行的行號中跳躍，我明白的事情全都交付於妳，求妳千萬別離開我。每當我逼不得已暫時離開妳，就如靈魂缺少了軀殼般地焦慮，四處找尋著唯一的妳。

是接近期末的時候，要決定要如何運行下學期，還有一些 final project 在等著，雖然已知學期成績會很難看，不過就是如此，悲劇才是人生精彩的地方。

但是 final project 還是要交出去。只要記得繳交，千萬別露出 …

最後

慶祝一下 UVa 2100 題，雖然不怎麼想寫，但是逃避現實的力量促使。

越來越寫不出精彩，人生。

Problem

Your new company is building a robot that can hold small lightweight objects. The robot will have the intelligence to determine if an object is light enough to hold. It does this by taking pictures of the object from the 6 cardinal directions, and then inferring an upper limit on the object’s weight based on those images. You must write a program to do that for the robot.

You can assume that each object is formed from an N×N×N lattice of cubes, some of which may be missing. Each 1×1×1 cube weighs 1 gram, and each cube is painted a single solid color. The object is not necessarily connected.

Input

The input for this problem consists of several test cases representing different objects. Every case begins with a line containing N, which is the size of the object ( 1 <= N <= 10). The next N lines are the different N×N views of the object, in the order front, left, back, right, top, bottom. Each view will be separated by a single space from the view that follows it. The bottom edge of the top view corresponds to the top edge of the front view. Similarly, the top edge of the bottom view corresponds to the bottom edge of the front view. In each view, colors are represented by single, unique capital letters, while a period (.) indicates that the object can be seen through at that location.

Input for the last test case is followed by a line consisting of the number 0.

Output

For each test case, print a line containing the maximum possible weight of the object, using the format shown below.

Sample Input

1
2
3
4
5
6
7
8

3
.R. YYR .Y. RYY .Y. .R.
GRB YGR BYG RBY GYB GRB
.R. YRR .Y. RRY .R. .Y.
2
ZZ ZZ ZZ ZZ ZZ ZZ
ZZ ZZ ZZ ZZ ZZ ZZ
0

Sample Output

1
2

Maximum weight: 11 gram(s)
Maximum weight: 8 gram(s)

Solution

題目描述：

現在有一些著色的立方體 1x1x1，每一個立方小塊會由一個顏色構成， 然後這些立方塊會疊在一起，最大為 N N N 。機器人在周圍拍照，將六個影像傳回來，請問現在最多可能有多少立方塊。

題目解法：

這題最麻煩的是座標假想。

現在眼前有一個立方體，而前方是 Y 軸正向，右手是 X 軸正向，上方是 Z 軸正向。

而對於每一個面來說，機器人相當於在 X-Y 平面上走動。拍攝的時候，X 軸是往下方正向，Y 軸是往右方正向。

接著，先把空洞挖掉。再者，把所有可能進行標記，接著嘗試把那一面貼上去，對於不符合顏色的立方塊拔掉，直到六個面都屬於符合的狀態 (迭代更新)。

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

#include <stdio.h> 
#include <string.h>
char cube[16][16][16];
// front, left, back, right, top, bottom
void getXYZ(int N, int kind, int x, int y, int d, int &rx, int &ry, int &rz) {
	switch(kind) {
		case 0:
			rx = y, ry = d, rz = N - x - 1;
			break;
		case 1:
			rx = d, ry = N - y - 1, rz = N - x - 1;
			break;
		case 2:
			rx = N - y - 1, ry = N - d - 1, rz = N - x - 1;
			break;
		case 3:
			rx = N - d - 1, ry = y, rz = N - x - 1;
			break;
		case 4:
			rx = y, ry = N - x - 1, rz = N - d - 1;
			break;
		case 5:
			rx = y, ry = x, rz = d;
			break;
	}
}
int main() {
	char views[6][16][16];
	for(int N; scanf("%d", &N) == 1 && N; )  {
		int x, y, z;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < 6; j++)
				scanf("%s", &views[j][i]);
		}
		
		memset(cube, '?', sizeof(cube));
		
		for(int k = 0; k < 6; k++) {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(views[k][i][j] != '.')
						continue;
					for(int d = 0; d < N; d++) {
						getXYZ(N, k, i, j, d, x, y, z);
						cube[x][y][z] = '.';
					}
				}
			}
		}
		bool update = false;
		do {
			update = false;
			for(int k = 0; k < 6; k++) {
				for(int i = 0; i < N; i++) {
					for(int j = 0; j < N; j++) {
						if(views[k][i][j] == '.')
							continue;
						for(int d = 0; d < N; d++) {
							getXYZ(N, k, i, j, d, x, y, z);
							if(cube[x][y][z] == '.')
								continue;
							if(cube[x][y][z] == '?') {
								cube[x][y][z] = views[k][i][j];
								update = true;
								break;
							} else if(cube[x][y][z] == views[k][i][j]) {
								break;	
							} else {
								cube[x][y][z] = '.';
								update = true;
							}
						}
					}
				}
			}
		} while(update == true);
		
		int ret = 0;
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				for(int k = 0; k < N; k++)
					ret += cube[i][j][k] != '.';
		printf("Maximum weight: %d gram(s)\n", ret);
	}
	return 0;
}
/*
front, left, back, right, top, bottom.
3
.R. YYR .Y. RYY .Y. .R.
GRB YGR BYG RBY GYB GRB
.R. YRR .Y. RRY .R. .Y.
2
ZZ ZZ ZZ ZZ ZZ ZZ
ZZ ZZ ZZ ZZ ZZ ZZ
0
*/

Problem

Suppose that a polygon is represented by a set of integer coordinates, {(x0, y0), (x1, y1), (x2, y2), …, (xn, yn), (x0, y0)}. Please find the convex hull of the polygon, where a convex hull is the minimum bounding convex polygon and “convex” means the angle between two consecutive edges is less than 180o.

Input file

Input consists of several datasets separated by a blank line. Each dataset contains a sequence of integer coordinates xi, yi, one in each line. All input sequence will contain at least 3 different points.

Output

The output for each dataset should contain a sequence of integer coordinates xi, yi specifying the convex hull, each in a line. The first coordinate of the output sequence must be the first coordinate in the input sequence that belongs to the convex hull. The output sequence must be in counter-cockwise order. Print a blank line between datasets.

Sample Input

1
2
3
4
5
6

0, 0
2, 0
1, 1
2, 2
0, 2
0, 0

Sample Output

1
2
3
4
5

0, 0
2, 0
2, 2
0, 2
0, 0

Solution

題目相當單純要輸出凸包的結果，但是最痛恨的是輸出格式，要求從輸入順序中最小的開始打印。

莫名其妙地弄了很多 WA 出來，也許輸入有重複點的關係，所以把點附加輸入編號可能會有所錯誤，總是暴力查找一個哪個點是要開始打印的即可。

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

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
        x(a), y(b) {}
    bool operator <(const Pt &a) const {
        if(x != a.x)       
            return x < a.x;
        return y < a.y;
    }   
    bool operator ==(const Pt &a) const {
        return x == a.x && y == a.y;
    }
};
int cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m - 1;
}
Pt D[100005], C[100005<<1], p;
Pt I[100005];
int main() {
	int cases = 0;
	char s[1024];
	while(gets(s)) {
		if(cases++ > 0)
			puts("");
		int n = 0, m, x, y;
		sscanf(s, "%d, %d", &x, &y);
		I[n] = D[n] = Pt(x, y);
		n++;
		while(gets(s) && s[0] != '\0') {
			sscanf(s, "%d, %d", &x, &y);
			I[n] = D[n] = Pt(x, y);
			n++;
		}
		m = monotone(n, D, C);
		int mark = -1;
		for(int i = 0; i < n && mark == -1; i++) {
			for(int j = 0; j < m; j++)
				if(C[j] == I[i]) {
					mark = j;
					break;
				}
		}
		for(int i = mark; i < m; i++)
			printf("%d, %d\n", C[i].x, C[i].y);	
		for(int i = 0; i <= mark; i++)
			printf("%d, %d\n", C[i].x, C[i].y);	
	}
	
    return 0;
}

Problem

Given the value of an n you will have to find the modulo 100000000 value of the following expression:

floor(sqrt(1)) + floor(sqrt(3)) + floor(sqrt(5)) + ... + floor(sqrt(m)) , where m is the largest odd number not greater than n. Or in other words you will have to find the value of S where,

S = floor(sqrt(1)) + floor(sqrt(3)) + floor(sqrt(5)) + ... + floor(sqrt(m)) MOD 100000000

Input

The input file contains at most 30000 lines of inputs. Each line contains a single 64-nit signed integer which denotes the value of n. Input is terminated by a line containing a single zero which should not b processed.

Output

For each line of input produce one line of output. This line contains the value of S.

Sample Input

1
2
3
4
5

9
19
29
10000000
0

Output for Sample Input

1
2
3
4

9
26
49
38426378

Solution

先把前幾項列出來，會發現一個規律

1
2
3
4
5
6
7
8

11
22
3333
4444
555555
666666
77777777
...

每一次會增加兩個。

假設第 1 組為 11 22，第 2 組為 3333 4444 …
需要使用二分搜尋找到我們總共要幾組，然後直接利用公式算出來 sigma(2i * (2i - 1 + 2i))。

但是公式算出來後，會有一個 /3 需要出處理，這邊使用乘法反元素，幸好 3 和 100000000 有互質，不然還真是沒有辦法避免大數運算，計算的時候請各種小心 overflow 的問題。

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

#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define MOD 100000000 
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra;
            lb -= n/m*rb;
        } else {
            ra -= n/m*la;
            rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    if(i)
        return (la%mod+mod)%mod;
    return (ra%mod+mod)%mod;
}
long long getM(long long n) {
	long long l = 0, r = 3037000499LL/2, m, ret;
	long long tmp;
	while(l <= r) {
		m = (l + r) / 2;
		tmp = 4 * (m) * (m + 1);
		if(tmp <= n)
			l = m + 1, ret = m;
		else
			r = m - 1;
	}
	return ret;
}
int main() {
	unsigned long long n;
	long long inv3 = inv(3, MOD);
	while(scanf("%llu", &n) == 1 && n) {
		long long ret = 0;/*
		for(long long i = 1; i <= n; i += 2) {
			// printf("%d\n", (int)sqrt(i));
			ret += (long long) sqrt(i);
			ret %= MOD;
		}
		printf("%lld\n", ret);*/
		unsigned long long m = getM(n);
		long long prev = 4*(m)*(m + 1)%MOD*(2*m + 1)%MOD*inv3%MOD - m * (m + 1)%MOD;
		unsigned long long pn = 4 * (m) * (m + 1) - 1;
		prev = (prev%MOD + MOD)%MOD;
		//printf("%lld %lld %lld\n", m, prev, pn);
		m++;
		if(pn + m * 4 < n) {
			prev += (2 * m - 1) * 2 * m%MOD;
			pn += m * 4;
			//printf("CROSS1 %llu %llu\n", pn, prev);
			prev += (n - pn)/2 * 2 * m%MOD;
			//printf("CROSS2 %llu %llu\n", m * 2, (n - pn) /2);
		} else {
			prev += (n - pn)/2 * (2 * m - 1)%MOD;
			//puts("CROSS3");
		}
		printf("%llu\n", (prev%MOD + MOD)%MOD);
	}
	return 0;
}
/*
11
22
3333
4444
555555
666666
77777777
...
*/
/*
10000000001
*/

接續

接續上一篇的 向 NachOS 4.0 作業進發 (1)，我們繼續完成排程處理，在原始的 NachOS 4.0 中，基礎排程是 Round-robin，它的運作方式藉由定時呼叫 threads/alarm.h 中的 Alarm::CallBack()，而呼叫的時脈來源設定為 machine/stats.h 中的 const int TimerTicks = 100; 決定，數值越小表示呼叫頻率越高，置換的次數就會上升。

目標 Scheduler

• FIFO (FCFS) 先來先服務
• SJF 最短工作優先
• Priority 最小優先權優先
• RR (Round-robin)
• multi-level queue 最後的大魔王

開始

第一步 - 測試

先來說說怎麼測試自己的寫的代碼正確性，不然怎麼寫都只是理論腦補，雖然會動，但是不知道是否寫對。

• 第一種方式為下達

    $ ./nachos -e ../test/test1 -e ../test/test2 ... 多個
  

  這樣必須自己設置優先權、Burst Time，這方面撰寫方式有兩種，其一是來亂，其二是較為正式，而在 Burst Time 的計算又分成兩種，一是執行前已知、二是執行時猜測。

  • 其一來亂寫法，

      $ ./nachos -e ../test/test1 -e ../test/test2 ... 多個
    

    不改變原本的的執行方式，直接在代碼中決策 thread fork 出來時所擁有的優先權和 Burst Time。

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

    static int testPriority = 0; void Thread::Fork(VoidFunctionPtr func, void *arg) { // morris add testPriority++; if(testPriority == 1) setPriority(64); else if(testPriority == 2) setPriority(128); else setPriority(64); // end morris add

    
    因此，您可能會寫出以上的代碼，當然我不建議這麼寫，雖然是一種測試方式，但這並不好，一開始就這麼錯得相當離譜。

  • 其二寫法，增加下達參數，不過這些參數格式要去查閱一下他們的參數傳遞建造，我想會寫成大概的樣子為

      $ ./nachos -e ../test/test1 -pw 64 -e ../test/test2  -pw 128 ... 
    

    多個為了不增加工作量，這裡就沒有親自去實作。某方面來說，可能要寫很多 small program 進行測試，並且撰寫時還要預測會跑多久，這難度會稍微提高。

• 第二種方式按照軟工的寫法
  來寫 test code 吧！如果細心一點，就會看到相關的 Class::SelfTest() 在很多 class 都有的，因此我們需要把 test code 寫到 SelfTest 中被呼叫。因此，不需要有實體的 process 運行，只是單純地測試我們寫的 scheduler 的排程順序是否正確。

  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

  void threadBody() { Thread *thread = kernel->currentThread; while (thread->getBurstTime() > 0) { thread->setBurstTime(thread->getBurstTime() - 1); kernel->interrupt->OneTick(); printf("%s: remaining %d\n", kernel->currentThread->getName(), kernel->currentThread->getBurstTime()); } } void Thread::SchedulingTest() { const int thread_num = 4; char *name[thread_num] = {"A", "B", "C", "D"}; int thread_priority[thread_num] = {5, 1, 3, 2}; int thread_burst[thread_num] = {3, 9, 7, 3}; Thread *t; for (int i = 0; i < thread_num; i ++) { t = new Thread(name[i]); t->setPriority(thread_priority[i]); t->setBurstTime(thread_burst[i]); t->Fork((VoidFunctionPtr) threadBody, (void *)NULL); } kernel->currentThread->Yield(); }

  
  請自行在 class Thread 增加 setPriority(), setBurstTime(), SchedulingTest() … 等 method header and body。

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

  class Thread { private: ... public: ... // morris add void setBurstTime(int t) {burstTime = t;} int getBurstTime() {return burstTime;} void setStartTime(int t) {startTime = t;} int getStartTime() {return startTime;} void setPriority(int t) {execPriority = t;} int getPriority() {return execPriority;} static void SchedulingTest(); private: // some of the private data for this class is listed above // morris add int burstTime; // predicted burst time int startTime; // the start time of the thread int execPriority; // the execute priority of the thread ... };

  
  接著是需要 call testcode 加入到 ThreadedKernel 中。

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

  void ThreadedKernel::SelfTest() { Semaphore *semaphore; SynchList<int> *synchList; LibSelfTest(); // test library routines currentThread->SelfTest(); // test thread switching Thread::SchedulingTest(); // test semaphore operation semaphore = new Semaphore("test", 0); ... }

  
  因此我們可以利用單一 module 就能進行檢查。

        $ cd code/threads
        $ ./nachos
  

  但是這種方式，並沒有決定我們要測試哪一種類型的 scheduler，額外需要設定參數，讓其選擇建造哪一種的 readyList(Thread*)

        $ cd code/threads
        $ ./nachos FCFS
        $ ./nachos SJF
        $ ./nachos Priority
        $ ./nachos RR
  

  預計要修成如上述的測試方式。

  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

  int main(int argc, char **argv) { ... debug = new Debug(debugArg); DEBUG(dbgThread, "Entering main"); // SchedulerType type = RR; if(strcmp(argv[1], "FCFS") == 0) { type = FIFO; } else if (strcmp(argv[1], "SJF") == 0) { type = SJF; } else if (strcmp(argv[1], "PRIORITY") == 0) { type = Priority; } else if (strcmp(argv[1], "RR") == 0) { type = RR; } // kernel = new KernelType(argc, argv); kernel->Initialize(type); CallOnUserAbort(Cleanup); // if user hits ctl-C kernel->SelfTest(); kernel->Run(); return 0; }

第一步測試撰寫就這麼結束，比起撰寫新的 code，不會進行測試也是徒勞。

雖然這麼說，實際運作也是先寫 code 再寫 test code，因為當時還不太懂這些，所以如果已經先寫了一些也不用難過，大家都是這麼走過來的。

如果不知道怎麼執行，哪還有什麼撰寫的欲望，如果不知道怎麼測試，那就是在黑暗中漫步。

第二步 - 撰寫

在撰寫開始前，如果使用走第一種測試方式的人，需要將實體記憶體用大一點，否則需要實作虛擬記憶體的 context-swith。

1
2
3

const unsigned int NumPhysPages = 64;  // morris modify, old value=32
const int MemorySize = (NumPhysPages * PageSize);
const int TLBSize = 4;			// if there is a TLB, make it small

若完成以上的修改，在 /userprog 下，執行

1

$ ./nachos -e ../test/test1 -e ../test/test2 -e ../test/test1

就不會跑出 segment fault 。

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

enum SchedulerType {
        RR,     // Round Robin
        SJF,
        Priority,
		FIFO
};
...
class Scheduler {
  public:
	Scheduler();
	Scheduler(SchedulerType type);		// Initialize list of ready threads 
	...
    	// morris add
	SchedulerType getSchedulerType() {return schedulerType;}
	void setSchedulerType(SchedulerType t) {schedulerType = t;}
  private:
	...
};

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

int SJFCompare(Thread *a, Thread *b) {
	if(a->getBurstTime() == b->getBurstTime())
		return 0;
	return a->getBurstTime() > b->getBurstTime() ? 1 : -1;
}
int PriorityCompare(Thread *a, Thread *b) {
	if(a->getPriority() == b->getPriority())
		return 0;
	return a->getPriority() > b->getPriority() ? 1 : -1;
}
int FIFOCompare(Thread *a, Thread *b) {
	return 1;
}
//----------------------------------------------------------------------
// Scheduler::Scheduler
// 	Initialize the list of ready but not running threads.
//	Initially, no ready threads.
//----------------------------------------------------------------------
Scheduler::Scheduler() {
	Scheduler(RR);
}
Scheduler::Scheduler(SchedulerType type)
{
	schedulerType = type;
	switch(schedulerType) {
	case RR:
		readyList = new List<Thread *>;
		break;
	case SJF:
		readyList = new SortedList<Thread *>(SJFCompare);
		break;
	case Priority:
		readyList = new SortedList<Thread *>(PriorityCompare);
		break;
	case FIFO:
		readyList = new SortedList<Thread *>(FIFOCompare);
	}
	toBeDestroyed = NULL;
} 

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

void 
Alarm::CallBack() 
{
    Interrupt *interrupt = kernel->interrupt;
    MachineStatus status = interrupt->getStatus();
    bool woken = _bedroom.MorningCall();
    kernel->currentThread->setPriority(kernel->currentThread->getPriority() - 1);
    if (status == IdleMode && !woken && _bedroom.IsEmpty()) {// is it time to quit?
        if (!interrupt->AnyFutureInterrupts()) {
	    timer->Disable();	// turn off the timer
	}
    } else {			// there's someone to preempt
	if(kernel->scheduler->getSchedulerType() == RR ||
		kernel->scheduler->getSchedulerType() == Priority ) {
//		interrupt->YieldOnReturn();
		cout << "=== interrupt->YieldOnReturn ===" << endl;
		interrupt->YieldOnReturn();
        }
    }
}

在 Burst Time 計算上，如果採用運行時估計，可以在以下代碼中進行計算。kernel->stats->userTicks 是執行 user program 的時間累加器 (也存有一個 system program 的時間累加器，運行 thread context-free, thread scheduling … 等時間用途。)

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

void 
Alarm::WaitUntil(int x) {
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    Thread* t = kernel->currentThread;
    // burst time
    int worktime = kernel->stats->userTicks - t->getStartTime();
    t->setBurstTime(t->getBurstTime() + worktime);
    t->setStartTime(kernel->stats->userTicks);
    cout << "Alarm::WaitUntil go sleep" << endl;
    _bedroom.PutToBed(t, x);
    kernel->interrupt->SetLevel(oldLevel);
}

其實到這裡已經完成，接下來就放幾張測試結果。

最後

如果在

1
2

$ cd code
$ make

編譯時發生錯誤，想必是兩個地方的 Initialize() 發生錯誤，所以請參照以下代碼進行修改。這問題是發生於我們在 /threads 下修改 main.cc 的關係，所以必須在每一個 kernel 宣告地方都給一個決定 scheduler 類型的參數。

其一,

1
2
3
4
5
6
7
8
9

#include "../threads/scheduler.h"
class SynchDisk;
class UserProgKernel : public ThreadedKernel {
  public:
  	...
    void Initialize();		// initialize the kernel 
    void Initialize(SchedulerType type);
    ...

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

void
UserProgKernel::Initialize()
{
    Initialize(RR);
}
void
UserProgKernel::Initialize(SchedulerType type)
{
    ThreadedKernel::Initialize(type);	// init multithreading
    machine = new Machine(debugUserProg);
    fileSystem = new FileSystem();
#ifdef FILESYS
    synchDisk = new SynchDisk("New SynchDisk");
#endif // FILESYS
}

1
2
3
4
5
6
7
8
9
10
11

#include "../threads/scheduler.h"
class PostOfficeInput;
class PostOfficeOutput;
class NetKernel : public UserProgKernel {
  public:
    ...
    void Initialize();		// initialize the kernel 
    void Initialize(SchedulerType);
    ...

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

void 
NetKernel::Initialize() {
	Initialize(RR);
}
void
NetKernel::Initialize(SchedulerType type)
{
    UserProgKernel::Initialize(type);	// init other kernel data structs
    postOfficeIn = new PostOfficeInput(10);
    postOfficeOut = new PostOfficeOutput(reliability, 10);
}

致網路資源

感謝網路上前人們所遺留的遺產。雖然在看不懂的文字中摸索，但仍抓到了一點線索。

我一無所有，直到見到了你們。