解題區►解題區 - UVa

UVa 844 - Pousse

Problem

模擬一款推硬幣的遊戲，在一個 N x N 的盤面，可以從上下左右四個方向塞入自己的硬幣。

現在有兩個人輪流玩，一開始由 ‘X’ 作為先手，塞入硬幣的過程中，會將同行或同列的硬幣往前推，如果同一個的硬幣個數大於 N，則末端的硬幣將會掉出盤面。

模擬遊戲，直到其中一個玩家的連線個數大於另一名玩家，連線個數只看行、列皆具有相同硬幣的情況。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT

Sample Output

1
2
3
TIE GAME
X WINS

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
#include <stdio.h> 
#include <string.h>
char cmd[32767][64];
char g[128][128];
int n;
int isCompleted() {
	int Oline = 0, Xline = 0, cnt;
	char c;
	for (int i = 0; i < n; i++) {
		c = g[i][0], cnt = 0;
		for (int j = 0; g[i][0] == g[i][j] && j < n; cnt++, j++);
		if (cnt == n && c != ' ') {
			Oline += c == 'O';
			Xline += c == 'X';
		}
		c = g[0][i], cnt = 0;
		for (int j = 0; g[0][i] == g[j][i] && j < n; cnt++, j++);
		if (cnt == n && c != ' ') {
			Oline += c == 'O';
			Xline += c == 'X';
		}
	}
	return Oline == Xline ? 0 : (Oline < Xline ? -1 : 1);
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		int m = 0;
		while (scanf("%s", cmd[m]) == 1) {
			if (!strcmp(cmd[m], "QUIT"))
				break;
			m++;
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				g[i][j] = ' ';
		int ret = 0, turn = 0;
		for (int i = 0; i < m; i++, turn = !turn) {
			int x;
			sscanf(cmd[i]+1, "%d", &x);
			x--;
			if (cmd[i][0] == 'L') {
				int idx = 0;
				while (idx < n && g[x][idx] != ' ')	idx++;
				for (int i = idx; i > 0; i--)
					g[x][i] = g[x][i-1];
				g[x][0] = turn ? 'O' : 'X';
			}
			if (cmd[i][0] == 'R') {
				int idx = n-1;
				while (idx > 0 && g[x][idx] != ' ')	idx--;
				for (int i = idx; i < n-1; i++)
					g[x][i] = g[x][i+1];
				g[x][n-1] = turn ? 'O' : 'X';
			}
			if (cmd[i][0] == 'T') {
				int idx = 0;
				while (idx < n && g[idx][x] != ' ')	idx++;
				for (int i = idx; i > 0; i--)
					g[i][x] = g[i-1][x];
				g[0][x] = turn ? 'O' : 'X';
			}			
			if (cmd[i][0] == 'B') {
				int idx = n-1;
				while (idx > 0 && g[idx][x] != ' ')	idx--;
				for (int i = idx; i < n-1; i++)
					g[i][x] = g[i+1][x];
				g[n-1][x] = turn ? 'O' : 'X';
			}
//			for (int i = 0; i < n; i++, puts(""))
//				for (int j = 0; j < n; j++)
//					putchar(g[i][j]);
//			puts("---");
			if (ret = isCompleted())
				break;
		}
		if (ret)
			puts(ret < 0 ? "X WINS" : "O WINS");
		else
			puts("TIE GAME");
		if (testcase)
			puts("");
	}
	return 0;
}
/*
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT
*/
Read More +
解題區►解題區 - UVa

UVa 828 - Deciphering Messages

Problem

給一加密原則，現在要求解密，並且在只有一組文本情況下輸出正解。

一開始給定一字串 L，接著加密時，每一組訊息的 word，由左而右加密。

  • 如果字符 c 存在於 L，使用凱薩加密 shift N 位。
  • 如果字符 c 不存在於 L，輸出三個字浮，分別是 L[m]、c 使用凱薩加密 shift N 位、L[m+1]。每一次使用這一條 m 就 +1，假想 L 是環狀的。

Sample Input

1
2
3
4
5
6
7
8
9
10
1
RSAEIO
2
5
RTSSKAEAGE
GRSCAV
RGSSCAV
RUSIQO
RUSSGAACEV JEGIITOOGR

Sample Output

