解題區/解題區 - UVa

UVa 11638 - Temperature Monitoring

Problem

We have a device to monitor temperature. After configuring it, we place it inside the chamber whose temperature we wish to monitor. The device is equipped with four alarms each of which can be configured differently. The Alarms are identified by the numbers 1, 2, 3 and 4. The device takes a reading of its surrounding at a regular interval.

In this problem you will be simulating the behavior of such a device.

我們有一個監測溫度裝置，在安裝配置後，將其放入所要監控溫度的室內。這個裝置共有四個警報器，分別編號為 1, 2, 3, 4，這些警報器將會每隔固定一段時間進行溫度檢測。
在這個問題中，請模擬這裝置的行為。

Input

The first line of input contains a positive integer T<101, which denotes the number of test cases. Each case consists of several lines which are described below.

輸入第一行為測資筆數 T (T < 101)

The first line contains a positive integer M, which denotes the measurement interval. That is, the device takes a reading every M seconds.

每一組測資第一行為一個正整數 M，表示裝置每隔 M 秒會進行偵測。

The second line contains a non-negative integer S, which denotes the ‘Startup delay’. This is the amount of time that the device will remain idle after placing inside the chamber before it takes its first reading. The device will instantly take a reading when the ‘Startup delay’ ends.

第二行為一個非負整數 S，表示裝置在前 S 秒正在安裝，這段時間機器將不會進行偵測，在安裝完後，將會立即地進行檢測。

The third line contains four integers. The integers give the threshold temperature for alarm 1,2,3,4 respectively. Here threshold temperature means, when a recorded temperature crosses this temperature the corresponding alarm will be triggered.

第三行會有 4 個正整數，分別表示警報器 1, 2, 3, 4 的警報閥值 (根據閥值進行溫度比較)

The fourth line contains a non-negative integer C. The least significant 8 bits of this integer represents the configurations of the four alarms. The rightmost 4 bits (bit 0 to 3) determine if the alarms are enabled(bit value 1) or disabled(bit value 0). For example, if the bits are set as 0011, this means Alarm 1 and 2 are enabled and Alarm 3 and 4 are disabled. If an alarm is disabled, it will never be triggered.

第四行將會有一個非負整數 C，用最低的 8 個 bits 表示警報器的設定，最右邊的 4 個 bits (bit 0 to bit 3) 表示警報器是否有啟動 (1 表示有啟動，反之則否)，例如 0011 表示警報器 1, 2 被啟動，3, 4 則沒有被啟動。如果警報器沒有被啟動，則將不會被觸發。

The next 4 bits(bits 4 to 7) determine the triggering type of each alarm. A value of 0 means, it’s a low trigger and a value of 1 means it’s a high trigger. For example, if the bits are set as 1100, this means Alarm 1 and 2 are set for low trigger and Alarm 3 and 4 for high trigger. Here high trigger means if a recorded temperature is above the set threshold temperature for an alarm, it will be triggered. Similarly, a Low trigger means if a recorded temperature is below the set threshold temperature for an alarm, that alarm will be triggered.

接下來的 4 個 bits 將會決定警報器的類型，亦即表示 1 高觸發 (大於閥值觸發) 0 表示低觸發 (低於閥值觸發)。例如 1100，警報器 1, 2 將會是低觸發，3, 4 則會是高觸發。

The fifth line contains a positive integer K<=100. The following K lines contain a pair of integers each in the format time temp. Here time represents the duration of a period with constant temperature and temp indicates the temperature of the environment in that period. Note that, time is always positive. The time value of first pair indicates the period immediately following the placement of the device inside the environment to be monitored. Successive time values indicate the duration of periods in the order they occur. The temperature at the border regions is considered to be that of the period just ending. Also, the temperature at the very beginning is that of the first period. Every value in the input will fit in 32 bit signed integer.

第五行將會有一個正整數 K，表示接下來依序發生的時間情況。將會從時間 0 開始，依序播報 (duration, temp) 表示新的溫度持續多久 (duration)。假設所有數據皆可以在 32 bits 內。

Output

For each case of input, there will be one line of output. It will first contain the case number, followed by the triggering status of each of the four alarms. The triggering status will contain four strings of either yes or no, separated by a space. The first string will be yes if alarm 1 was triggered at least once and no otherwise. The second string will be the status of alarm 2 and so on. Look at the sample output for exact formatting.

Sample Input

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

Output for Sample Input

1
2
Case 1: no no no yes
Case 2: no no no no

Solution

題目相當令人討厭，因為區間涵蓋沒有講得很清楚。

但是最後可以明白的是

[ti, tj][tj, tk] 其中 ti < tj < tk，我們在討論觸發的時候，端點是需要被考慮的。

