解題區/解題區 - UVa

UVa 12058 - Highway Monitor

Problem

在 n 個點的高速公路上，需要監視 m 條邊上的情況，監視器只能位於點上，並且可以監控所有與該點相連的邊，費用有限最多只能放置 k 個監視器，找到其中一種使用少於等於 k 個監視器的方法。

Sample Input

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

Sample Output

1
2
Case #1: no
Case #2: yes 1 2 5

Solution

解決最少點集覆蓋所有邊，是一個 NP 問題，雖然這一題已經給定限制搜索必須小於等於 K。

對於 DLX (Dancing Links and Algorithm X) 運用在最少重複覆蓋而言，K 是沒有太大的必要，事實上根據 degree 最大的節點開始窮舉的效果跟 DLX 差不多的。而這一題沒有要求最少，只是請求在範圍內的任一解輸出即可。

DLX 一開始用在精準覆蓋，解決重複覆蓋的效果只能說還算可以，大多的時間都花在計算估價函數，那個啟發式估價是用最簡單的貪心。有時候需要覆蓋的 colume 數量非常多，所以寫法上用 memset 也許是不錯的，但是用懶標記是更為快速。

DLX 的精神在於雙十字鏈表，並且每次找最少可能的 colume 開始窮舉，窮舉時會斷開所有相關在其他 colume 的可能，並在移除掉不需要窮舉的 colume，而在重複覆蓋上則不會移除掉需要窮舉的 colume。

  • 精确覆盖：
    首先选择当前要覆盖的列(含1最少的列)，将该列和能够覆盖到该列的行全部去掉，再枚举添加的方法。枚举某一行r，假设它是解集中的一个，那么该行所能覆盖到的所有列都不必再搜，所以删除该行覆盖到的所有列，又由于去掉的列相当于有解，所以能够覆盖到这些列的行也不用再搜，删之。
  • 重复覆盖：
    首先选择当前要覆盖的列(同上)，将该列删除，枚举覆盖到该列的所有行：对于某一行r，假设它是解集中的一个，那么该行所能覆盖到的列都不必再搜，所以删除该行覆盖到的所有列。注意此时不用删去覆盖到这些列的行，因为一列中允许有多个1。这里有一个A*的优化：估价函数h意义为从当前状态最好情况下需要添加几条边才能覆盖。