1
2
3
4
5
RICE
error in encryption
EAT
error in encryption
SEAT HERE

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
int inL[128] = {}, N, Q, Llen;
char L[128], s[1024];
char text[128];
int sol;
void dfs(int idx, int pl, int m) {
	while (s[idx] == ' ')	text[pl++] = ' ', idx++;
	if (sol >= 2)	return;
	if (s[idx] == '\0') {
		sol++;
		text[pl] = '\0';
		puts(text);
		return;
	}
	
	char a, b, c;
	for (int i = 'A'; i <= 'Z'; i++) {
		if (inL[i]) {
			a = L[m%Llen];
			b = (i-'A'+N)%26 + 'A';
			c = L[(m+1)%Llen];
			text[pl] = i;
			if (a == s[idx] && b == s[idx+1] && c == s[idx+2]) {
				dfs(idx+3, pl+1, m+1);
			}
		} else {
			a = (i-'A'+N)%26 + 'A';
			text[pl] = i;
			if (a == s[idx]) {
				dfs(idx+1, pl+1, m);
			}
		} 
	}
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%s", L);
		scanf("%d %d", &N, &Q);
		memset(inL, 0, sizeof(inL));
		for (int i = 0; L[i]; i++)
			inL[L[i]] = 1;
		Llen = strlen(L);
		while (getchar() != '\n');
		for (int i = 0; i < Q; i++) {
			gets(s);
			sol = 0;
			dfs(0, 0, 0);
			if (sol != 1)
				puts("error in encryption");
		}
		if (testcase)
			puts("");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 818 - Cutting Chains

Problem

有 n 個鐵環，現在已知鐵環之間緊扣在一起，目標要把鐵環串成一鏈，可以選擇將鐵環剪開，隨後再將其串在一起。

找最少剪開的次數。

Sample Input

1
2
3
4
5
6
5 1 2 2 3 4 5 -1 -1
7 1 2 2 3 3 1 4 5 5 6 6 7 7 4 -1 -1
4 1 2 1 3 1 4 -1 -1
3 1 2 2 3 3 1 -1 -1
3 1 2 2 1 -1 -1
0

Sample Output

1
2
3
4
5
Set 1: Minimum links to open is 1
Set 2: Minimum links to open is 2
Set 3: Minimum links to open is 1
Set 4: Minimum links to open is 1
Set 5: Minimum links to open is 1

Solution

n < 15，窮舉哪幾個環需要剪開，接著把這些需要剪開的環先抽出來，查看剩餘的鐵環的情況，必須滿足都是鏈狀，而且連通元件的個數不能大於剪開的個數 + 1，如此一來，在放回剪開的環才能串在一起。

鏈狀的檢查：檢查每一個 node 的 degree 不可大於 2，同時不應該存在環。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int g[16][16], gmask[16];
int visited[16];
int dfs(int u, int p, int open, int n) {
	visited[u] = 1;
	for (int i = 0; i < n; i++) {
		if ((open>>i)&1)
			continue;
		if (g[u][i] == 0 || i == p)
			continue;
		if (visited[i] || dfs(i, u, open, n))
			return 1;
	}
	return 0;
}
int checkChain(int open, int n) {
	for (int i = 0; i < n; i++) {
		if ((open>>i)&1)
			continue;
		int t = gmask[i]^(gmask[i]&open);
		int degree = __builtin_popcount(t);
		if (degree > 2)
			return 0;
	}
	
	int op = __builtin_popcount(open);
	int comp = 0;
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < n; i++) {
		if ((open>>i)&1)	continue;
		if (visited[i] == 0) {
			if (dfs(i, -1, open, n)) // have cycle
				return 0;
			comp++;
		}
	}
	return op >= comp - 1;
}
int main() {
	int cases = 0;
	int n, x, y;
	while (scanf("%d", &n) == 1 && n) {
		memset(g, 0, sizeof(g));
		memset(gmask, 0, sizeof(gmask));
		while (scanf("%d %d", &x, &y) == 2) {
			if (x == -1)	break;
			x--, y--;
			g[x][y] = g[y][x] = 1;
			gmask[x] |= 1<<y, gmask[y] |= 1<<x;
		}
		
		int ret = 0x3f3f3f3f;
		for (int i = 0; i < (1<<n); i++) { // 1: open.
			int op = __builtin_popcount(i);
			if (op >= ret)	continue;
			if (checkChain(i, n))
				ret = min(ret, op); 
		}
		printf("Set %d: Minimum links to open is %d\n", ++cases, ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 814 - The Letter Carrier's Rounds

Problem

模擬郵件發送的協定訊息，給定給一台 mail server 上的使用者名稱，接著發送群組訊息。

每一組發送者，會按照輸入順序的 mail server，將相同的 server 上的使用者統一發送，如果存在不合法的使用者名稱，必須回傳找不到，如果對一個 mail server 中都沒有合法使用者，則忽略此次傳送。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report!  --Fiona
*
*

Sample Output

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
Connection between Cairo and MexicoCity
     HELO Cairo
     250
     MAIL FROM:<Hamdy@Cairo>
     250
     RCPT TO:<Conrado@MexicoCity>
     250
     RCPT TO:<Lisa@MexicoCity>
     550
     DATA
     354
     Congratulations on your efforts !!
     --Hamdy
     .
     250
     QUIT
     221
Connection between Cairo and SanFrancisco
     HELO Cairo
     250
     MAIL FROM:<Hamdy@Cairo>
     250
     RCPT TO:<Shariff@SanFrancisco>
     250
     DATA
     354
     Congratulations on your efforts !!
     --Hamdy
     .
     250
     QUIT
     221
Connection between London and HongKong
     HELO London
     250
     MAIL FROM:<Fiona@London>
     250
     RCPT TO:<Chen@HongKong>
     250
     DATA
     354
     Thanks for the report!  --Fiona
     .
     250
     QUIT
     221
Connection between London and Paris
     HELO London
     250
     MAIL FROM:<Fiona@London>
     250
     RCPT TO:<Natasha@Paris>
     550
     QUIT
     221

Solution

一個純模擬的題目，關於此類協定可以在計算機網路中學到。

保證寄信者都是合法的，小心每一行的資訊可能很長，用 char array 很容易 buffer overflow。也因此掛了很多 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
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 <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <vector> 
using namespace std;
set<string> MTA;
int readMTA() {
	string cmd, mta, name;
	int n;
	while (cin >> cmd) {
		if (cmd == "*")	return 1;
		cin >> mta >> n; 
		for (int i = 0; i < n; i++) {
			cin >> name;
			MTA.insert(string(name) + "@" + string(mta));
		}
	}
	return 0;
}
void parse_address(const string& s, string& user, string& mta) {
  int k = s.find('@');
  user = s.substr(0, k);
  mta = s.substr(k+1);
}
int main() {
	string msg;
	readMTA();
	while (cin >> msg) {
		if (msg[0] == '*')	break;	
		vector<string> user, mta, mail;
		set<string> S;
		vector<int>	used;
		string u, m;
		parse_address(msg, u, m);
		user.push_back(u), mta.push_back(m);
		while (cin >> msg && msg[0] != '*') {
			parse_address(msg, u, m);
			if (S.count(u + "@" + m))	continue;
			S.insert(u + "@" + m);
			user.push_back(u), mta.push_back(m);
		}
		while (getchar() != '\n');
		while (getline(cin, msg) && msg[0] != '*')
			mail.push_back(msg);
		used.resize(user.size(), 0);
		for (int i = 1; i < user.size(); i++) {
			if (used[i])	continue;
			printf("Connection between %s and %s\n", mta[0].c_str(), mta[i].c_str());
			printf("     HELO %s\n", mta[0].c_str());
			printf("     250\n");
			printf("     MAIL FROM:<%s@%s>\n", user[0].c_str(), mta[0].c_str());
			printf("     250\n");
			int s = 0;
			for (int j = i; j < user.size(); j++) {
				if (mta[j] == mta[i]) {
					used[j] = 1;
					printf("     RCPT TO:<%s@%s>\n", user[j].c_str(), mta[j].c_str());
					if (MTA.count(user[j] + "@" + mta[j]))
						printf("     250\n"), s++;
					else
						printf("     550\n");
				}
			}
			if (s > 0) {
				printf("     DATA\n");
				printf("     354\n");
				for (int j = 0; j < mail.size(); j++)
					printf("     %s\n", mail[j].c_str());
				printf("     .\n");
				printf("     250\n");
			}
			printf("     QUIT\n");
			printf("     221\n");
		}
	}
	return 0;
}
/*
MTA London 4 Fiona Paul Heather Nevil
MTA SanFrancisco 3 Mario Luigi Shariff
MTA Paris 3 Jacque Suzanne Maurice
MTA HongKong 3 Chen Jeng Hee
MTA MexicoCity 4 Conrado Estella Eva Raul
MTA Cairo 3 Hamdy Tarik Misa
*
Hamdy@Cairo Conrado@MexicoCity Shariff@SanFrancisco Lisa@MexicoCity
*
Congratulations on your efforts !!
--Hamdy
*
Fiona@London Chen@HongKong Natasha@Paris
*
Thanks for the report!  --Fiona
*
*
*/
Read More +
解題區►解題區 - UVa

UVa 810 - A Dicey Problem

Problem

給一個 2D 地圖，上面放置一骰子，人從 2D 地圖的下方往上方看，骰子必須貼著某一條邊，往上下左右的地方滾過去，滾的時候必須滿足，其骰子上方的點數與地圖該格的點數相同，或者是移動到星號位置。

一開始給定骰子面向玩家的點數、以及骰子上方的點數，骰子滾動出去回到原本地方的最短路徑為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DICEMAZE1
3 3 1 2 5 1
-1 2 4
5 5 6
6 -1 -1
DICEMAZE2
4 7 2 6 3 6
6 4 6 0 2 6 4
1 2 -1 5 3 6 1
5 3 4 5 6 4 2
4 1 2 0 3 -1 6
DICEMAZE3
3 3 1 1 2 4
2 2 3
4 5 6
-1 -1 -1
END

Sample Output

1
2
3
4
5
6
7
8
DICEMAZE1
  (1,2),(2,2),(2,3),(3,3),(3,2),(3,1),(2,1),(1,1),(1,2)
DICEMAZE2
  (2,6),(2,5),(2,4),(2,3),(2,2),(3,2),(4,2),(4,1),(3,1),
  (2,1),(2,2),(2,3),(2,4),(2,5),(1,5),(1,6),(1,7),(2,7),
  (3,7),(4,7),(4,6),(3,6),(2,6)
DICEMAZE3
  No Solution Possible

Solution

每一個 2D 位置 (x, y) 會有兩個骰子資訊做為紀錄，只需要知道骰子的兩個面，即可知道骰子的結構。

針對其狀態進行 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
#include <stdio.h>
#include <string.h> 
#include <queue>
#include <vector>
#include <assert.h>
using namespace std;
#define MAXSTATE 65536
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct state {
	int x, y, top, front;
	state *prev;
} states[MAXSTATE];
int statesIdx;
int n, m, sx, sy, dtop, dfront;
int g[32][32];
state* getNewState(int x, int y, int dtop, int dfront, state *prev = NULL) {
	state *p = &states[statesIdx++];
	assert (statesIdx < MAXSTATE);
	p->x = x, p->y = y, p->top = dtop, p->front = dfront, p->prev = prev;
	return p;
}
int diceTable[7][7]; // [front][top] = right
void rotateDice(int dir, int dtop, int dfront, int &rtop, int &rfront) {
	rtop = rfront = 1;
	if (dir == 0) { // roll up
		rtop = dfront, rfront = 7 - dtop;
	} else if (dir == 1) { // roll down
		rtop = 7 - dfront, rfront = dtop;
	} else if (dir == 2) { // roll left
		rfront = dfront;
		rtop = diceTable[dfront][dtop];
	} else if (dir == 3) { // roll right
		rfront = dfront;
		rtop = 7 - diceTable[dfront][dtop];
	}
}
void bfs(int sx, int sy, int dtop, int dfront) {
	statesIdx = 0;
	int used[32][32][7][7] = {}; // used[x][y][dtop][dfront]
	int tx, ty, tdtop, tdfront;
	queue<state*> Q;
	state *u, *v;
	Q.push(getNewState(sx, sy, dtop, dfront));
	used[sx][sy][dtop][dfront] = 1;
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		for (int i = 0; i < 4; i++) {
			tx = u->x + dx[i], ty = u->y + dy[i];
			if (tx <= 0 || ty <= 0 || tx > n || ty > m)
				continue;
			if (g[tx][ty] != -1 && g[tx][ty] != u->top)
				continue;
			if (tx == sx && ty == sy) { // back to start square, print result
				vector< pair<int, int> > ret;
				state *p = u;
				ret.push_back(make_pair(sx, sy));
				while (p != NULL) {
					ret.push_back(make_pair(p->x, p->y));
					p = p->prev;
				}
				for (int i = ret.size() - 1, j = 0; i >= 0; i--, j++) {
					if (j%9 == 0)	printf("  ");
					if (j%9 != 0)	printf(",");
					printf("(%d,%d)", ret[i].first, ret[i].second);					if (j%9 == 8 || i == 0)	{
						if (i)	printf(",\n");
						else	puts("");
					}
				}
				return ;
			}
			rotateDice(i, u->top, u->front, tdtop, tdfront);
			if (used[tx][ty][tdtop][tdfront])
				continue;
			used[tx][ty][tdtop][tdfront] = 1;
			v = getNewState(tx, ty, tdtop, tdfront, u);
			Q.push(v);
		}
	}
	puts("  No Solution Possible");
}
int main() {
	// diceface[front][top] = right
	diceTable[1][2] = 4, diceTable[1][3] = 2, diceTable[1][4] = 5, diceTable[1][5] = 3;
	diceTable[2][1] = 3, diceTable[2][3] = 6, diceTable[2][4] = 1, diceTable[2][6] = 4;
	diceTable[3][1] = 5, diceTable[3][2] = 1, diceTable[3][5] = 6, diceTable[3][6] = 2;
	diceTable[4][1] = 2, diceTable[4][2] = 6, diceTable[4][5] = 1, diceTable[4][6] = 5;
	diceTable[5][1] = 4, diceTable[5][3] = 1, diceTable[5][4] = 6, diceTable[5][6] = 3;
    diceTable[6][2] = 3, diceTable[6][3] = 5, diceTable[6][4] = 2, diceTable[6][5] = 4;
    
	char testcase[1024];
	while (scanf("%s", testcase) == 1) {
		if (!strcmp("END", testcase))
			break;
		scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &dtop, &dfront);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				scanf("%d", &g[i][j]);
		printf("%s\n", testcase);
		bfs(sx, sy, dtop, dfront);
	}
	return 0;
}
Read More +
學校課程►資料庫系統

資料庫系統－劉寶鈞

single value function 的意思？問問 劉寶鈞 老師 吧！

課程心得

強烈建議遠離 此課程，分析如下描述， 劉寶鈞 老師強烈建議把定義背得一模一樣，最好不要翻譯，因為很難達到一樣的水平，也很難說好。資料庫歷史悠久，因此歷史課程會持續一陣子，課程內容並沒有相當多的實務經驗。老師秉持著數年專業，保證嚴格批閱所有考卷。

如果沒人抱怨，我來說說這鬼畜的經歷，絕不能讓其消散。

期中考分析

保證題目描述與錯字 100% 複製考卷

  1. 傳統檔案系統為何不能共享 而資料庫如何做到可以共享？(10 分)
    傳統檔案系統的資料存在各自的電腦中，而且格式不一，有相當大的重複資料，由於各自管理所需要的資料，更新時間也會不一致，因此在共享的支援相當不利，共享的結果不一定是最新、不能同時匹配在不同的電腦中的資料。
    資料庫系統將資料集中化管理，收集到同一個系統中，並且藉由 SQL 中的 DML 支持使用者進行共享資料的存取、檢索，由系統管理同一時間多名使用者對資料的存取。
    上述為零分作答，劉寶鈞老師說明若沒提到 SCHEME DATA 一律零分。

  2. 以 Relation Model 為例 說明 Data Model 之三要素。(10 分)
    略說－有 資料表示法、資料的操作、約束條件，舉幾個例子便可完事。
    此題作答還算正常，但是沒有舉例子大致上會被扣到慘不忍睹。

  3. 比較說明 DDL 及 DML。(10 分)
    略說－Data Definition Language、Data Manipulation Language，分別是定義資料庫、資料表用的，另一個是對使用者詢問、操作資料。
    此題作答還算正常，但是沒有舉例子大致上會被扣到慘不忍睹。

  4. 何謂 3-value logic ？並證明 P OR (NOT P) = 1 在 2-value logic 是成立的，但在 3-value logic is not always true。(10 分)
    3-value logic 分別為 true, false, unknown。

在 2-value 中

P NOT P P OR (NOT P)
T F T
F T T

在 3-value 中

P NOT P P OR (NOT P)
T F T
F T T
unknown unknown unknown

用 0 表示 false, 1 表示 true, 1/2 表示 unknown，AND = MIN, OR = MAX, NOT = 1 - x。
=> P = 1/2, P OR (NOT P) = MAX(0.5, 1 - 0.5) = 0.5 = unknown。

unknown 不屬於 true，因此 3-value 在 P OR (NOT P) = 1 not always true。
以上作答零分，劉寶鈞老師在考卷上對 unknown 用紅筆寫了 What ? 一開始直接零分，之後才勉為其難拿到五分。投影片上面也這麼寫的，到底在 What ? 什麼勁，你自己拿出來講的東西上都這麼寫，寫下去分數還沒有？

  1. 寫出若含 NULL value 五個 single value function 的規則。(10 分)
    WHAT the fuck about single value function ?
    略列表 AND OR NOT EQUAL PRODUCT 的幾種情況。
    上述為零分作答，劉寶鈞老師說明 single value function 的要寫出 aggregate function。我問老師「為什麼不直接寫 aggregate function？」老師回答道「就是故意不這麼寫。」

  2. 寫出 SQL query 之 SELECT, FROM, WHERE, GROUP BY, HAVING 之義意。(10 分)
    錯字直接按表抄，這一題原本對於 HAVING 的解釋不夠完善，掛掉直接只剩下五分。WTF，五個定義錯一個就直接砍一半分數？對於 HAVING 只有寫提供 WHERE 無法進行 aggregation function 的判斷條件，必須與 GROUP BY 一起使用。這樣難道錯了嗎？GROUP BY 都解釋了，你還說我錯？

結語

我不是肚子裡的肥蟲，一定是我蠢得無可救藥，拿了不及格的成績？

很久沒有衝動想要殺人，這下子又開始想殺人。

助教不替老師改考卷，讓老師這樣改考卷行嗎？

我是個壞學生，這門課真的氣死人，出口罵髒話根本不足以洩憤。

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

UVa 1665 - Islands

Problem

給一個地勢圖，詢問若高度低於 x 時，有多少連通子圖。

Sample Input

1
2
3
4
5
6
7
8
1 
4 5 
1 2 3 3 1
1 3 2 2 1
2 1 3 4 3
1 2 2 2 2
5 
1 2 3 4 5

Sample Output

1
2 3 1 0 0

Solution

由於詢問操作的 x 是嚴格遞增，可以發現盤面上的元素越來越少。如果反過來操作，從高度 x 由大到小開始詢問，就可以發現元素越來越多，同時是一個聯集的操作，如此一來可以使用并查集運行。

把每一個高度位置，從高到低排序，針對詢問依序將地點放置進去，每次的放置必須與相鄰存在的元素進行聯集。

為了加快速度

  • 使用基數排序，加快對於一開始需要的排序成本，已達到線性需求。
  • 優化輸入
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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm> 
using namespace std;
#define MAXN 1024
int g[MAXN][MAXN], h[131072], out[131072];
int parent[MAXN * MAXN], weight[MAXN * MAXN];
struct Pos {
	int x, y, h;
	Pos(int a = 0, int b = 0, int c = 0):
		x(a), y(b), h(c) {}
	bool operator<(const Pos &a) const {
		return h > a.h;
	}
};
int findp(int x) {
	return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
	x = findp(x), y = findp(y);
	if (x == y)	return 0;
	if (weight[x] > weight[y])
		weight[x] += weight[y], parent[y] = x;
	else
		weight[y] += weight[x], parent[x] = y;
	return 1;
}
Pos D[MAXN * MAXN], TMP[MAXN * MAXN];
void RadixSort(Pos *A, Pos *B, int n) {
    int a, x, d, C[256];
    Pos *T;
    for(x = 0; x < 4; x++) {
        d = x * 8;
        for(a = 0; a < 256; a++)     	C[a] = 0;
        for(a = n-1; a >= 0; a--)      	C[(A[a].h>>d)&255]++;
        for(a = 256 - 2; a >= 0; a--)   C[a] += C[a+1];
        for(a = n-1; a >= 0; a--)   	B[--C[(A[a].h>>d)&255]] = A[a];
        T = A, A = B, B = T;
    }    
}
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
	const int dx[] = {0, 0, 1, -1};
	const int dy[] = {1, -1, 0, 0};
	int testcase, n, m, q, tx, ty;
//	scanf("%d", &testcase);
	ReadInt(&testcase);
	while (testcase--) {
//		scanf("%d %d", &n, &m);
		ReadInt(&n);
		ReadInt(&m);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
//				scanf("%d", &g[i][j]);
				ReadInt(&g[i][j]);
//		scanf("%d", &q);
		ReadInt(&q);
		for (int i = 0; i < q; i++)
//			scanf("%d", &h[i]);
			ReadInt(&h[i]);
		
		int didx = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				D[didx++] = Pos(i, j, g[i][j]);
			}
		}
		RadixSort(D, TMP, n*m);
		int idx = 0, nm = n*m, sum = 0;
		Pos u;
		for (int i = nm; i >= 0; i--)
			parent[i] = i, weight[i] = 1;
		for (int i = q - 1; i >= 0; i--) {
			while (idx < nm && D[idx].h > h[i]) {
				sum++;
				u = D[idx++];
//				printf("add %d %d - %d\n", u.x, u.y, u.h);
				for (int j = 0; j < 4; j++) {
					tx = u.x + dx[j], ty = u.y + dy[j];
					if (tx < 0 || ty < 0 || tx >= n || ty >= m)
						continue;
					if (g[tx][ty] > h[i]) {
						sum -= joint(u.x * m + u.y, tx * m + ty);
					}
				}
			}
			out[i] = sum;
//			printf("%d\n", sum);
		}
		for (int i = 0; i < q; i++)
			printf("%d ", out[i]);
		puts("");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12412 - A Typical Homework

