解題區/解題區 - UVa

UVa 918 - ASCII Mandelbrot

Problem

根據題目意思，Z = 0 + 0i 開始，窮舉給定區間內的複數 C = a + bi，迭代 Z = Z * Z + C，迭代多少次使得 |Z| > 2，迭代次數將會由給定的字串依序塗色。

Sample Input

1
2
3
2
"#$&/|[]+;:-." -1.2 1.2 0.1 -2 1 0.05
"1234567890AB" -1.2 -0.8 0.02 -0.5 0.5 0.02

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
########$$$$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&$$$$$$$$$$$$$$$$$$
#######$$$$$$$&&&&&&&&&&&&&&&&/////| +||///&&&&$$$$$$$$$$$$$$
######$$$$$&&&&&&&&&&&&&&&&//////||[]-;- |////&&&&$$$$$$$$$$$
#####$$$&&&&&&&&&&&&&&&&///////|||[+;  -+[||////&&&&&$$$$$$$$
####$$&&&&&&&&&&&&&&&&///////||[[]+      +[||||//&&&&&&$$$$$$
###$$&&&&&&&&&&&&&&//////||[]++++;:      :;+[[[ |//&&&&&$$$$$
##$$&&&&&&&&&&&&&////||||[[].               .    |/&&&&&&$$$$
##$&&&&&&&&&&&//|||||||[[[+ .                   ][|/&&&&&&$$$
#$&&&&&&&///||].]]]]]]]]]+-                     ; |//&&&&&&$$
#&&&//////|||[]:  .   -;;-                       +[//&&&&&&&$
#&//////||||[]+-                                 ]|///&&&&&&$
#/////[[[[]+.                                   +[|///&&&&&&$
                                              .+][|///&&&&&&&
#/////[[[[]+.                                   +[|///&&&&&&$
#&//////||||[]+-                                 ]|///&&&&&&$
#&&&//////|||[]:  .   -;;-                       +[//&&&&&&&$
#$&&&&&&&///||].]]]]]]]]]+-                     ; |//&&&&&&$$
##$&&&&&&&&&&&//|||||||[[[+ .                   ][|/&&&&&&$$$
##$$&&&&&&&&&&&&&////||||[[].               .    |/&&&&&&$$$$
###$$&&&&&&&&&&&&&&//////||[]++++;:      :;+[[[ |//&&&&&$$$$$
####$$&&&&&&&&&&&&&&&&///////||[[]+      +[||||//&&&&&&$$$$$$
#####$$$&&&&&&&&&&&&&&&&///////|||[+;  -+[||////&&&&&$$$$$$$$
######$$$$$&&&&&&&&&&&&&&&&//////||[]-;- |////&&&&$$$$$$$$$$$
#######$$$$$$$&&&&&&&&&&&&&&&&/////| +||///&&&&$$$$$$$$$$$$$$
########$$$$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&$$$$$$$$$$$$$$$$$$
333333333333333333333333333333333222222222222222222
333333333333334444433333333333333332222222222222222
333333334444444444444444433333333333322222222222222
333334444444445555555444444433333333333222222222222
334444444444558866555554444444433333333332222222222
444444444445567 9B755555444444444333333333322222222
4444444444555678B9766555544444444433333333332222222
4444444445555668A0866666554444444444333333333322222
44444444555556670 A87667765444444444433333333332222
4444444555556667   08778A75544444444443333333333322
444444555555666790  99AA  6554444444444333333333332
444444555555667889  B   A76654444444444433333333333
444445555555677889A   A9876655444444444443333333333
444455555556677880A  B09876655544444444444333333333
44455555556677889A    A9877655554444444444433333333
4455555556677899       9887665555544444444443333333
4555555566789 0AB      0988765555554444444444333333
555555566680B          AAB 866555555444444444433333
5555566667A               B876555555554444444433333
55566666789AB              A76655555555444444443333
566666677880B             B977665555555554444444333

Solution

何等兇殘的題目，以前不少 testdata 是用 float 混用 double 產出來的結果，亦或者是輸出轉 float，各種神祕的方式才能恰好符號原本測資的誤差。
砸了許多混用方式才將那殘害世人的題目解決
－想到之前不少 float 拯救世界。

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
// 918 - ASCII Mandelbrot
// WTF for testdata, I used + 0.00000001f to pass it.
#include <stdio.h> 
#include <math.h>
int main() {
    int testcase;
    double MINI, MAXI, MINR, MAXR, PRECI, PRECR;
    char CHARS[128];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%s %lf %lf %lf %lf %lf %lf", CHARS, &MINI, &MAXI, &PRECI, &MINR, &MAXR, &PRECR);
        CHARS[0] = CHARS[13] = ' ';
        for(double a = MINI; a <= MAXI + 0.00000001f; a += PRECI) {
            for(double b = MINR; b <= MAXR + 0.00000001f; b += PRECR) {
                float za = 0, zb = 0, ca = b, cb = a, ta, tb;
                int i;
                for(i = 0; i < 12; i++) {	
                    ta = za * za - zb * zb;
                    tb = 2 * za * zb;
                    za = ta + ca, zb = tb + cb;
                    if(za * za + zb * zb > 4)
                        break;
                }
                printf("%c", CHARS[i+1]);
            }
            puts("");
        }
        if(testcase)
            puts("");
    }
    return 0;
}
/*
2
"#$&/|[]+;:-." -1.2 1.2 0.1 -2 1 0.05
"1234567890AB" -1.2 -0.8 0.02 -0.5 0.5 0.02
*/
Read More +
解題區/解題區 - UVa