這一題會有 n 個 row，每一個 row 會覆蓋第 i 個節點覆蓋哪些邊。因此需要對所有輸入的邊進行編號，也就是 colume 會有 m 個。m 最大 50 萬，窮舉起來相當刺激。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXV 0x3f3f3f3f
#define MAXE 1048576
#define MAXC 1048576
#define MAXR 1024
struct DacingLinks {
    int left, right;
    int up, down;
    int ch, rh;
    int data; // extra info
} DL[MAXE];
int s[MAXC], o[MAXR], head, size, Ans, findflag;
void Remove(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = DL[i].left;
        DL[DL[i].left].right = DL[i].right;
        s[DL[i].ch]--;
    }
}
void Resume(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = i;
        DL[DL[i].left].right = i;
        s[DL[i].ch]++;
    }
}
int used[MAXC] = {};
int H() {
    static int c, ret, i, j, time = 0;
    for(c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
        if(used[c] != time) {
            ret ++, used[c] = time;
            for(i = DL[c].down; i != c; i = DL[i].down)
                for(j = DL[i].right; j != i; j = DL[j].right)
                    used[DL[j].ch] = time;
        }
    }
    return ret;
}
void DFS(int k) {
    if(k + H() >= Ans)    return;
    if(DL[head].right == head) {
        if(k < Ans) {
        	Ans = k, findflag = 1;
            printf("yes");
            for (int i = 0; i < k; i++)
                printf(" %d", DL[o[i]].data);
            puts("");
        }
        return;
    }
    int t = MAXV, c, i, j;
    for(i = DL[head].right; i != head; i = DL[i].right) {
        if(s[i] < t) {
            t = s[i], c = i;
        }
    }
    for(i = DL[c].down; i != c; i = DL[i].down) {
        o[k] = i;
        Remove(i);
        for(j = DL[i].right; j != i; j = DL[j].right)	Remove(j);
        DFS(k+1);
        for(j = DL[i].left; j != i; j = DL[j].left)     Resume(j);
        Resume(i);
        if (findflag)	break;
    }
}
int new_node(int up, int down, int left, int right) {
    assert(size < MAXE);
    DL[size].up = up, DL[size].down = down;
    DL[size].left = left, DL[size].right = right;
    DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
    return size++;
}
void addrow(int n, int Row[], int data) {
    int a, r, row = -1, k;
    for(a = 0; a < n; a++) {
        r = Row[a];
        DL[size].ch = r, s[r]++;
        DL[size].data = data;
        if(row == -1) {
            row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
            DL[row].rh = a;
        }else {
            k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
            DL[k].rh = a;
        }
    }
}
void init(int m) {
    size = 0;
    head = new_node(0, 0, 0, 0);
    int i;
    for(i = 1; i <= m; i++) {
        new_node(i, i, DL[head].left, head);
        DL[i].ch = i, s[i] = 0;
    }
} 
int main() {
    int testcase, cases = 0;
    int n, m, k, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &n, &m, &k);
        vector<int> g[1024];
        for (int i = 1; i <= m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(i);
            g[y].push_back(i);
        }
        assert(m < MAXC);
        init(m);
        int row[1024];
        for (int i = 1; i <= n; i++) {
            sort(g[i].begin(), g[i].end());
            for (int j = 0; j < g[i].size(); j++)
                row[j] = g[i][j];
            addrow(g[i].size(), row, i);
        }
        printf("Case #%d: ", ++cases);
        Ans = k + 1, findflag = 0;
        DFS(0);
        if (Ans == k+1)
            puts("no");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12052 - Cyber cafe

Problem

給一張圖有 N 個節點、M 條邊，其中要放置 S 台新主機於其中 S 個節點，而沒放置的節點繼續使用舊主機，為了服務舊主機的網咖，每個舊節點旁邊最多只能有一個新主機網咖。

請問有多少種放置方法。

Sample Input

1
2
3
4
5
6
7
8
9
10
Dhaka
6 2 7
AB BC CD DE EF FA AD
Chittagong
4 3 4
AB AC AD BC
Sylhet
3 2 3
AB BC CA
TheEnd

Sample Output

1
2
3
4
5
6
7
Dhaka
9
Chittagong
1
Sylhet
0
TheEnd

Solution