Problem

寫一個模擬成績登錄系統的程式。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
0011223344 1 John 79 98 91 100
0022334455 1 Tom 59 72 60 81
0011223344 2 Alice 100 100 100 100
2423475629 2 John 60 80 30 99
0
3
0022334455
John
0
5
1
2
0011223344
0
5
0
4
0

Sample Output

1
略

Solution

純苦工題目。

Try adding 1e-5 to all floating point values as you print them.

難怪會 WA，看到時小夥伴們都傻眼，不過應該也是因為大部分仍然使用 float 輸出，用 double 反而會得到 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
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
// WTF > Try adding 1e-5 to all floating point values as you print them.
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define eps 1e-5
class Student {
	public:
	string SID, name;
	int CID, score[4];
	Student(int c, int d[], string a = "", string b = "") {
		SID = a, name = b;
		CID = c;
		for (int i = 0; i < 4; i++)
			score[i] = d[i];
	}
	void print() {
		printf("%s %d %s %d %d %d %d %d %.2lf\n", 
			SID.c_str(), CID, name.c_str(),
				score[0], score[1], score[2], score[3], getTotal(), getAvg());
	}
	int getTotal() {
		return score[0] + score[1] + score[2] + score[3];
	}
	double getAvg() {
		return (score[0] + score[1] + score[2] + score[3]) / 4.0 + eps;
	}
};
class SPMS {
	public:
	map<string, int> R_SID;
	vector<Student> students;
	void printMainMenu() {
		puts("Welcome to Student Performance Management System (SPMS).\n");
		puts("1 - Add\n2 - Remove\n3 - Query\n4 - Show ranking\n5 - Show Statistics\n0 - Exit\n");
	}
	void addStudent() {
		char SID[128], name[128];
		int CID, score[4];
		while (true) {
			puts("Please enter the SID, CID, name and four scores. Enter 0 to finish.");
			scanf("%s", SID);
			if (!strcmp(SID, "0"))
				return;
			scanf("%d %s", &CID, name);
			for (int i = 0; i < 4; i++)	scanf("%d", &score[i]);
			
			if (R_SID[SID]) {
				puts("Duplicated SID.");
			} else {
				R_SID[SID]++;
				Student u(CID, score, SID, name);
				students.push_back(u);
			}
		}
	}
	void removeStudent() {
		char s[128];
		while (true) {
			puts("Please enter SID or name. Enter 0 to finish.");
			scanf("%s", s);
			if (!strcmp(s, "0"))
				return;
			int cnt = 0;
			for (vector<Student>::iterator it = students.begin();
				it != students.end(); ) {
				if (it->SID == s || it->name == s) {
					cnt++;
					R_SID[it->SID]--;
					it = students.erase(it);
				} else {
					it++;
				}
			}
			printf("%d student(s) removed.\n", cnt);
		}
	}
	int getRank(Student u) {
		int ret = 1;
		for (int i = 0; i < students.size(); i++)
			if (students[i].getTotal() > u.getTotal())
				ret++;
		return ret;
	}
	void queryStudent() {
		char s[128];
		while (true) {
			puts("Please enter SID or name. Enter 0 to finish.");
			scanf("%s", s);
			if (!strcmp(s, "0"))
				return;
			for (vector<Student>::iterator it = students.begin();
				it != students.end(); it++) {
				if (it->SID == s || it->name == s) {
					printf("%d ", getRank(*it));
					it->print();
				}
			}
		}
	}
	void printRankList() {
		puts("Showing the ranklist hurts students' self-esteem. Don't do that.");
	}
	void printStatistics() {
		puts("Please enter class ID, 0 for the whole statistics.");
		int CID;
		scanf("%d", &CID);
		
		int pass[4] = {}, fail[4] = {}; // subject
		int sum[4] = {}, n = 0;
		int sumtable[5] = {};
		vector<int> table; // student
		table.resize(students.size(), 0); 
		for (int i = 0; i < students.size(); i++) {
			if (CID && CID != students[i].CID)
				continue;
			n++;
			for (int j = 0; j < 4; j++) {
				sum[j] += students[i].score[j];
				if (students[i].score[j] >= 60) {
					pass[j]++;
					table[i]++;
				} else {
					fail[j]++;
				}
			}
			sumtable[table[i]]++;
		}
		
		for (int i = 3; i >= 1; i--)
			sumtable[i] += sumtable[i+1];
		printf("Chinese\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
			(double) sum[0] / n + eps, pass[0], fail[0]);
		printf("Mathematics\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
			(double) sum[1] / n + eps, pass[1], fail[1]);
		printf("English\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
			(double) sum[2] / n + eps, pass[2], fail[2]);
		printf("Programming\nAverage Score: %.2lf\nNumber of passed students: %d\nNumber of failed students: %d\n\n",
			(double) sum[3] / n + eps, pass[3], fail[3]);
		printf("Overall:\nNumber of students who passed all subjects: %d\nNumber of students who passed 3 or more subjects: %d\nNumber of students who passed 2 or more subjects: %d\nNumber of students who passed 1 or more subjects: %d\nNumber of students who failed all subjects: %d\n\n",
			sumtable[4], sumtable[3], sumtable[2], sumtable[1], sumtable[0]);
	}
} spms;
int main() {
	int cmd;
	while (true) {
		spms.printMainMenu();	
		scanf("%d", &cmd);
		if (cmd == 0)
			return 0;
		if (cmd == 1)
			spms.addStudent();
		if (cmd == 2)
			spms.removeStudent();
		if (cmd == 3)
			spms.queryStudent();
		if (cmd == 4)
			spms.printRankList();
		if (cmd == 5)
			spms.printStatistics();
	}	
	return 0;
}
/*
1
0011223344 1 John 79 98 91 100
0022334455 1 Tom 59 72 60 81
0011223344 2 Alice 100 100 100 100
2423475629 2 John 60 80 30 99
0
3
0022334455
John
0
5
1
2
*/
Read More +
解題區►解題區 - UVa