詳細操作，詳見代碼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h> 
int main() {
    int testcase, cases = 0;
    int M; /* the device takes a reading every M seconds. */
    int S; /* The device will instantly take a reading when the ‘Startup delay’ ends. */
    int threshold[4]; /* */
    int C; /* */
    int enable[4], trigger[4]; /* trigger 0 <, 1 > */
    int K, time, temp;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &M);
        scanf("%d", &S);
        for(int i = 0; i < 4; i++)
            scanf("%d", &threshold[i]);
        scanf("%d", &C);
        
        for(int i = 0; i < 4; i++)
            enable[i] = (C>>i)&1;
        for(int i = 4; i < 8; i++)
            trigger[i - 4] = (C>>i)&1;
        
        int result[4] = {};
        int now_time = 0, L, R;
        scanf("%d", &K);
        while(K--) {
            scanf("%d %d", &time, &temp);
            L = now_time;
            R = now_time + time;
            if(R < S) {
                
            } else {
                int last_read = R / M * M;
                if(L <= last_read && last_read <= R && last_read >= S) {
                    for(int i = 0; i < 4; i++) {
                        if(trigger[i] == 0) {
                            result[i] |= (temp < threshold[i])&enable[i];
                        } else {
                            result[i] |= (temp > threshold[i])&enable[i];
                        }
                    }
                }
            }
            now_time = R;
        }
        printf("Case %d:", ++cases);
        for(int i = 0; i < 4; i++)
            printf(" %s", result[i] ? "yes" : "no");
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10709 - Intersection is Not that Easy

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
*/
Read More +
解題區/解題區 - UVa

UVa 11585 - Nurikabe

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.

Example Nurikabe

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;
}
Read More +
解題區/解題區 - UVa

UVa 12721 - Cheap B-Subsequence

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 (Pi, Ci), which indicates that if this letter appears in a position X on the subsequence, where X is a multiple of Pi, then the cost of (X/Pi) * Ci 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
*/
Read More +
解題區/解題區 - UVa

UVa 181 - Hearts

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;
}
Read More +
解題區/解題區 - UVa

UVa 1051 - Bipartite Numbers

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
*/
Read More +
解題區/解題區 - UVa

UVa 1030 - Image Is Everything

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
*/
Read More +
解題區/解題區 - UVa

UVa 675 - Convex Hull of the Polygon

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;
}
Read More +
解題區/解題區 - UVa

UVa 11260 - Odd Root Sum

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
*/
Read More +
解題區/解題區 - UVa

UVa 157 - Route Finding

Problem

Many cities provide a comprehensive public transport system, often integrating bus routes, suburban commuter train services and underground railways. Routes on such systems can be categorised according to the stations or stops along them. We conventionally think of them as forming lines (where the vehicle shuttles from one end of the route to the other and returns), loops (where the two ends of the branch are the same and vehicles circle the system in both directions) and connections, where each end of the route connects with another route. Obviously all of these can be thought of as very similar, and can connect with each other at various points along their routes. Note that vehicles can travel in both directions along all routes, and that it is only possible to change between routes at connecting stations.

To simplify matters, each route is given a designation letter from the set A to Z, and each station along a route will be designated by another letter from the set a to z. Connecting stations will have more than one designation. Thus an example could be:

A common problem in such systems is finding a route between two stations. Once this has been done we wish to find the best route, where best means shortest time.

Write a program that will read in details of such a system and then will find the fastest routes between given pairs of stations. You can assume that the trip between stations always takes 1 unit of time and that changing between routes at a connecting station takes 3 units of time.

Input

Input will consist of two parts. The first will consist of a description of a system, the second will consist of pairs of stations. The description will start with a number between 1 and 26 indicating how many routes there are in the system. This will be followed by that many lines, each describing a single route. Each line will start with the route identifier followed by a : followed by the stations along that route, in order. Connections will be indicated by an = sign followed by the complete alternative designation. All connections will be identified at least once, and if there are more than two lines meeting at a connection, some or of all the alternative designations may be identified together. That is, there may be sequences such as ...hc=Bg=Cc=Abd.... If the route forms a loop then the last station will be the same as the first. This is the only situation in which station letters will be repeated. The next portion of the input file will consist of a sequence of lines each containing two stations written contiguously. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each pair of stations in the input. Each line will consist of the time for the fastest route joining the two stations, right justified in a field of width 3, followed by a colon and a space and the sequence of stations representing the shortest journey. Follow the example shown below. Note that there will always be only one fastest route for any given pair of stations and that the route must start and finish at the named stations (not at any synonyms thereof), hence the time for the route must include the time for any inter-station transfers.

The example input below refers to the diagram given above.

Sample input

1
2
3
4
5
6
7
8
9
4
A:fgmpnxzabjd=Dbf
D:b=Adac=Ccf
B:acd=Azefg=Cbh
C:bac
AgAa
AbBh
BhDf
#

Sample output

1
2
3
 5: Agfdjba
 9: Abaz=Bdefgh