對於每一個節點的連接方式用一個 32-bit 壓縮，接著窮舉所有可能放置方法 state，對於沒有放置的節點，直接壓縮結果與 state 做 AND 運算，算 bits 數是否都小於 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    char ss[1024];
    int n, s, p;
    while (scanf("%s", &ss) == 1) {
        printf("%s\n", ss);
        if (!strcmp(ss, "TheEnd"))
            break;
        scanf("%d %d %d", &n, &s, &p);
        int g[26][26] = {};
        for (int i = 0; i < p; i++) {
            scanf("%s", ss);
            int x = ss[0] - 'A', y = ss[1] - 'A';
            g[x][y] = g[y][x] = 1;
        }
        int mask[26] = {};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                mask[i] |= g[i][j]<<j;
        int ret = 0;
        for (int i = (1<<n)-1; i >= 0; i--) {
            if (__builtin_popcount(i) == s) {
                int ok = 1;
                for (int j = 0; j < n && ok; j++) {
                    if ((i>>j)&1)	continue;
                    if (__builtin_popcount(mask[j]&i) >= 2)
                        ok = 0;
                }
                ret += ok;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12051 - Mazes in Higher Dimensions

Problem

好比 2D 方格，從左下角到右上角的方法數。而這一題是在三維空間，一樣的方式要越來越靠近右上方的頂點，但是部分點會有障礙物，會造成無法通行。

題目給定的維度事實上是終點座標，而非該維度數，用 row major 的時候要計算 dim[i]+1。

Sample Input

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

Sample Output

1
2
Case 1: 756756
Case 2: 6318655200

Solution

特地用懶標記完成 dp 計算，但是忘了有可能無法抵達終點，忘了補上最對於終點的懶標記操作，直接輸出 dp[ret] 結果一直噴 WA。

懶標記檢查 if (used[ret] != testcase) dp[ret] = 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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXN 3000005
long long dp[MAXN] = {};
int used[MAXN] = {}, ob[MAXN] = {}; // obstacle
int main() {
    memset(dp, 0, sizeof(dp));
    memset(ob, 0, sizeof(ob));
    memset(used, 0, sizeof(used));
    int n, m, dim[16], row[16], v[16];
    int testcase = 0, cases = 0;
    while (scanf("%d %d", &n, &m) == 2 && n+m) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &dim[i]);
            dim[i]++;
        }
        testcase++;
        row[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--)
            row[i] = row[i+1] * dim[i+1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                scanf("%d", &v[j]);
            int x = 0;
            for (int j = 0; j < n; j++)
                x += v[j] * row[j];
            ob[x] = testcase;
        }
        if(ob[0] == testcase){
            printf("Case %d: 0\n", ++cases);
            continue;
        }
        int ret = 0;
        for (int i = 0; i < n; i++)
            ret += (dim[i] - 1) * row[i];
        queue<int> Q;
        Q.push(0), used[0] = testcase;
        dp[0] = 1;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            long long ways = dp[x];
            for (int i = 0; i < n; i++)
                v[i] = x / row[i], x %= row[i];
            for (int i = 0; i < n; i++) {
                v[i]++;
                if (v[i] < dim[i]) {
                    x = 0;
                    for (int j = 0; j < n; j++)
                        x += v[j] * row[j];
                    if (ob[x] != testcase) {
                        if (used[x] != testcase)
                            dp[x] = 0;
                        dp[x] += ways;
                        if (used[x] != testcase)
                            Q.push(x), used[x] = testcase;
                    }
                }
                v[i]--;
            }
        }
        if (used[ret] != testcase)	dp[ret] = 0;
        printf("Case %d: %lld\n", ++cases, dp[ret]);
    }
    return 0;
}
/*
3 0 
5 5 5
 
3 1 
9 8 7
1 1 1
3 2
9 8 7
1 1 1
5 6 6
3 2
9 8 7
2 3 4
9 8 7
3 2
9 8 7
2 3 4
9 8 7
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 10381 - The Rock

Problem

給定一個 N x M 地圖，已知有部分的牆壁和一個透明的牆壁，每一個障礙物都佔據一個方格，而透明牆壁一開始不知道位於何處，直到碰壁的時候才發現，找一條最慘情況下的最短路徑。

Sample Input

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

Sample Output

1
2
15
11

Solution

最小化最大值，首先窮舉任何一個透明牆壁可能出現的地方，對於透明牆壁的鄰近四格建立再碰壁方向下，抵達終點的最短路徑。

接著，使用最短路的方式進行更新，在這裡使用 dijkstra 的方式，對於每一個點的狀態為 (走到這裡第幾步) = 從起點走到這，最慘的偏移路徑最小化 為何。

概念上理解，設計一條路徑，路徑畫好後，對於每一點賭下一個點就是透明牆壁，偏移路徑長最長為何就會是該路徑的花費。

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 <queue>
#include <assert.h>
#include <algorithm>
using namespace std;
char g[64][64];
int dist[64][64], walldist[64][64][4];
int n, m;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
struct State {
    int x, y;
    int g, h;
    State(int a=0, int b=0, int c=0, int d=0):
        x(a), y(b), g(c), h(d) {}
    bool operator<(const State &a) const {
        return h > a.h;
    }
};
int dp[40][40][40 * 40];
int search(int sx, int sy, int ex, int ey) {
    priority_queue<State> pQ;
    State u, v;
    int tx, ty, h;
    pQ.push(State(sx, sy, 0, 0));
    memset(dp, 63, sizeof(dp));
    while (!pQ.empty()) {
        u = pQ.top(), pQ.pop();
        if (u.h > dp[u.x][u.y][u.g])
            continue;
        if (u.x == ex && u.y == ey)
            return u.h;
        for (int i = 0; i < 4; i++) {
            tx = u.x + dx[i], ty = u.y + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if (g[tx][ty] == '#' || g[tx][ty] == 'E')
                continue;
            if (g[tx][ty] == '.') 
                h = max(u.h, u.g + walldist[u.x][u.y][i]);
            else if (g[tx][ty] == 'X')
                h = max(u.h, u.g);
            assert(u.g + 1 < 40 * 40);
            if (dp[tx][ty][u.g + 1] > h) {
                dp[tx][ty][u.g + 1] = h;
                pQ.push(State(tx, ty, u.g + 1, h));
            }
        }
    }
    return 0;
}
void bfs(int sx, int sy) {
    memset(dist, 63, sizeof(dist));
    queue<int> X, Y;
    int tx, ty;
    X.push(sx), Y.push(sy);
    dist[sx][sy] = 0;
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        for (int i = 0; i < 4; i++) {
            tx = sx + dx[i], ty = sy + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if (g[tx][ty] == '#' || dist[tx][ty] <= dist[sx][sy] + 1)
                continue;
            dist[tx][ty] = dist[sx][sy] + 1;
            X.push(tx), Y.push(ty);
        }
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int sx, sy, ex, ey, tx, ty;
        
        memset(walldist, 0, sizeof(walldist));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'E')	sx = i, sy = j;
                if (g[i][j] == 'X')	ex = i, ey = j;				
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] != '.')
                    continue;
                g[i][j] = '#';
                bfs(ex, ey);
                for (int k = 0; k < 4; k++) {
                    tx = i + dx[k], ty = j + dy[k];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    if (g[tx][ty] == '#')
                        continue;
                    walldist[tx][ty][(k+2)%4] = dist[tx][ty];
                }
                g[i][j] = '.';
            }
        }
        int ret = search(sx, sy, ex, ey);
        printf("%d\n", ret);
    }
    return 0;
}
/*
2
8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
 
3 4
..X.
.##.
.E..
*/
Read More +
解題區/解題區 - UVa