UVa 12462 - Rectangle

Problem

在長條圖中，每一條有其的數值和顏色屬性，找到一個最大的面積，使得每一個顏色都出現過。

Sample Input

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

Sample Output

1
2
3
4
5
6
7
9
6
5
12
10
10
2999999991

Solution

對於每一個長條 h[i]，勢必將往左往右延伸到第一個數值比較低的，因此會得到一個區間 [l, r]，如果 [l, r] 之間不具有所有顏色，則忽略之。反之紀錄 h[i] * (r - l + 1) 是否為最大值。這樣的貪心方式，盡可能會具有最多的顏色，同時考慮到所有最大面積會卡住的地方。

但是窮舉找到每一個 [l, r] 相當費時，這裡運用單調堆的思路，分別從左、從右側往反方向掃描，掃描時維護堆裡面元素呈現遞減情況，分別找到左右端點後，檢查是否區間內有相符的顏色個數。

找所有左右端點只需要 O(n) 時間，但是檢查區間內的顏色個數是否符合則必須 O(nm)。

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
#include <stdio.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
#define MAXN 131072
#define MAXC 32
int h[MAXN], c[MAXN], sumc[MAXN][MAXC];
int L[MAXN], R[MAXN]; 
int main() {
	int N, C;
	while (scanf("%d %d", &N, &C) == 2 && N) {
		for (int i = 1; i <= N; i++)
			scanf("%d", &h[i]);
		for (int i = 1; i <= N; i++)
			scanf("%d", &c[i]);
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < C; j++)
				sumc[i][j] = sumc[i-1][j];
			sumc[i][c[i]]++;
		}
		for (int i = 0; i < C; i++)
			sumc[N+1][i] = sumc[N][i]; 
			
		h[0] = h[N+1] = 0;
		stack<int> stk;
		stk.push(0);
		for (int i = 1; i <= N; i++) {
			while (h[i] <= h[stk.top()])
				stk.pop();
			L[i] = stk.top() + 1, stk.push(i);
		}
		
		while (!stk.empty())	stk.pop();
		
		stk.push(N + 1);
		for (int i = N; i >= 1; i--) {
			while (h[i] <= h[stk.top()])
				stk.pop();
			R[i] = stk.top() - 1, stk.push(i);
		}
		
		long long ret = 0;
		for (int i = 1; i <= N; i++) {
			int ok = 1;
			for (int j = 0; j < C; j++)
				ok &= sumc[R[i]][j] - sumc[L[i] - 1][j] > 0;
			if (ok)
				ret = max(ret, (long long) h[i] * (R[i] - L[i] + 1));
		}
		printf("%lld\n", ret);
	}
	return 0;
}
/*
6 3
2 3 1 7 3 5
2 0 1 0 1 2
3 1
2 2 2
0 0 0
5 2
3 2 1 2 3
1 0 1 0 1
6 4
1 2 3 4 5 6
0 1 2 3 1 0
7 2
1 2 3 4 3 2 1
0 1 0 1 0 1 0
10 2
2 1 2 1 1 2 1 2 2 1
1 0 0 0 1 0 0 1 1 0
3 2
1000000000 999999997 999999999
0 1 1
*/
Read More +
解題區►解題區 - UVa

