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

UVa 11931 - Maze Escape

Problem

類似倉庫番遊戲，必須將箱子推到指定的按鈕位置，才會開啟逃離門，每一次可以走一步，如果箱子在旁邊，則人與箱子會同時往同一個方向移動。求逃離最少步數。

在還沒有打開門之前，門就相當於障礙物存在，不能經過。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0

Sample Output

1
2
No Way!
20

Solution

反例輸出有誤，把 No Way! 拆成兩行送出結果拿到 WA。

把人的位置和箱子位置記錄成一個狀態，得到 dist[sx][sy][bx][by] 進行 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
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int sx, sy, ex, ey, bx, by, cx, cy;
int n, m;
char g[32][32];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int dist[25][25][25][25];
int bfs() {
    memset(dist, 0, sizeof(dist));
    dist[sx][sy][bx][by] = 1;
    queue<int> X, Y, BX, BY;
    int x, y, tx, ty, ttx, tty;
    X.push(sx), Y.push(sy), BX.push(bx), BY.push(by);
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        bx = BX.front(), BX.pop();
        by = BY.front(), BY.pop();
        int step = dist[x][y][bx][by];
        for (int i = 0; i < 4; i++) {
            tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if (g[tx][ty] == 'd' && g[bx][by] == 'b')
                return step;
            if (g[tx][ty] == '#' || g[tx][ty] == 'd')
                continue;
            if (tx == bx && ty == by) { // push it
                ttx = tx + dx[i], tty = ty + dy[i];
                if (ttx < 0 || tty < 0 || ttx >= n || tty >= m)
                    continue;
                if (g[ttx][tty] == '#' || g[ttx][tty] == 'd')
                    continue;
                if (dist[tx][ty][ttx][tty] == 0) {
                    dist[tx][ty][ttx][tty] = step + 1;
                    X.push(tx), Y.push(ty), BX.push(ttx), BY.push(tty);
                }
            } else {
                if (dist[tx][ty][bx][by] == 0) {
                    dist[tx][ty][bx][by] = step + 1;
                    X.push(tx), Y.push(ty), BX.push(bx), BY.push(by);
                }
            }
        }
    }
    return -1;
}
int main() {
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '@')
                    sx = i, sy = j;
                if (g[i][j] == 'd')
                    ex = i, ey = j;
                if (g[i][j] == 'x')
                    bx = i, by = j;
                if (g[i][j] == 'b')
                    cx = i, cy = j;
            }
        }
        int ret = bfs();
        if (ret < 0)	
            puts("No Way!");
        else
            printf("%d\n", ret);
    }
    return 0;
}
/*
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 11669 - Non Decreasing Prime Sequence

Problem

每一個數字可以做質因數分解，找尋區間 [l, r] 所有數字質因數分解後，字典順序第 k 小的結果。

字典順序先按照集合個數由小到大，相同時才按照一般字典順序排序。

Sample Input

1
2
3
4
3
2 10 1
2 10 5
2 10 9

Sample Output

1
2
3
Case 1: 2
Case 2: 2 2
Case 3: 2 2 2

Solution

首先必須建質數表，之後利用 dfs 搜索出字典順序的結果，特別小心 overflow 的計算，必須使用 long long 防止在 1000000 以內的數字相乘溢位。

之後可以得到每一個數字質因數分解之後的排序結果 rank[i] = number, arank[number] = i。

然而每一組詢問，相當於在 arank 中查找 [l, r] 的第 k 小數字為何，輸出其 number 的結果。

套用區間第 k 大的解法，在離線情況下 (不更動元素)，按照順序插入 rank[number]，在 O(n log n) 時間內建表，消耗 O(n log n) 空間，在 O(log n) 回答。

在回答方面比歸併樹或者是塊狀鏈表快很多，可惜的是空間消耗相當驚人。

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

為了找到區間 K 大，使用函數式線段樹有點類似於掃描線算法，對於某個時間點依序將數字放進去，然後對於區間查詢 K 大的時候，相當於對某個時間點之間作減法運算。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
struct Node {
    int l, r, lson, rson;
    int sum;
} node[1048576 * 23];
int nodesize = 0;
int root[1048576];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].l = l, node[k].r = r, node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    node[k].sum += val;
    if (node[k].l == node[k].r) return k;
    int m = (node[k].l + node[k].r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, x, val);
    else
        node[k].rson = change(node[p].rson, x, val);
    return k;
}
int query(int tp, int tq, int k) {
    if (node[tp].l == node[tp].r)
        return node[tp].l;
    int t = node[node[tp].lson].sum - node[node[tq].lson].sum;
    if (k <= t)
        return query(node[tp].lson, node[tq].lson, k);
    else
        return query(node[tp].rson, node[tq].rson, k - t);
}
#define maxL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[100000], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int fpath[30];
int rank[1048576], arank[1048576], ridx = 0;
void dfsBuild(int idx, long long v, int mxdep, int dep) {
    if (dep == mxdep) {
        rank[v] = ++ridx;
        arank[ridx] = v;
        return ;
    } 
    for (int i = idx; i < Pt && v * P[i] <= 1000000; i++)
        fpath[dep] = P[i], dfsBuild(i, v * P[i], mxdep, dep+1);
}
void printfactor(int n) {
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            for(j = 0; n%P[i] == 0; n /= P[i], j++)
                printf(" %d", P[i]);
        }		
    }
    if (n != 1)	printf(" %d", n);
    puts("");
}
int main() {
    sieve();
    for (int i = 1; i < 20; i++)
        dfsBuild(0, 1, i, 0);    
            
    nodesize = 1;
    root[0] = build(1, 1000000);        
    for (int i = 1; i <= 1000000; i++) {
        if (rank[i])
        	root[i] = change(root[i-1], rank[i], 1);
        else
        	root[i] = root[i-1];
    }
    
    int testcase, cases = 0, x, y, k;
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d %d %d", &x, &y, &k);
    	int ret = arank[query(root[y], root[x-1], k)];
    	printf("Case %d:", ++cases);
        printfactor(ret);
    }
    return 0;
}
/*
 7 3
 1 5 2 6 3 7 4
 2 5 3
 4 4 1
 1 7 3
 */
