前文

課程 計算型智慧 報告，這是一門碩班課程，因此聽了許多學長的報告，雖然有難有易，牽扯的領域相當繁雜且艱深，例如影像分析、電機、醫學領域 … 等，很多都是有聽沒有懂，但是多少能明白一些些道理，即使後來挑選幾個進行實作，發現自己根本沒有理解，或者只是單純實作能力不足。

其中最常見到的報告內容是 B*-tree with floor plan，對於電子電路的配置擺放，要求最小化面積的操作。當然其中也有幾個跟我報告的預測性有關。對於影響分析就不多述了，其中也有幾個電費電流調控也挺有意思的，總之報告內容相當多元。

報告的時候，教授就在台下緊盯，而我剛好是在教授開會的時候報告，這學期僅我一個在教授不在的情況下報告。

• One Exam: 30%
  只有一次期中考，而且還是人腦仿電腦考試，但是題目沒有講清楚，考炸了不少，題目理解上把常數搞錯意思，但是這不影響廣義型算法，希望助教給點分！例如：在基因算法中交配的兩兩交配，難道就不能與自己交配嗎？而在粒子算法中，只給兩個參數，難道就不能只模仿全局最佳點和自己嗎？如果只有兩個參數，而且加總為一，您叫我如何模仿鄰居和自己，看來只能二選一。
• Homework: 40% (3 programs)
• Presentation: 30%
  教授不在的情況下仍可以報告，所以成績是由助教評定嗎？
• Questions: 3
  本課程一定要問三個問題，否則視如無效修課，但是問題我總是在課堂中發問，對於學長報告的內容有點作噁不明白。

論文挑選為「Building optimal regression tree by ant colony system – genetic algorithm Application to modeling of melting points」這是一篇化學期刊上的運用，不是在計算機領域的論文。

開始

從一個最簡單的應用開始

在二十個問題內，能猜出心中想的目標角色。這一類的遊戲相當多，在很多遊戲或者是心理測驗中都會用到，用來預測你大概會是哪一種類型的人、或者正在想什麼。
http://en.akinator.com/

決策樹

決策樹的分類

• Classification Tree：分類樹
  分類，輸出 “類型”
• Regression Tree：回歸樹
  關係程度，輸出 “數值”
• CART (Classification And Regression Tree) 即上述兩個的總稱

關於 CART

• 大量數據可以快速算出結果
• 易於理解 和 解釋
• 可以用統計數據驗證模型
• 最優 CART 是 NP 問題。
• 能力有限，只能對有限數據屬性操作
• 機器學習 Machine Learning 領域常用

論文實驗資料

• 4173 種化合物，分類屬性有 202 種描述方式。在 4173 種化合物中，3000 種用來訓練，1173 種用來驗證。
• 與另外一組經由 277 種藥物進行熔點預測的 CART 相比。(另外一篇論文做的結果)
• 目標預測更加準確。

CART–ACS–GA 理論

• 將 ACS – GA 算法，套用在 CART 的建造上。
• 先說說 ACS – GA 算法運作

ACS-GA

ACS–GA 算法 (蟻群遺傳混合算法)，基於 ACS 的缺點 – 收斂慢，加入 GA 算法來加快。

• 為什麼不單純使用 GA 算法就好？
• 對問題編碼的困難 (轉 DNA 的問題)，突變效果可能不好

螞蟻基因也有好壞問題

• 如何反應基因好壞
• 對費洛蒙決策的方式
• 對費洛蒙的敏感度 … 等

換句話說，將螞蟻的能力也各自數據化，對於產生較好解的螞蟻，繁殖、交配、突變，接著談論如何運用在 CART！

CART 建造

假解亂做前，如何隨機？CART 是一棵二分樹
How we do ?

• 基於深度優先的方式，直到某個葉節點的分類種數 < 30 或深度大於某個值，就退回。
• 每一層必須決定 “依據哪個屬性分類” Age ? Gender ? Last R ?
• 分類時，又要按照什麼 數值 進行分割。< 30 ? > 30 ? = 30 ?

假設 CART 有 m 個節點，n 個分類描述。在此篇中，化合物有 202 種描述，即 n = 202。

• 為了表示螞蟻的判斷能力，到達某個節點 i 時，採用下一個分類方式 k 的費洛蒙 M[i][k]
  i < m, k < n