UVa 12618 - I Puzzle You

Problem

給一個 n = 3 魔術方塊的盤面，找最少操作次數使其每一面顏色都相同。

每一次操作限定旋轉 90 度。如果需要的步數大於 7 步，直接輸出 Impossible。

Sample Input

1
2
3
4
5
4
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY
WWWWWWRRRRRYBBBWOOGGGRRYBBBWOOGGGRRYBBBWOOGGGOOOYYYYYY
WWBWWBWWBRRRBBYOOOWGGBBYOOOWGGRRRRRRBBYOOOWGGYYGYYGYYG
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYGGGYYYYYY

Sample Output

1
2
3
4
Case 1: 0
Case 2: 1
Case 3: 2
Case 4: Impossible

Solution

首先，關於旋轉操作只能手動打表，總共會有 9 種旋轉序列 (窮舉時操作成順、逆兩種)，其中的 6 種序列會使得相鄰的面旋轉 90 度 (必須特別考慮這邊緣的旋轉)。

關於啟發式：六個面中，其中一個面具有最多的顏色，將會是預估的最少移動操作。

這一個啟發式相當重要，也非常難想，參考 http://blog.csdn.net/qq564690377/article/details/16867503

一開始使用 IDA* 的效果似乎不很好，於是換了雙向 BFS (doubling BFS)，由於步數限定 7 步內，從目標狀態建表 4 步內的結果。接著對於每一組詢問，搜索 3 步內的操作，查看是否會相遇。