UVa 12853 - The Pony Cart Problem

Problem

現在有一台馬車繞行一個圓，馬車內側輪胎畫出小圓、外側畫出大圓，現在知道馬車內側與外側輪胎之間的距離 D，同時知道內側輪胎每滾一圈，外側輪胎會滾 N 圈，請問外側輪胎畫出來的圓周長為何？

Sample Input

1
2
3
4
3
5.00 2.00
4.20 1.44
8.03 2.01

Sample Output

1
2
3
Case 1: 62.832
Case 2: 86.365
Case 3: 100.40

Solution

感謝峻維兄熱心翻譯

假設內側輪胎畫出小圓半徑為 A，兩個輪胎的半徑 B

$$\frac{ \frac{ 2 \pi A}{2 \pi B} }{ \frac{2 \pi (A + D)}{2 \pi A} } = N \\ \Rightarrow A = \frac{D}{N-1}$$

所求為$2 \pi (A+D)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <math.h>
int main() {
    int testcase, cases = 0;
    const double pi = acos(-1);
    double D, N, A; 
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf %lf", &D, &N);
        A = D / (N - 1);
        double ret = 2 * pi * (A + D);
        printf("Case %d: %.3lf\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12849 - Mother's Jam Puzzle

Problem

有大中小三種類型的果醬瓶在三層的架子上，每一層有不同個數的果醬瓶。但是知道每一層的總果醬體積，反求大中小果醬瓶的容積。

Sample Input

1
2
3
4
5
6
7
2
3 3 1 20.00
6 0 2 20.00
6 4 0 20.00
3 0 1 6.00
0 2 2 10.00
1 3 1 10.00

Sample Output

1
2
Case 1: 1.11 3.33 6.67
Case 2: 1.00 2.00 3.00

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
void gaussianElimination(double mtx[][16], 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++)
        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;
    }
}
int main() {
    int testcase, cases = 0;
    double f[16][16], ret[16];
    int sol[16];
    scanf("%d", &testcase);
    while (testcase--) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 4; j++)
                scanf("%lf", &f[i][j]);
        }
        gaussianElimination(f, 3, ret, sol);
        printf("Case %d: %.2lf %.2lf %.2lf\n", ++cases, ret[0], ret[1], ret[2]);
    }
    return 0;
}
/*
2
3 3 1 20.00
6 0 2 20.00
6 4 0 20.00
3 0 1 6.00
0 2 2 10.00
1 3 1 10.00
*/
Read More +
解題區/解題區 - UVa