Read More +
解題區/解題區 - UVa

UVa 11501 - Laurel Creek

Problem

在淹水的平台上，有不少樹樁 (stump) 和漂浮的圓木 (log)，可以經由圓木到另一個樹樁，請問最少要幾個操作才能從起點樹樁到終點樹樁。

操作：

  • 根據相鄰的圓木，移動到下一個樹樁。
  • 撿起某一個方向的相鄰圓木，身上最多拿著一個圓木。
  • 往另一個方向放置圓木，並且另一端要恰好接著樹樁。

給定的圓木會有多個 | 或者是 - 連接在一起表示同一個圓木。

Sample Input

1
2
3
4
5
6
7
8
9
1
7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E

Sample Output

1
10

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
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
int n, m;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct state {
    char g[17][17];
    int x, y, log;
    bool operator<(const state &a) const {
        if (x != a.x)	return x < a.x;
        if (y != a.y)	return y < a.y;
        if (log != a.log)	return log < a.log;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] != a.g[i][j])
                    return g[i][j] < a.g[i][j];
        return false;
    }
    void print() {
        for (int i = 0; i < n; i++, puts("")) {
            for (int j = 0; j < m; j++) {
                if (i == x && j == y)	printf("!");
                else	printf("%c", g[i][j]);
            }
        }
        printf("log %d\n", log);
        puts("--");
    }
};
int isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs(state init) {
    state u, v;
    queue<state> Q;
    map<state, int> R;
    int tx, ty;
    Q.push(init), R[init] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = R[u];
        if (u.g[u.x][u.y] == 'E')
            return step;	
//		u.print(), getchar();
        for (int i = 0; i < 4; i++) { // traverse
            tx = u.x + dx[i], ty = u.y + dy[i];
            while (isValid(tx, ty) && u.g[tx][ty] != '.') {
                if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                    v = u, v.x = tx, v.y = ty;
                    if (R.find(v) == R.end()) {
                        R[v] = step + 1;
                        Q.push(v);
                    }
                    break;
                }
                if (i < 2 && u.g[tx][ty] != '-')	break;
                if (i > 1 && u.g[tx][ty] != '|')	break;
                tx += dx[i], ty += dy[i];
            }
        }
        if (u.log == 0) { // pick up
            for (int i = 0; i < 4; i++) {
                tx = u.x + dx[i], ty = u.y + dy[i];
                if (isValid(tx, ty) && ((i < 2 && u.g[tx][ty] == '-') || (i > 1 && u.g[tx][ty] == '|'))) {
                    v = u;
                    while (isValid(tx, ty) && u.g[tx][ty] != '.') {
                        if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                            if (R.find(v) == R.end()) {
                                R[v] = step + 1;
                                Q.push(v);
                            }
                            break;
                        }
                        v.g[tx][ty] = '.', v.log++;
                        if (i < 2 && u.g[tx][ty] != '-')	break;
                        if (i > 1 && u.g[tx][ty] != '|')	break;
                        tx += dx[i], ty += dy[i];						
                    }
                }
            }
        } else { // put down.
            for (int i = 0; i < 4; i++) {
                tx = u.x + dx[i], ty = u.y + dy[i];
                if (isValid(tx, ty) && u.g[tx][ty] == '.') {
                    int dist = 0;
                    while (isValid(tx, ty)) {
                        if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E') {
                            v = u;
                            if (dist == u.log) {
                                v.log = 0;
                                tx = u.x + dx[i], ty = u.y + dy[i];
                                while (isValid(tx, ty) && u.g[tx][ty] == '.') {
                                    if (u.g[tx][ty] == 'S' || u.g[tx][ty] == 'B' || u.g[tx][ty] == 'E')
                                        break;
                                    if (i < 2)	v.g[tx][ty] = '-';
                                    if (i > 1)	v.g[tx][ty] = '|';
                                    tx += dx[i], ty += dy[i];
                                }
                                if (R.find(v) == R.end()) {
                                    R[v] = step + 1;
                                    Q.push(v);
                                }
                            }
                            break;
                        }
                        if (u.g[tx][ty] != '.')	break;
                        dist++;
                        tx += dx[i], ty += dy[i];
                    }
                }
            }
        }
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        state init, u, v;
        for (int i = 0; i < n; i++)
            scanf("%s", init.g[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (init.g[i][j] == 'B')
                    init.x = i, init.y = j, init.log = 0;
            }
        }
        int ret = bfs(init);
        printf("%d\n", ret);
    }
    return 0;
}
/*
999
7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E
4 4
....
.B.S
.|..
...E
7 11
....S...S..
........|..
B-----S.|.E
......|.|..
......|.S..
......|....
....S-S....
4 4
....
S-B.
....
..E.
*/
Read More +
解題區/解題區 - UVa