• 這樣可以決定分類方式。對於某個節點 i，i 可以是目前累計完成的節點個數，或者是其他。

上面決定了分類方式，但沒決定分割點 ( cut point ) 的選擇方式。

• 假設用 10 種決策方式，來對應分類到節點內有的所有項目屬性，進行統計分類。
  • 決策方式 1：平均、眾數、權重、 ID3、C4.5 (熵理論和訊息增益) … 等分割策略
  • 決策方式 2 : 用 10 個常數對於屬性最大最小值 f(min, max) = x0 * min + x1 * max + x2 * min * max
  • 決策方式 3：最大最小值之間切 10 等分。
• 費洛蒙將會有 10 × n × m，即 M[10][n][m]。

關於適應函數

對於葉節點

Partial least squares method 不同於 “最小平方法”

• 多因變數 對 多自變數 的回歸建模方法
• 對於每一個葉節點的所有資料分別做偏最小二乘法，會得到分類的相聯性，也就是 相關係數 (correlation coefficient)
• 相關係數總和大小 與 適應力高低 成正比，用 驗證集 找到相關係數。

結論

• 對於下次迭代，偏向於好的切割屬性
• 對於切割屬性，可以得到好的分割點
• 排除單一分割策略的形式

Problem

In this problem your job is to find the distance between two lines or a line and a line segment or two line segments. Suppose we have two points A(x1,y1) and B(x2,y2) on a two dimensional Cartesian plane. If we connect A and B then we get line segment AB. But if we connect AB and extend it on both side at infinite length then we get line AB.

Input

The input file contains several sets of inputs. The description of each set of input is given below:

The description for each set of input is given in two lines. Each line contains four integers and a string. First line contains x1, y1, x2, y2 and S1 and the second line contains x3, y3, x4, y4 and S2. The value of S1 and S2 can be either “L” or “LS” which stands for “Line” and “Line-segment” respectively. (x1, y1) and (x2, y2) are the endpoints of first line segment or they are just two different points on the first line depending on the value of S1. The same story applies for the second input line for this set. Input is terminated by a set where the value of S1 and S1 is “END”. This set should not be processed. Point (x1,y1) and (x2,y2) are always different. Similarly point (x3,y3) and (x4,y4) are also always different. All the integers in the input file have absolute value less than 101.

Output

For each set of input you should produce one line of output which contains a single floating-point number indicating the distance between the two lines or line segments or the distance between one line and one line segment. This floating-point number contains five digits after the decimal point. Errors less than 2e-5 will be ignored.

Sample Input

1
2
3
4
5
6

10 10 20 20 L
-10 –10 19 19 L
10 10 12 13 LS
11 11 19 20 LS
10 10 12 12 END
11 11 23 34 END

Output for Sample Input

1
2

0.00000
0.27735

Solution

題目描述：

詢問 線段/線 和 線段/線 之間的最短距離為何。

題目解法：

據說這一題精準度卡很緊，上一次是在兩年前寫這一題，那是使用投影判斷，果真死在精度？

總之，為了避開投影精準度問題，使用外積和內積來判斷我們所有需要的條件。

• 兩線斷是否相交
• 一個點是否在線段兩端點之間 (線段上方/下方)
• 是否在線段上

以上三點接能只靠加減乘來完成，由於輸入值都是整數，不會有精度上的問題。

接著，個別討論所有配對情況要如何判斷。

• 線段與線段
  • 相交，最鄰近距離 0。
  • 不相交，查閱是否能作投影，否則直接查閱到端點的距離。
• 線與線
  • 不平行，最鄰近距離 0。
  • 平行，直接調用公式計算兩線距離。 // 當然可以調用投影距離。
• 線與線段
  • 線段跨過線的兩側，最鄰近距離 0
  • 同側，直接做投影。

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