UVa 12844 - Outwitting the Weighing Machine

Problem

有五個人要測體重，倆倆上去秤得到體重總和為何，現在反推每個人的體重為多少。

Sample Input

1
2
3
4
3
114 116 118 120 121 122 123 124 125 129
110 111 114 115 118 118 119 122 123 126
180 190 190 196 196 206 216 216 226 232

Sample Output

1
2
3
Case 1: 56 58 60 64 65
Case 2: 53 57 58 61 65
Case 3: 90 90 100 106 126

Solution

這題跟 10202 - Pairsumonious Numbers 一樣。

如果將體重、總和排序後 A[]、SUM[]，保證最小的 A[0] + A[1] = SUM[0]，和 A[0] + A[2] = SUM[1] 但是不曉得 A[0] + A[3] 和 A[1] + A[2] 哪個小，因此窮舉 A[1] + A[2] 的結果。

每一次窮舉，可以解出前三小的值，之後就能依序推出所有結果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
// same 10202 - Pairsumonious Numbers
int main() {
    int n, m, A[50], sum[50];
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	n = 5;
        m = n*(n-1)/2;
        for(int i = 0; i < m; i++)
            scanf("%d", &sum[i]);
        sort(sum, sum+m);
        
        printf("Case %d:", ++cases);
        multiset<int> oRB;
        for(int i = 2; i < m; i++)
            oRB.insert(sum[i]);
        int idx, flag = 0;
        for(int i = 2; i < m; i++) { // A[1]+A[2] = sum[i]
            if((sum[0]+sum[1]+sum[i])%2)
                continue;
            int tmp = (sum[0]+sum[1]+sum[i])/2;
            A[0] = tmp - sum[i];
            A[1] = tmp - sum[1];
            A[2] = tmp - sum[0];
            multiset<int> RB; // copy
            multiset<int>::iterator it;
            RB = oRB;
            it = RB.find(sum[i]);
            RB.erase(it);
            int pass = 1;
            for(int j = 3; j < n; j++) {
                it = RB.begin();// get min
                A[j] = (*it) - A[0];
                RB.erase(it);
                int ok = 1;
                for(int k = 1; k < j; k++) { // delete A[j]+A[0-(j-1)]
                    int tmp = A[j] + A[k];
                    it = RB.find(tmp);
                    if(it == RB.end()) {
                    	ok = 0;
                    	break;
                    }
                    RB.erase(it);
                }
                if(!ok)	{
                	pass = 0;
                    break;
                }
            }
            if(pass) {// output ans
                flag = 1;
                for(int j = 0; j < n; j++)
                    printf(" %d", A[j]);
                puts("");
                break;
            }
        }
        if(!flag)
            puts("Impossible");
    }
    return 0;
}
/*
3
114 116 118 120 121 122 123 124 125 129
110 111 114 115 118 118 119 122 123 126
180 190 190 196 196 206 216 216 226 232
*/
Read More +
解題區/解題區 - UVa