UVa 11376 - Tilt!

Problem

滾球遊戲，一顆紅球在迷宮中滾動要收集到所有藍色球球 (藍色球球最多 25 顆)，求滾動的傾斜次數最少。每一次將盤面傾斜，紅球必須滾到該方向的最底部，能滾就必須繼續往方向滾過去。

Sample Input

1
2
3
4
5
6
7
8
9
5
9AC9C
18006
5120C
12806
3A63E
1 1
5 5
0

Sample Output

1
ESWNENWSE

Solution

這題說不定 bfs 就可以過，被蘿莉控的文字欺騙寫了不純正的 IDA，IDA 原則上不會記錄任何搜索狀態，否則就跟 A* 一樣，然而這一題多卡一個狀態紀錄，就這麼 AC，並且拿到 Rank 6，速度還挺快的。

狀態：當前紅球所在位置、已經得到的藍球 (壓縮在一個 32bits 內)

估價函數：當前位置到剩餘藍球的最少步數的最大值

預處理每一個位置滾動的下一個位置，減少過程中模擬的時間。

單純的 IDA* 無法通過，在討論區的測資也要跑很久，隨後加搜索過程中的狀態紀錄，速度可以說飛快。但是由於深度加深的處理，每一次必須清空搜索紀錄，稍微比 bfs 好點的地方只在於利用啟發式的估價函數砍不少狀態紀錄。

IDA*

迭代加深搜索，由於 dfs 會深度優先，會導致搜索深度太深而無法找到最少、最佳解，因此根據搜索時的估價函數，慢慢鬆弛可以搜索的限制深度。