#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
enum LINE_TYPE {LINE, SEGMENT};
struct LINE2D {
    Pt s, e;
    LINE_TYPE type;
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double 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 between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
double distProjection(Pt as, Pt at, Pt s) {
    int a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double closest(LINE2D l1, LINE2D l2) {
    if(l1.type == SEGMENT && l2.type == SEGMENT) {
        if(intersection(l1.s, l1.e, l2.s, l2.e))
            return 0;
        double c = 1e+30;
        if(between(l1.s, l1.e, l2.s))
            c = min(c, distProjection(l1.s, l1.e, l2.s));
        else
            c = min(c, min(dist(l1.s, l2.s), dist(l1.e, l2.s)));
            
        if(between(l1.s, l1.e, l2.e))
            c = min(c, distProjection(l1.s, l1.e, l2.e));
        else
            c = min(c, min(dist(l1.s, l2.e), dist(l1.e, l2.e)));
        /* opposite */
        if(between(l2.s, l2.e, l1.s))
            c = min(c, distProjection(l2.s, l2.e, l1.s));
        else
            c = min(c, min(dist(l1.s, l2.s), dist(l1.e, l2.s)));
            
        if(between(l2.s, l2.e, l1.e))
            c = min(c, distProjection(l2.s, l2.e, l1.e));
        else
            c = min(c, min(dist(l2.s, l1.e), dist(l2.e, l1.e)));
        return c;
    }
    if(l1.type == LINE && l2.type == LINE) {
        int a1, a2, b1, b2, c1, c2;
        a1 = l1.s.y - l1.e.y;
        b1 = l1.e.x - l1.s.x;
        c1 = - (a1 * l1.s.x + b1 * l1.s.y);
        a2 = l2.s.y - l2.e.y;
        b2 = l2.e.x - l2.s.x;
        c2 = - (a2 * l2.s.x + b2 * l2.s.y);
        if(a1 * b2 - a2 * b1 != 0)
            return 0;
        return distProjection(l1.s, l1.e, l2.s);
    }
    if(l1.type != l2.type) {
        if(l1.type == SEGMENT)
            swap(l1, l2);
        /* l1 LINE, l2 SEGMENT*/
        int a1, b1, c1;
        a1 = l1.s.y - l1.e.y;
        b1 = l1.e.x - l1.s.x;
        c1 = - (a1 * l1.s.x + b1 * l1.s.y);
        int v1, v2;
        v1 = a1 * l2.s.x + b1 * l2.s.y + c1;
        v2 = a1 * l2.e.x + b1 * l2.e.y + c1;
        if(v1 * v2 <= 0)
            return 0; // different side
        return min(distProjection(l1.s, l1.e, l2.s), distProjection(l1.s, l1.e, l2.e));
    }
    return -1;
}
int main() {
    // freopen("in.txt", "r+t", stdin);
    // freopen("out.txt", "w+t", stdout); 
    int x1, x2, y1, y2;
    LINE2D l1, l2;
    char s[1024];
    while(scanf("%d %d %d %d %s", &x1, &y1, &x2, &y2, s) == 5 && s[0] != 'E') {
        l1.s = Pt(x1, y1), l1.e = Pt(x2, y2);
        if(!strcmp("L", s))
            l1.type = LINE;
        else
            l1.type = SEGMENT;
        scanf("%d %d %d %d %s", &x1, &y1, &x2, &y2, s);
        l2.s = Pt(x1, y1), l2.e = Pt(x2, y2);
        if(!strcmp("L", s))
            l2.type = LINE;
        else
            l2.type = SEGMENT;
        double ret = closest(l1, l2);
        printf("%.5lf\n", ret);
    }
    return 0;
}
/*
10 10 20 20 L
-10 -10 19 19 L
10 10 12 13 LS
11 11 19 20 LS
1 1 2 2 LS
3 3 4 4 LS
1 1 2 2 LS
3 3 4 4 L
10 10 12 12 END
11 11 23 34 END
*/

Demo UVa OJ，標製作只有自己會用的 TAG，詳細請查閱 Github。

• 目前 javascript 存放在 Google Drive
• 每一篇限用一個 tag，無法解決多重匯入問題。如果硬是要匯入也行，只是會重複好幾次。
• 請確保每個頁面的 <head> 有引入 jquery 1.7.0 以上的版本。

順手測一下

GitHub jQuery Repo Widget

TEST

事實上只是將上述的 jQuery 修改而已。

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 {% math %}a = b + c{% endmath %}.

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

1

This equation{% math %}\cos 2\theta = \cos^2 \theta - \sin^2 \theta =  2 \cos^2 \theta - 1 {% endmath %} is inline.

更多

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