狀態壓縮可以採用重新命名，也就是最小化表示法，不管顏色，只考慮同構。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
#include <stdio.h> 
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int rotateInfo[9][12] = {
	{1, 4, 7, 13, 25, 37, 46, 49, 52, 45, 33, 21}, // margin rotate begin
	{3, 6, 9, 15, 27, 39, 48, 51, 54, 43, 31, 19},
	{10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21},
	{34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45},
	{1, 2, 3, 18, 30, 42, 54, 53, 52, 34, 22, 10},
	{7, 8, 9, 16, 28, 40, 48, 47, 46, 36, 24, 12},
	{2, 5, 8, 14, 26, 38, 47, 50, 53, 44, 32, 20}, // center rotate begin
	{4, 5, 6, 17, 29, 41, 51, 50, 49, 35, 23, 11},
	{22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}
};
int rotateFace[6][9] = { // not center rotate
	{10, 11, 12, 22, 23, 24, 34, 35, 36},
	{18, 17, 16, 30, 29, 28, 42, 41, 40},
	{1, 4, 7, 2, 5, 8, 3, 6, 9},
	{52, 49, 46, 53, 50, 47, 54, 51, 48},
	{21, 20, 19, 33, 32, 31, 45, 44, 43},
	{13, 14, 15, 25, 26, 27, 37, 38, 39}
};
int rotateOrder1[9] = {2, 5, 8, 1, 4, 7, 0, 3, 6};
int rotateOrder2[9] = {6, 3, 0, 7, 4, 1, 8, 5, 2};
int face[6][9] = {
	{1, 2, 3, 4, 5, 6, 7, 8, 9},
	{10, 11, 12, 22, 23, 24, 34, 35, 36},
	{13, 14, 15, 25, 26, 27, 37, 38, 39},
	{16, 17, 18, 28, 29, 30, 40, 41, 42},
	{19, 20, 21, 31, 32, 33, 43, 44, 45},
	{46, 47, 48, 49, 50, 51, 52, 53, 54}
};
map<string, int> Rstep, Bstep;
void adjustInfo() {
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 12; j++)
			rotateInfo[i][j]--;
	for (int i = 0; i < 6; i++)
		for (int j = 0; j < 9; j++)
			face[i][j]--;
	for (int i = 0; i < 6; i++)
		for (int j = 0; j < 9; j++)
			rotateFace[i][j]--;
}
int isCompleted(const char A[]) {
	for (int i = 0; i < 6; i++) {
		int ok = 1;
		for (int j = 0; j < 9; j++)
			ok &= A[face[i][j]] == A[face[i][0]];
		if (!ok)	return ok;
	}
	return 1;
}
string reduceCube(string u) {
	static int used[128] = {}, R[128], testcase = 0;
	char idx = 'A';
	testcase++;
	for (int i = 0; i < u.length(); i++) {
		if (used[u[i]] != testcase) {
			R[u[i]] = idx++, used[u[i]] = testcase;
		}
		u[i] = R[u[i]];
	}
	return u;
}
string rotateCube(string u, int kind, int dir) {
	static int a, b, c;
	static char tmp[9];
	if (dir == 0) {
		char v[3] = {u[rotateInfo[kind][0]], u[rotateInfo[kind][1]], u[rotateInfo[kind][2]]};
		for (int i = 0; i < 3; i++) {
			a = i * 3, b = i * 3 + 1, c = i * 3 + 2;
			u[rotateInfo[kind][a]] = u[rotateInfo[kind][a + 3]];
			u[rotateInfo[kind][b]] = u[rotateInfo[kind][b + 3]];
			u[rotateInfo[kind][c]] = u[rotateInfo[kind][c + 3]];
		}
		a = 3 * 3, b = 3 * 3 + 1, c = 3 * 3 + 2;
		u[rotateInfo[kind][a]] = v[0];
		u[rotateInfo[kind][b]] = v[1];
		u[rotateInfo[kind][c]] = v[2];
		if (kind < 6) {
			for (int i = 0; i < 9; i++)
				tmp[i] = u[rotateFace[kind][i]];
			for (int i = 0; i < 9; i++)
				u[rotateFace[kind][i]] = tmp[rotateOrder1[i]];
		}
	} else {
		char v[3] = {u[rotateInfo[kind][9]], u[rotateInfo[kind][10]], u[rotateInfo[kind][11]]};
		for (int i = 3; i > 0; i--) {
			a = i * 3, b = i * 3 + 1, c = i * 3 + 2;
			u[rotateInfo[kind][a]] = u[rotateInfo[kind][a - 3]];
			u[rotateInfo[kind][b]] = u[rotateInfo[kind][b - 3]];
			u[rotateInfo[kind][c]] = u[rotateInfo[kind][c - 3]];
		}
		a = 0, b = 1, c = 2;
		u[rotateInfo[kind][a]] = v[0];
		u[rotateInfo[kind][b]] = v[1];
		u[rotateInfo[kind][c]] = v[2];		
		if (kind < 6) {
			for (int i = 0; i < 9; i++)
				tmp[i] = u[rotateFace[kind][i]];
			for (int i = 0; i < 9; i++)
				u[rotateFace[kind][i]] = tmp[rotateOrder2[i]];
		}
	}
	return u;
}
int hfunction(string u) {
	static int used[128] = {}, testcase = 0, cnt = 0;
	int ret = 0;
	for (int i = 0; i < 6; i++) {
		testcase++, cnt = 0;
		for (int j = 0; j < 9; j++) {
			if (used[u[face[i][j]]] != testcase) {
				used[u[face[i][j]]] = testcase;
				cnt++;
			}
		}
		ret = max(ret, cnt - 1);
	}
	return ret;
}
void bfs(string A) {
	queue<string> Q;
	string u, v;
	Rstep.clear();
	A = reduceCube(A); 
	Q.push(A), Rstep[A] = 0;
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		int step = Rstep[u];
		if (step >= 4)	continue;
		for (int i = 0; i < 9; i++) {
			v = reduceCube(rotateCube(u, i, 0));
			if (Rstep.find(v) == Rstep.end()) {
				Rstep[v] = step + 1;
				Q.push(v);
			}
			v = reduceCube(rotateCube(u, i, 1));
			if (Rstep.find(v) == Rstep.end()) {
				Rstep[v] = step + 1;
				Q.push(v);
			}
		}
	}