這方面很類似 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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <stdio.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
char g[16][16];
int bg[16][16], dirg[16][16][4][3], blueAll, blueCnt;
int short_path[16][16][32];
const int dx[] = {0, -1, 1, 0};
const int dy[] = {1, 0, 0, -1};
const int dmask[] = {4, 8, 2, 1};
const char dstr[] = "ENSW";
void buildDirg(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 4; k++) {
                int blue = 0;
                int sx = i, sy = j;
                while (true) {
                    if (bg[sx][sy])
                        blue |= 1<<(bg[sx][sy]-1);
                    if (g[sx][sy]&dmask[k])
                        break;
                    sx += dx[k], sy += dy[k];
                }
                dirg[i][j][k][0] = sx;
                dirg[i][j][k][1] = sy;
                dirg[i][j][k][2] = blue;
            }
        }
    }
}
void buildHfun(int n) {
    memset(short_path, 0x3f, sizeof(short_path));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            queue<int> X, Y;
            int dist[16][16], sx, sy, tx, ty;
            memset(dist, 0x3f, sizeof(dist));
            X.push(i), Y.push(j), dist[i][j] = 0;
            if (bg[i][j])
                short_path[i][j][bg[i][j]-1] = min(short_path[i][j][bg[i][j]-1], 0);
            while (!X.empty()) {
                sx = X.front(), X.pop();
                sy = Y.front(), Y.pop();
                for (int p = 0; p < 4; p++) {
                    tx = sx, ty = sy;
                    while (true) {
                        if (bg[tx][ty])	
                            short_path[i][j][bg[tx][ty]-1] = min(short_path[i][j][bg[tx][ty]-1], dist[sx][sy] + 1);
                        if (g[tx][ty]&dmask[p])
                            break;
                        tx += dx[p], ty += dy[p];
                    }						
                    if (dist[tx][ty] > dist[sx][sy] + 1) {
                        dist[tx][ty] = dist[sx][sy] + 1;
                        X.push(tx), Y.push(ty);
                    }
                }
            }
        }
    }
}
int ida_dep, solved;
char path[1024];
int H(int sx, int sy, int bstate) {
    int ret = 0;
    for (int i = 0; i < blueCnt; i++) {
        if ((bstate>>i)&1)	continue;
        ret = max(ret, short_path[sx][sy][i]);
    }
    return ret;
}
map<int, int> record[16][16]; // [sx][sy][bstate] = minstep
int IDA(int sx, int sy, int bstate, int dep, int hv, int dlast) {
    if (hv == 0) {
        path[dep] = '\0';
        puts(path);
        solved = dep;
        return dep;
    }
    if (dep + hv > ida_dep)	return dep + hv;
    
    map<int, int>::iterator it = record[sx][sy].find(bstate);
    if (it == record[sx][sy].end())
        record[sx][sy][bstate] = dep;
    else {
        if (it->second <= dep)	return 0x3f3f3f3f;
        else					it->second = dep;
    }
    
    int ret = 0x3f3f3f3f, shv, tmp;
    for (int i = 0; i < 4; i++) {
        if (i == dlast)	continue;
        path[dep] = dstr[i];
        shv = H(dirg[sx][sy][i][0], dirg[sx][sy][i][1], bstate|dirg[sx][sy][i][2]);
        tmp = IDA(dirg[sx][sy][i][0], dirg[sx][sy][i][1], bstate|dirg[sx][sy][i][2], dep+1, shv, i);
        if (solved)	return solved;
        ret = min(ret, tmp);
    }
    return ret;
}
int main() {
    int n, next_n, sx, sy, ex, ey;
    char s[1024];
    scanf("%d", &n);
    while (n) {
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        scanf("%d %d", &sx, &sy);
        sx--, sy--;
        memset(bg, 0, sizeof(bg));
        while (getchar() != '\n');
        while (gets(s)) {
            if (sscanf(s, "%d %d", &ex, &ey) == 2) {
                ex--, ey--;
                bg[ex][ey] = 1;
            } else if (sscanf(s, "%d", &next_n) == 1)
                break;
        }
        blueAll = blueCnt = 0;
        int bx[128], by[128];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (bg[i][j]) {
                    bx[blueCnt] = i, by[blueCnt] = j;
                    blueCnt++, bg[i][j] = blueCnt, blueAll |= 1<<(blueCnt-1);
                }
                if ('0' <= g[i][j] && g[i][j] <= '9')
                    g[i][j] -= '0';
                else if(g[i][j] >= 'A' && g[i][j] <= 'Z')
                    g[i][j] = g[i][j] - 'A' + 10;
            }
        }
        
        buildDirg(n);
        buildHfun(n);
        
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < n; j++) {
//				for (int k = 0; k < blueCnt; k++) {
//					printf("%d %d to %d %d = %d\n", i, j, bx[k], by[k], short_path[i][j][k]);
//				}
//			}
//		}
        
        int bstate = 0;
        if (bg[sx][sy])	bstate = 1<<(bg[sx][sy]-1);
        int initH = H(sx, sy, bstate);
        if (initH == 0) {
            puts("SOLVED");
        } else {
            solved = 0;
            ida_dep = initH;
            while (solved == 0) {
                ida_dep = IDA(sx, sy, bstate, 0, initH, 4);
                for (int i = 0; i < n; i++) // not tradition ida*
                    for (int j = 0; j < n; j++)
                        record[i][j].clear();
            }
        }
        n = next_n;
    }
    return 0;
}
/*
5
9AC9C
18006
5120C
12806
3A63E
1 1
5 5
0
8
9A88CB8C
18610824
30804184
90430004
10080457
1430000C
53800245
3A263A26
6 4
4 1
8 1
2 2
7 3
4 4
1 5
7 5
5 6
3 7
8 7
2 8
4 8
6
98E98E
30A00C
908047
10430C
710804
B63677
4 1
1 3
3 6
5
9AC9C
18006
5120C
12806
3A63E
1 1
5 5
0
*/
Read More +