UVa 12842 - The Courier Problem

Problem

軍隊筆直等速度移動，隊伍長度 L，信使位於隊伍最後面，要傳遞訊息到隊伍前方後跑回隊伍末端。跑回末端時候，隊伍已經前進 L 距離。求信使跑的距離為何？

Sample Input

1
2
1
50

Sample Output

1
Case 1: 120.71

Solution

假設軍隊移動速度$v$, 信使移動速度$u$。

看時間

$$\frac{L}{v} = \frac{L}{u-v} + \frac{L}{u+v} \\ u^{2} - v^{2} = 2v, \\ \text{Let u = 1, get } v = \frac{-2 + \sqrt{8} }{2}$$

輸出$\frac{L}{v} u$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <math.h>
int main() {
    int testcase, cases = 0;
    double L;
    double u = 1, v = (-2 + sqrt(8))/ 2.0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf", &L);
        double time = L / v;
        printf("Case %d: %.2lf\n", ++cases, time * u);
    }
    return 0;
}
/*
army v, courier u
time: 
L / v = L / (u - v) + L / (u + v) => u^2 - v^2 = 2v
result L / v * u, let u = 1 => v = (-2 + sqrt(8))/ 2.0.
*/
Read More +
解題區/解題區 - UVa

UVa 12841 - In Puzzleland (III)

Problem

給定一個無向圖，每一個頂點由大寫字母表示，找到從起點到終點，並且經過所有點 (每一個點最多經過一次) 的路徑，輸出最小字典順序的路徑。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
3
12 14
A B C D E F U V W X Y Z
A F
A V
B U
B W
C D
C V
D Y
D W
E X
E Z
F U
F Y
U Z
W X
3 2
A B C
A B
A C
4 5
L N I K
L N
I L
I N
K N
K I

Sample Output

1
2
3
Case 1: AVCDYFUBWXEZ
Case 2: impossible
Case 3: LINK

Solution

一開始想說點數最多才 15，根據 D&C 的作法，拆分成兩塊 (分別有 N/2 個點)，其中一塊從起點開始、另一塊以終點結束的路徑。隨後再把兩塊組合在一起，找字典順序最小即可，看來是測資太多，很容易就 TLE，不過這方法是最穩定的，建表最慘需要 O(2^15 * 7!)。

由於可行狀態太多，也就是好死不死給一張接近完全圖，那上述的算法會超慢，如果要計算方法總數可能才會用到上述解法。而這一題直接 dfs 搜索，並且確保每一步走下去時，剩下的節點會在同一個連通元件上，不會拆分成兩塊。

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector> 
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[26];
char path[32];
int n, m, st, ed, used[26];
int bused[26] = {}, tused = 0;
int bfs(int u, int comp) {
    tused++;
    int cnt = 0, v;
    queue<int> Q;
    Q.push(u), bused[u] = tused;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        cnt++;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (bused[v] != tused && used[v] == 0) {
                bused[v] = tused;
                Q.push(v);
            }
        }
    }
    return cnt == comp;
}
int dfs(int idx, int u) {
    path[idx] = u + 'A';
    if (idx < n - 1 && used[ed])	return 0;
    if (idx == n-1) {
        path[n] = '\0';
        puts(path);
        return 1;
    }
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (used[v] || !bfs(v, n - idx - 1))	
            continue;
        used[v] = 1;
        if(dfs(idx+1, v))	return 1;
        used[v] = 0;
    }
    return 0;
}
int main() {
    int testcase, cases = 0;
    int x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        char name[26][4], s1[4], s2[4], buf[26];
        int mg[26][26] = {};
        for (int i = 0; i < 26; i++)
            g[i].clear();
        for (int i = 0; i < n; i++)
            scanf("%s", name[i]);
        for (int i = 0; i < m; i++) {
            scanf("%s %s", s1, s2);
            x = s1[0] - 'A', y = s2[0] - 'A';
            mg[x][y] = mg[y][x] = 1;
        }
        st = name[0][0] - 'A', ed = name[n-1][0] - 'A';
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                if (mg[i][j])
                    g[i].push_back(j);
            }
        }
        printf("Case %d: ", ++cases);
        memset(used, 0, sizeof(used));
        used[st] = 1;
        int f = dfs(0, st);
        if (!f)	puts("impossible");
    }
    return 0;
}
/*
3
12 14
A B C D E F U V W X Y Z
A F
A V
B U
B W
C D
C V
D Y
D W
E X
E Z
F U
F Y
U Z
W X
3 2
A B C
A B
A C
50
4 5
L N I K
L N
I L
I N
K N
K I
*/
Read More +
解題區/解題區 - UVa