//	printf("4 steps state %d\n", Rstep.size());
}
int bfs2(string A) {
	if (isCompleted(A.c_str()))
		return 0;
	queue<string> Q;
	string u, v;
	Bstep.clear();
	A = reduceCube(A); 
	Q.push(A), Bstep[A] = 0;
	int ret = 0x3f3f3f3f;
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		int step = Bstep[u];
		if (Rstep.find(u) != Rstep.end())
			ret = min(ret, step + Rstep[u]);
		if (step >= 3 || step + hfunction(u) >= min(7, ret))
			continue;
		for (int i = 0; i < 9; i++) {
			v = reduceCube(rotateCube(u, i, 0));
			if (Bstep.find(v) == Bstep.end()) {
				Bstep[v] = step + 1;
				Q.push(v);
			}
			v = reduceCube(rotateCube(u, i, 1));
			if (Bstep.find(v) == Bstep.end()) {
				Bstep[v] = step + 1;
				Q.push(v);
			}
		}
	}
	return ret <= 7 ? ret : -1;
}
int main() {
	adjustInfo();
	bfs("WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY");
	int testcase, cases = 0;
	char A[64];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%s", A);
		int ret = bfs2(A);
		
		printf("Case %d: ", ++cases);
		if (ret == -1)
			puts("Impossible");
		else
			printf("%d\n", ret);
	}
	return 0;
}
/*
      W W W                               1  2  3
      W W W                               4  5  6
      W W W                               7  8  9
R R R B B B O O O G G G         10 11 12 13 14 15 16 17 18 19 20 21
R R R B B B O O O G G G         22 23 24 25 26 27 28 29 30 31 32 33
R R R B B B O O O G G G         34 35 36 37 38 39 40 41 42 43 44 45
      Y Y Y                              46 47 48
      Y Y Y                              49 50 51
      Y Y Y                              52 53 54
4
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY
WWWWWWRRRRRYBBBWOOGGGRRYBBBWOOGGGRRYBBBWOOGGGOOOYYYYYY
WWBWWBWWBRRRBBYOOOWGGBBYOOOWGGRRRRRRBBYOOOWGGYYGYYGYYG
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYGGGYYYYYY
*/
Read More +