UVa 915 - Stack of Cylinders

Problem

根據順序依據擺放半徑為 r 的圓，求最後的總長，以及從端點開始碰壁到另外一端所有圓編號，保證不會有三個圓相互接觸。

Sample Input

1
2
3
4
5
6
7
8
7
3
25
35
5
4
32
4

Sample Output

1
2
3
4
5
183.1
3
2
3
6

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n, cases = 0;
    while(scanf("%d", &n) == 1) {
        if(cases++)	puts("");
        double radius[128], posX[128];
        for(int i = 1; i <= n; i++)
            scanf("%lf", &radius[i]);
            
        double mx = 0;
        int prev[128] = {}, tail = 0;
        for(int i = 1; i <= n; i++) {
            double x = radius[i];
            for(int j = 1; j < i; j++) {
                double nx = sqrt(pow(radius[i]+radius[j], 2) - pow(radius[i]-radius[j], 2)) + posX[j];
                if(nx > x) 
                    prev[i] = j;
                x = max(x, nx);
//				printf("sqrt = %lf\n", pow(radius[i]+radius[j], 2) - pow(radius[i]-radius[j], 2));
            }
//			printf("prev[%d] %d\n", i, prev[i]);
            posX[i] = x;
            if(posX[i] + radius[i] > mx)
                tail = i;
            mx = max(mx, posX[i] + radius[i]);
        }
        printf("%.1lf\n", mx);
        vector<int> ret;
        while(tail) {
            ret.push_back(tail);
            tail = prev[tail];
        }
        printf("%d\n", ret.size());
        for(int i = ret.size() - 1; i >= 0; i--)
            printf("%d\n", ret[i]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 909 - The BitPack Data Compression Problem

Problem

解壓縮方式

1
2
3
4
5
6
7
8
While (there is input)
   n <-- read next byte
   If (0<= n <= 127)
       copy the next n+1 bytes to the output as they are
   Else If (129<= n <=255)
       copy the next byte n-128+1 times to the output
   Else If n=128
       do nothing

找到用最少 bytes 的壓縮結果。每組測資只會有一筆，並且以 EOF 結尾。

範例輸出用 [ddd] 表示不可視的字符或者是可視字符都有可能，但是實際輸出直接輸出該數值的 bytes 而非以 [] 表示的字串。

Sample Input 1

1
aaaaaaaarstqahbbbbbbb

Sample Output 1

1
[135]a[5]rstqah[134]b

Sample Input 2

1
aaaaaaaaaa

Sample Output 2

1
[137]a

Sample Input 3

1
abcdefghij

Sample Output 3

1
[9]abcdefghij

Solution

討論區一而三在而三的更正解答，最後要說明的是，你們最後的答案還是錯的！此外，測試資料輸入輸出都有不可視字符是哪招，明明說一行一筆測資，以為都是可視 …
－最後討論時間為 13 年前

dp[i] 表示從 [0, i] 壓縮的最少 bytes 數量，最後使用回溯找其中一解 (任何一解都可以)。

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
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int dp[65536], ardp[65536], from[65536], n, bb;
char s[65536];
void travel(int i) {
    if(i == 0)	return;
    if(ardp[i] >= 129) {
        travel(from[i]);
        printf("%c%c", ardp[i], s[i]), bb += 2;
    } else {
        travel(from[i]);
        printf("%c", ardp[i]), bb++;
        for(int j = ardp[i]; j >= 0; j--)
            printf("%c", s[i - j]), bb++;
    }
}
int main() {
    int idx = 1;
    char c;
    while((c = getchar()) != EOF)
        s[idx++] = c;
    {
        n = strlen(s+1);
        assert(n < 65536);
        memset(dp, 63, sizeof(dp));
        dp[0] = 0;
        for(int i = 0; i <= n; i++) {
            int cnt = 0;
            for(int j = i+1; j <= n; j++) {
                if(s[j] == s[i+1]) {
                    cnt++;
                    if(cnt + 127 > 255)
                        break;
                    if(cnt >= 2) {
                        if(dp[j] > dp[i] + 2)
                            ardp[j] = cnt + 127, from[j] = i;
                        dp[j] = min(dp[j], dp[i] + 2);
                    }
                } else
                    break;
            }
            cnt = 0;
            for(int j = i+1; j <= n; j++) {
                cnt++;
                if(cnt - 1 > 127)	break;
                if(dp[j] > dp[i] + cnt + 1)
                    ardp[j] = cnt - 1, from[j] = i;
                dp[j] = min(dp[j], dp[i] + cnt + 1);
            }
        }
        bb = 0;
        travel(n);
//		printf("bytes %d\n", bb);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 298 - Race Tracks

Problem

給定一個 N * M 的地圖，接著將會從起點出發抵達終點，一開始的速度為 (0, 0)，在下一個時刻，每一個維度的速度可以調整 -3, -2, -1, 0, 1, 2, 3 (也就是加速度)，但是速度的絕對值必須小於等於 3，同時給定這張地圖的矩形障礙物，移動的過程中不用考慮會不會遇到障礙物，只需要考慮跳躍落下的地點是否有障礙物。

Sample input

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

Sample output

1
2
Optimal solution takes 7 hops.
No solution.

Solution

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
#include <stdio.h> 
#include <queue>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int g[64][64];
int testcase, N, M, P;
int sx, sy, ex, ey;
void bfs() {
    int dp[64][64][8][8] = {};
    queue<int> X, Y, VX, VY;
    int x, y, vx, vy, tx, ty, dx, dy;
    dp[sx][sy][0+3][0+3] = 1;
    X.push(sx), Y.push(sy), VX.push(0), VY.push(0);
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        vx = VX.front(), VX.pop();
        vy = VY.front(), VY.pop();
        if(x == ex && y == ey) {
            printf("Optimal solution takes %d hops.\n", dp[x][y][vx+3][vy+3]-1);
            return;
        }
        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
                dx = vx + i, dy = vy + j;
                if(abs(dx) <= 3 && abs(dy) <= 3) {
                    tx = x + dx, ty = y + dy;
                    if(tx < 0 || tx >= N || ty < 0 || ty >= M || dp[tx][ty][dx+3][dy+3])
                        continue;
                    if(g[tx][ty])
                        continue;
                    dp[tx][ty][dx+3][dy+3] = dp[x][y][vx+3][vy+3] + 1;
                    X.push(tx), Y.push(ty);
                    VX.push(dx), VY.push(dy);
                } 
            }
        }
    }
    puts("No solution.");
}
int main() {
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &N, &M);
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        scanf("%d", &P);
        memset(g, 0, sizeof(g));
        for(int i = 0; i < P; i++) {
            int lx, ly, rx, ry;
            scanf("%d %d %d %d", &lx, &rx, &ly, &ry);
            for(int p = lx; p <= rx; p++)
                for(int q = ly; q <= ry; q++)
                    g[p][q] = 1;
        }
        bfs();
    }
    return 0;
}

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