UVa 12109 - Fairies' Defence

Problem

在三維空間中有 N 位仙女，突然間被攻擊者定住，而攻擊者可能在這三維方體中任何一點出現，出現時會攻擊最鄰近的仙女，請問每名仙女被攻擊的機率為何？

Sample Input

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

Sample Output

1
2
Case 1: 0.500 0.500
Case 2: 0.286 0.714

Solution

很明顯地是一個 3D Voronoi，但是要處理 3D Voronoi 還不太行，根據 DJWS 筆記中寫道，應該使用 O(N N log N) 的做法，窮舉一點與其他點之間拉出來的半平面交，計算半平面交的面積佔有多少。

但這一題是 3D 情況，也就是說半空間交，找到凸殼之後計算其體積，因此沒有單純的半平面交這麼簡單。

如何做到半空間交目前沒有想法，但是利用蒙地卡羅算機率還算可行，每一筆測資限制窮舉次數在 800 萬內即可通過。

由於 N 很小，也想過窮舉一點之後，拉出半空間的所有情況，任三面交一點，若該點在半空間中都符合，則保留於後面處理。得到所有點集，拿來做三維凸包，之後計算體積。關於三維凸包 (凸殼) 計算體積，內部戳一點，對於所有面會形成錐體，把所有錐體體積加總即可。

也許 DJWS 的作法是正確的，但是目前不知道如何做到半空間交。不知道要怎麼繞行算法。

關於 2D 的題目，請參考 zerojudge b358. 竹馬不敵天降

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
double mrandom() {
    int r = rand();
    return (double) r / RAND_MAX;
}
int main() {
    int n, a, b, c;
    int cases = 0;
    int x[32], y[32], z[32];
    while (scanf("%d", &n) == 1 && n) {
        scanf("%d %d %d", &a, &b, &c);
        const int runtime = 8000000;
        for (int i = 0; i < n; i++)
            scanf("%d %d %d", &x[i], &y[i], &z[i]);
        int count[32] = {}, guess = runtime / n;
        double tx, ty, tz;
        for (int i = guess - 1; i >= 0; i--) {
            tx = mrandom() * a, ty = mrandom() * b, tz = mrandom() * c;
            double dist = 1e+60, tmp;
            int mn = 0;
            for (int j = 0; j < n; j++) {
                tmp = (tx - x[j]) * (tx - x[j]) + (ty - y[j]) * (ty - y[j]) + 
                            (tz - z[j]) * (tz - z[j]);
                if (tmp < dist)
                    dist = tmp, mn = j;
            }
            count[mn]++;
        }
        printf("Case %d:", ++cases);
        for (int i = 0; i < n; i++)
            printf(" %.3lf", (double) count[i] / guess);
        puts("");		
    }
    return 0;
}
Read More +