10: Bhg=Cbac=Dcf

Solution

題目描述：

這一個交通運輸工具，配置如上圖所述，以大寫字母 (A - Z) 表示哪一種線路，每一條線路上有一些站牌 (a - z)。求某線某站到某線某站的最少花費時間。

然而在同一個線路上，轉換一個站的成本為 1，如果在線路交集站換一條線路走成本為 3。

輸入上比較特別，會用 = 表示交集的站編號，當然有可能會遇到多個線路的站交集在一起。

Dhc=Bg=Cc=Abd 則表示 D 線路上的 Dh-Dc-Dd，其中 Dc, Bg, Cc, Ab 共站。

可以當作雙向連通，如果有環，則會頭尾相同，例如 Dhch。

題目解法：

題目最令人討厭的是，交集站沒有說清楚，也就是說單一線路上的轉運站沒有說清楚，但事實上會被表示在其他線路上，這裡要自己取聯集。

但是做聯集是件挺麻煩的事，因此在求最短路上做點手腳，把狀態表示成 (某線某站, 前一次是否轉運)，這麼做就方便多了。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int trans_node(int r, int a) {
    r -= 'A', a -= 'a';
    return r * 26 + a;
}
void reverse_node(int n, int &r, int &a) {
    r = n /26 + 'A', a = n %26 + 'a';
}
vector<int> g[1024], g2[1024];
void spfa(int st, int ed) {
    int used[1024][2] = {}, dist[1024][2] = {}, prex[1024][2][2];
    for(int i = 0; i < 1024; i++)
        dist[i][0] = dist[i][1] = 0x3f3f3f3f;
    queue<int> Q, S;
    Q.push(st), S.push(0);
    dist[st][0] = 0, prex[st][0][0] = -1;
    while(!Q.empty()) {
        int u = Q.front(), s = S.front();
        Q.pop(), S.pop();
        used[u][s] = 0;
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if(dist[v][0] > dist[u][s] + 1) {
                dist[v][0] = dist[u][s] + 1;
                prex[v][0][0] = u, prex[v][0][1] = s;
                if(!used[v][0]) {
                    used[v][0] = 1, Q.push(v), S.push(0);
                }
            }
        }
        int cost = (s == 1) ? 0 : 3;
        for(int i = 0; i < g2[u].size(); i++) {
            int v = g2[u][i];
            if(dist[v][1] > dist[u][s] + cost) {
                dist[v][1] = dist[u][s] + cost;
                
                if(cost == 0)
                    prex[v][1][0] = prex[u][s][0], prex[v][1][1] = prex[u][s][1];
                else
                    prex[v][1][0] = u, prex[v][1][1] = s;
                if(!used[v][1]) {
                    used[v][1] = 1, Q.push(v), S.push(1);
                }
            }
        }
    }
    printf("%3d: ", min(dist[ed][0], dist[ed][1]));
    
    int r = -1, a = -1, s, mm = ed;
    if(dist[ed][0] <= dist[ed][1])
        s = 0;
    else
        s = 1;
    do {
        int nr, na;
        reverse_node(mm, nr, na);
        if(nr != r) {
            if(mm != ed)	printf("=");
            printf("%c%c", nr, na);
        } else {
            printf("%c", na);
        }
        int om = mm;
        mm = prex[om][s][0], s = prex[om][s][1];
        r = nr, a = na;
    } while(mm != -1);
    puts("");
}
int main() {
    char line[1024];
    for(int n; scanf("%d", &n) == 1;) {
        for(int i = 0; i < 1024; i++)
            g[i].clear(), g2[i].clear();
        while(n--) {
            scanf("%s", &line);
            int r = line[0], preX;
            preX = trans_node(r, line[2]);
            for(int i = 3; line[i]; i++) {
                if(line[i] != '=') {
                    int x = trans_node(r, line[i]);
                    int y = preX;
                    g[x].push_back(y);
                    g[y].push_back(x);
                    preX = x;
                } else {
                    int x = trans_node(line[i+1], line[i+2]);
                    int y = preX;
                    g2[x].push_back(y);
                    g2[y].push_back(x);
                    i += 2;
                }
            }
        }
        while(scanf("%s", line) == 1 && line[0] != '#') {
            int x = trans_node(line[0], line[1]);
            int y = trans_node(line[2], line[3]);
            spfa(y, x);
        }
    }
    return 0;
}
/*
4
A:fgmpnxzabjd=Dbf
D:b=Adac=Ccf
B:acd=Azefg=Cbh
C:bac
AgAa
AbBh
BhDf
#
5 
A:ab=Bbcdefghijk 
B:abc=Ajdef=Cb 
C:ab 
D:cd=Eg 
E:fg=Bf 
AaAk 
AcAk 
AbBb 
BaDd 
# 
*/
Read More +