UVa 268 - Double Trouble

Problem

在一個 B 進制數中，找到一個最小的數字 X，使得 2 * X 的結果恰好是 X 循環右移一位的結果 (意即最末位的數字推到首位，其餘往右推一位)。

例如範例給的

1
2
 X = 421052631578947368 
2X = 842105263157894736

末尾的 8 移動到首位，其餘往右推一位。

Sample Input

1
2
3
2
10
35

Sample Output

1
2
3
4
5
6
For base 2 the double-trouble number is
0 1
For base 10 the double-trouble number is
0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1
For base 35 the double-trouble number is
11 23

Solution

假設末位數字是 M，且 M 的數值一定介於 $0 <= M < B$，最後根據公式推

$$2*(NM) = MN, 0 \le M < B \\ 2(N * B + M) = N + B^{(k-1)} * M \\ N = M * \frac{(B^{(k-1)} - 2)}{(2 * B - 1)}$$

從位數少開始窮舉，再依序從 M 小的開始窮舉，找到可以整除的整數 N 值，做一次小整數的大數乘除法即可，並不會太難。

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
#include <stdio.h>
/* 
2*(NM) = MN, 0 <= M < B
2(N * B + M) = N + B^(k-1) * M
N = M * (B^(k-1) - 2)/(2 * B - 1)
*/
int main() {
    int B;
    while(scanf("%d", &B) == 1) {
        printf("For base %d the double-trouble number is\n", B);
        
        int d, product = 1, M;
        for(int k = 1; k < 1024; k++) {
            int ok = 0;
            for(M = 1; M < B; M++) {
                if((M * (product - 2))%(2 * B - 1) == 0) {
                    ok = 1, d = k;
                    break;
                }
            }
            if(ok)	break;
            product = (product * B)%(2 * B - 1);
        }
        
        int N[1024] = {};
        N[d - 1] = 1;
        for(int i = 0, carry = -2; i <= d; i++) {
            N[i] += carry;
            if(N[i] < 0) {
                N[i] += B, carry = -1;
            } else {
                break;
            }
        }
        
        for(int i = 0; i <= d; i++)
            N[i] *= M;
        for(int i = 0; i <= d; i++)
            N[i+1] += N[i]/B, N[i] %= B;
        for(int i = d, j = 0; i >= 0; i--) {
            j = j * B + N[i];
            N[i] = j / (2 * B - 1), j %= (2 * B - 1);
        }
        for(int i = d-2; i >= 0; i--)
            printf("%d ", N[i]);
        printf("%d \n", M);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 250 - Pattern Matching Prelims

Problem

對於一個 N * M 的灰階矩陣，找一個重心$(c_{x}, c_{y})$，重心會符合將
$$|column[0, c_{x}-1] - column[c_{x}+1, N-1]| \\ |row[0, c_{y}-1] - row[c_{y}+1, M-1]|$$

最小化, 其中 column, row 表示該列、該行的總和。如果有數個相同，則盡可能輸出最右小角的座標 (座標值越大越好)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 5
0.1 0.2 0.1 0.2 0.1
0.1 0.2 0.3 0.1 0.1
0.2 0.3 0.1 0.1 0.3
0.4 0.1 0.1 0.1 0.2
0.2 0.2 0.3 0.3 0.1
5 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2
0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3
0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.6
0 0

Sample Output

1
2
Case 1: center at (3, 3)
Case 2: center at (4, 6)

Solution

其實會發現 x 軸、y 軸的結果可以分開計算，是不會影響最後的結果，兩別分別取最佳的位置即可。

而為了求這個值，累計每一行、列的總和，使用 O(n) 掃描計算即可。參照代碼。

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
#include <stdio.h>
#include <math.h>
int main() {
#define eps 1e-6
    int n, m, cases = 0;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        double row[128] = {}, col[128] = {};
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                double x;
                scanf("%lf", &x);
                row[i] += x, col[j] += x;
            }
        }
        double left = 0, right = 0;
        double diff = 1e+30;
        int cx, cy;
        for(int i = 1; i < n; i++)
            right += row[i];
        for(int i = 0; i < n; i++) {
            if(fabs(right - left) < diff + eps) {
                diff = fabs(right - left);
                cx = i;
            }
            left += row[i], right -= row[i+1];
        }
        left = right = 0;
        diff = 1e+30;
        for(int i = 1; i < m; i++)
            right += col[i];
        for(int i = 0; i < m; i++) {
            if(fabs(right - left) < diff + eps) {
                diff = fabs(right - left);
                cy = i;
            }
            left += col[i], right -= col[i+1];
        }
        printf("Case %d: center at (%d, %d)\n", ++cases, cx+1, cy+1);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 239 - Tempus et mobilius. Time and motion

Problem

有一個神秘的球時鐘，球時鐘會有三個堆疊位置，分別是存放每分鐘、每五分鐘、每一個小時的球球，軌道每一分鐘會將一個球釋出，並且滾入位置，放置的位置優先順序為每分鐘、每五分鐘、每小時。

如果滾入的位置分別滿了 5, 12, 12 個球，則該位置的球將會按照原本進入順序的反順序放入軌道隊列的最晚端。在剛好滿的那個瞬間，那個球將會到次優先的位置去。

假使球有各自的編號，請問在第幾天的同一個時刻後，會回到原本的位置。

Sample Input

1
2
3
30
45
0

Sample Output

1
2
30 balls cycle after 15 days.
45 balls cycle after 378 days.

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
#include <stdio.h> 
#include <stack>
#include <queue>
using namespace std;
long long gcd(long long x, long long y) {
    for(long long t; x%y; t = x, x = y, y = t%y);
    return y;
}
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        // simulation
        queue<int> Q;
        stack<int> minute, five, hour;
        for(int i = 0; i < n; i++)
            Q.push(i);
        for(int i = 0; i < 24 * 60; i++) {
            int x = Q.front();
            Q.pop();
            if(minute.size() < 4) {
                minute.push(x);
            } else {
                while(!minute.empty())
                    Q.push(minute.top()), minute.pop();
                if(five.size() < 11)
                    five.push(x);
                else {
                    while(!five.empty())
                        Q.push(five.top()), five.pop();
                    if(hour.size() < 11)
                        hour.push(x);
                    else {
                        while(!hour.empty())
                            Q.push(hour.top()), hour.pop();
                        Q.push(x);
                    }
                }
            }
        }
        
        // permutation group
        int M[8192], visited[8192] = {};
        for(int i = 0; i < n; i++)
            M[i] = Q.front(), Q.pop();
        long long ret = 1;
        for(int i = 0; i < n; i++) {
            if(visited[i] == 0) {
                int j, len = 1;
                visited[i] = 1;
                for(j = M[i]; j != i; j = M[j]) {
                    visited[j] = 1, len++;
                }
                ret = ret / gcd(ret, len) * len;
            }
        }
        printf("%d balls cycle after %lld days.\n", n, ret);  
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 221 - Urban Elevations

Problem

給定一個三維空間建築物配置，給予每一個建築物西南方的端點，以及距離的深度，面向的建築物寬度和高度。求從南面往北面看過去，有多少建築物是可以被看到一部分的？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
14
160 0 30 60 30
125 0 32 28 60
95 0 27 28 40
70 35 19 55 90
0 0 60 35 80
0 40 29 20 60
35 40 25 45 80
0 67 25 20 50
0 92 90 20 80
95 38 55 12 50
95 60 60 13 30
95 80 45 25 50
165 65 15 15 25
165 85 10 15 35
0

Sample Output

1
2
For map #1, the visible buildings are numbered as follows:
5 9 4 3 10 2 1 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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Building {
    int x, y;
    int width, depth, height, label;
    int in() {
        return scanf("%d %d %d %d %d", &x, &y, &width, &depth, &height) == 5;
    }
    bool operator<(const Building &a) const {
        if(make_pair(x, y) != make_pair(a.x, a.y))
            return make_pair(x, y) < make_pair(a.x, a.y);
        return depth < a.depth;
    }
}; 
int coverL(vector< pair<int, int> > interval, int l, int r) {
    sort(interval.begin(), interval.end());
    int y = l;
    for(int i = 0; i < interval.size(); i++) {
        if(interval[i].first <= y)
            y = max(y, interval[i].second);
        else
            return 0;
    }
    return y >= r;
}
void solve(Building D[], int n) {
    sort(D, D+n);
    int f = 0;
    for(int i = 0; i < n; i++) {
        vector< pair<int, int> > interval;
        for(int j = 0; j < n; j++) {
            if(j == i)	continue;
            if(D[i].height > D[j].height || D[i].y <= D[j].y)
                continue;
            int l = max(D[i].x, D[j].x), r = min(D[i].x+D[i].width, D[j].x+D[j].width);
            if(l < r)
                interval.push_back(make_pair(l, r));
        }
        if(!coverL(interval, D[i].x, D[i].x + D[i].width)) {
            if(f++)	putchar(' ');
            printf("%d", D[i].label + 1);
        }
    }
    puts("");
}
int main() {
    int n, cases = 0;
    Building D[128];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++)
            D[i].in(), D[i].label = i;
        if(cases++)	puts("");
        printf("For map #%d, the visible buildings are numbered as follows:\n", cases);
        solve(D, n);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 215 - Spreadsheet Calculator

Problem

給一張 N * M 的試算表，並且給定每一格的值可以倚靠其他欄位的結果。是否存在循環依賴？如果不存在則將每一格的答案計算出，否則將輸出存有循環依賴上的所有格子情形。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0

Sample Output

1
2
3
4
5
6
7
      0     1
A     3     5
B     3    -2
A0: A0
B0: C1
C1: B0+A1

Solution

其實就最簡單就是利用高斯消去找解，但是測資中最討厭的地方在於假使 A0 = A0-A0 這種情況也要算依賴關係，那麼高斯消去仍然找得到所有變數的解。

所以最後還是弄一個 dfs 找是否會抵達環上任何一點。

如果將這些資訊排除，圖就是一個 DAG，不用高斯消去也是相當容易的模擬計算。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
void gaussianElimination(double mtx[][256], int n, double sol[], int nosol[]) {
#define eps 1e-6
    int i, j;		
    for(i = 0; i < n; i++) {
        int k = i;
        for(j = i; j < n; j++)
            if(fabs(mtx[k][i]) < fabs(mtx[j][i]))
                k = j;
        if(fabs(mtx[k][i]) < eps)
            continue;
        if(k != i) {
            for(j = 0; j <= n; j++)
                swap(mtx[k][j], mtx[i][j]);
        }
        for(j = 0; j < n; j++) {
            if(i == j)  continue;
            for(k = n; k >= i; k--) {
                mtx[j][k] -= mtx[j][i]/mtx[i][i]*mtx[i][k];
            }
        }
    }	
//	for(int i = 0; i < n; i++) {
//		for(int j = 0; j <= n; j++)
//			printf("%lf ", mtx[i][j]);
//		puts("");
//	}
    for(int i = 0; i < n; i++)
    	nosol[i] = 0;
    for(i = n-1; i >= 0; i--) {
        if(fabs(mtx[i][i]) < eps)
            nosol[i] = 1;
        else {
            if(fabs(mtx[i][n]) < eps)
                sol[i] = 0;
            else
                sol[i] = mtx[i][n]/mtx[i][i];
        }
        for(j = i+1; j < n; j++)
            if(fabs(mtx[i][j]) > eps && nosol[j])
                nosol[i] = 1;
    }
}
vector<int> depend[512];
int visited[512], in_stk[512];
int dfs(int u, int p) {
    visited[u] = 1, in_stk[u] = 1; 
    for(int i = 0; i < depend[u].size(); i++) {
        int v = depend[u][i];
        if(in_stk[v])	return 1;
        if(visited[v] == 0 && dfs(v, u))
            return 1;
    }
    in_stk[u] = 0;
    return 0;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int N, M;
    char s[1025], exp[32][32][128];
    while(scanf("%d %d", &N, &M) == 2 && N+M) {
        while(getchar() != '\n');
        
        int notsolvable[256];
        double f[256][256] = {}, value[256];
        
        for(int i = 0; i < N * M; i++) {
            depend[i].clear();
        }
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                scanf("%s", s);
                strcpy(exp[i][j], s);
                int sign = 1;
                f[i * M + j][i * M + j] = 1;
                for(int k = 0; s[k]; k++) {
                    if(s[k] == '+')			sign = 1;
                    else if(s[k] == '-')	sign = -1;
                    else if('0' <= s[k] && s[k] <= '9') {
                        int num = 0;
                        while('0' <= s[k] && s[k] <= '9')
                            num = num * 10 + s[k] - '0', k++;
                        k--;
                        f[i * M + j][N * M] += sign * num;
                    } else {
                        int rol = s[k] - 'A', num = 0;
                        k++;
                        while('0' <= s[k] && s[k] <= '9')
                            num = num * 10 + s[k] - '0', k++;
                        k--;
                        f[i * M + j][rol * M + num] -= sign;
                        depend[i * M + j].push_back(rol * M + num);
                    }
                }
            }
        }
        gaussianElimination(f, N*M, value, notsolvable);
        for(int i = 0; i < N*M; i++) {
            memset(visited, 0, sizeof(visited));
            memset(in_stk, 0, sizeof(in_stk));
            notsolvable[i] |= dfs(i, i);
        }
        int allsol = 1;
        for(int i = 0; i < N*M; i++) {
//			printf("%lf %d\n", value[i], notsolvable[i]);
            allsol &= !notsolvable[i];
        }
        if(allsol) {
            printf(" ");
            for(int i = 0; i < M; i++)
                printf("%6d", i);
            puts("");
            for(int i = 0; i < N; i++) {
                printf("%c", i + 'A');
                for(int j = 0; j < M; j++)
                    printf("%6d", (int)value[i * M +j]);
                puts("");
            }
        } else {
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {
                    if(notsolvable[i * M + j]) {
                        printf("%c%d: %s\n", i + 'A', j, exp[i][j]);
                    }
                }
            }
        }
        puts("");
    } 
    return 0;
}
/*
2 2
A1+B1
5
3
B0-A1
3 2
A0
5
C1
7
A1+B1
B0+A1
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 11871 - New Land

Problem

題目給定在 n * m 的格子中，以及一些障礙物，求一個最大空白矩形。

Sample Input

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

Sample Output

1
2
Case 1: 12
Case 2: 3

Solution

帶入單調堆。

線性時間 O(NM) 完成。紀錄每一列的向左拓展最寬為何，然後對於每一列(假設它是矩形的最右側的邊上)找到最大矩形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
#define maxL ((2048*2048)>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
// http://mypaper.pchome.com.tw/zerojudge/post/1326159411
int solve(int n, int h[]) {
    int ret = 0;
    int i, height;
    stack< pair<int, int> > stk;// <height, position>
    pair<int, int> e;
    stk.push(make_pair(-1, 0));
    h[n] = 0;// visual height.
    for(i = 0; i <= n; i++) {
        height = h[i];
        e = make_pair(height, i);
        while(height < stk.top().first) {
            e = stk.top(), stk.pop();
            ret = max(ret, (i - e.second) * e.first);
        }
        if(height > stk.top().first)
            stk.push(make_pair(height, e.second));
    }
    return ret;
}    
int n, m, h[2048];
int main() {
    int k, c, x, cases = 0, testcase;
    ReadInt(&testcase);
    while(testcase--) {
    	ReadInt(&n);
    	ReadInt(&m);
    	memset(mark, 0, sizeof(mark));
    	memset(h, 0, sizeof(h));
        for(int i = 0; i < n; i++) {
        	ReadInt(&k);
        	ReadInt(&c);
        	int pos = 0;
            for(int j = 0; j < k; j++) {
            	ReadInt(&x);
                c = !c;
                if(c) {
            		while(x--)
            			SET(i * 2048 + pos), pos++;
            	} else {
            		pos += x;
            	}
            }
        }
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
            	if(GET(j * 2048 + i))
            		h[j]++;
            	else
            		h[j] = 0;
            }
            ret = max(ret, solve(n, h));
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +