解題區/解題區 - UVa

UVa 561 - Jackpot

Problem

拉霸遊戲，給你每一個輪子上的情況，而你可以可以看到每個輪子的連續三個可視範圍。

可視範圍構成的 3 x 3 區塊，

  • 如果上面一排都是相同元素，則獎金累加 5 元
  • 如果下面一排都是相同元素，則獎金累加 5 元
  • 如果中間一排都是相同元素，則獎金累加 10 元
  • 如果左上到右下的對角線上都是相同元素，則獎金累加 7 元
  • 如果右上到左下的對角線上都是相同元素，則獎金累加 7 元

求轉動一次的期望獎金為何

Sample Input

1
2
3
4
5
6
7
8
9
2
3 4 6
AAB
BABA
BBAAAB
12 15 18
CCCCCCCCCCCC
CCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCC

Sample Output

1
2
8.5000
34.0000

Problem

直接窮舉每一種字符的機率於每一個位置即可。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
int main() {
    int testcase;
    int A, B, C;
    char sa[1024], sb[1024], sc[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &A, &B, &C);
        scanf("%s %s %s", sa, sb, sc);
        int cntA[26] = {}, cntB[26] = {}, cntC[26] = {};
        for (int i = 0; sa[i]; i++) {
            cntA[sa[i] - 'A']++;
        }
        for (int i = 0; sb[i]; i++) {
            cntB[sb[i] - 'A']++;
        }
        for (int i = 0; sc[i]; i++) {
            cntC[sc[i] - 'A']++;
        }
        double ret = 0;
        for (int i = 0; i < 26; i++) {
            ret += cntA[i] * cntB[i] * cntC[i] * 7.0 / A/ B/ C * 2;
            ret += cntA[i] * cntB[i] * cntC[i] * 10.0 / A/ B/ C;
            ret += cntA[i] * cntB[i] * cntC[i] * 5.0 / A/ B/ C * 2;
        }
        printf("%.4lf\n", ret);
    }
    return 0;
}
/*
 2
 3 4 6
 AAB
 BABA
 BBAAAB
 12 15 18
 CCCCCCCCCCCC
 CCCCCCCCCCCCCCC
 CCCCCCCCCCCCCCCCCC
*/
Read More +
解題區/解題區 - UVa

UVa 560 - Magic

Problem

根據下列幾個條件，要把一個數字移除掉這些性質。

  • if a number is divisible by 3: divide it by 3
  • if a number is divisible by 7: divide it by 7
  • if a 3 occurs in the decimal representation: remove this 3 (remove if possible leading zeros)
  • if a 7 occurs in the decimal representation: remove this 7 (remove if possible leading zeros)
  • if a substring of 3 times the same digit occurs in the decimal representation: remove * it (remove if possible leading zeros)
  • if a substring of 7 times the same digit occurs in the decimal representation: remove it (remove if possible leading zeros)
  • if eventually no digit is left, consider this as the number 0.

移除的位置和順序可以任意替換，請問最後最大的數字為何？

Sample Input

1
2
3
4
3
999
273
2331

Sample Output

1
2
3
11
2
11

Solution

模擬這些移除的操作，使用 bfs 搜索，由於數字會越來越小，因此小於當前答案的部分可以忽略搜索，否則將很容易得到 TLE。

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 <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
using namespace std;
string divideString(string u, int div) {
    char s[1024] = {};
    int num = 0;
    for (int i = 0; i < u.length(); i++) {
        num = num * 10 + u[i] - '0';
        s[i] = num/div + '0', num %= div;
    }
    int idx = s[0] == '0' ? 1 : 0;
    string v = s + idx;
    return v;
}
string removePos(string u, int pos, int items = 1) {
    string v = u.substr(0, pos) + u.substr(pos + items);
//    cout << u << ", " << pos <<" = " << v<< endl;
    if (v.length() == 0)
        return "0";
    return v;
}
int numicStringCompare(string u, string v) {
    if (u.length() != v.length())
        return u.length() < v.length();
    for (int i = 0; i < u.length(); i++) {
        if (u[i] != v[i])
            return u[i] < v[i];
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        char s[1024];
        scanf("%s", s);
        set<string> diff;
        queue<string> Q;
        string ret = "";
        diff.insert(s), Q.push(s);
        while (!Q.empty()) {
            string u = Q.front();
            Q.pop();
//            cout << u << endl;
            if (numicStringCompare(u, ret))
                continue;
            int r3 = 0, r7 = 0;
            int cond = 0;
            for (int i = 0; i < u.length(); i++) {
                r3 = (r3 * 10 + u[i] - '0')%3;
                r7 = (r7 * 10 + u[i] - '0')%7;
            }
            if(r3 == 0) {
                string v = divideString(u, 3);
                if (diff.find(v) == diff.end())
                    diff.insert(v), Q.push(v);
                cond = 1;
            }
            if (r7 == 0) {
                string v = divideString(u, 7);
                if (diff.find(v) == diff.end())
                    diff.insert(v), Q.push(v);
                cond = 1;
            }
            for (int i = 0; i < u.length(); i++) {
                if (u[i] == '3' || u[i] == '7') {
                    string v = removePos(u, i);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
            }
            for (int i = 0; i < u.length(); i++) {
                int con3 = 0, con7 = 0;
                for (int j = i, k = 0; k < 3 && j < u.length(); j++, k++) {
                    if (u[j] == u[i])
                        con3++;
                    else    break;
                }
                for (int j = i, k = 0; k < 7 && j < u.length(); j++, k++) {
                    if (u[j] == u[i])
                        con7++;
                    else    break;
                }
                if (con3 == 3) {
                    string v = removePos(u, i, 3);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
                if (con7 == 7) {
                    string v = removePos(u, i, 7);
                    if (diff.find(v) == diff.end())
                        diff.insert(v), Q.push(v);
                    cond = 1;
                }
            }
            if (cond == 0) {
                if (numicStringCompare(ret, u)) {
                    ret = u;
                }
            }
        }
        cout << ret << endl;
    }
    return 0;
}
/*
 3
 999
 273
 2331
 
 6
 4900006514979587103
 9305660497031957126752544737246
 13708976269278645181999140607
 1427490008594779
 107351103235212538538682
 65244379091939972650698
*/
Read More +
解題區/解題區 - UVa

UVa 358 - Don't Have A Cow

Problem

有一個半徑為 R 的圓草地，接著將一頭牛綁在圓周上 (定點)，請問繩長多少的時候，恰好能夠將圓佔有 P% 的面積。

Sample input

1
2
1
100 0.33

Sample output

1
R = 100, P = 0.33, Rope = 13.24

Solution

將圓放在坐標軸上，假設綁定的位置於 (R, 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
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
#define eps 1e-8
int main() {
    int testcase;
    double R, P;
    const double pi = acos(-1);
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf %lf", &R, &P);
        double l = 0, r = pi, mid, ret = 0;
        double A = R * R * pi;
        while (fabs(l - r) > eps) {
            mid = (l + r)/2;
            ret = hypot(R * cos(mid) - R, R * sin(mid));
            double theta = (pi - mid)/2;
            double area = (ret * ret * theta/2 + (R * R * mid/2 - R * R * sin(mid)/2))*2;
            if (area < A * P)
                l = mid;
            else
                r = mid;
        }
        printf("R = %.0lf, P = %.2lf, Rope = %.2lf\n", R, P, ret);
        if(testcase)
            puts("");
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 12654 - Patches

Problem

輪胎上有數個洞需要補丁，只有兩種補丁，每個補丁長度不同，求用總長度最少的補丁覆蓋所有的洞。

Sample Input

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

Sample Output

1
2
3
4
5
8
12
2
2
3

Solution

這一題最麻煩就是處理環的部分，事實上我們可以窮舉補丁的起始位置，然後針對這一個位置進行 O(n) 計算 DP 最小值。

因此最後能在 O(n^2) 完成，為了簡化計算，直接對陣列的 rotate shift left 操作。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int F[1024];
int main() {
    int N, C, T[2];
    while(scanf("%d %d %d %d", &N, &C, &T[0], &T[1]) == 4) {
        for(int i = 0; i < N; i++)
            scanf("%d", &F[i]);
        sort(F, F+N);
        int ret = 0x3f3f3f3f;
        for(int i = 0; i < N; i++) {
            int dp[1024] = {};
            for(int j = 0; j <= N; j++)
                dp[j] = 0x3f3f3f3f;
            dp[0] = 0;
            int cover1 = 0, cover2 = 0;
            for(int j = 0; j < N; j++) {
                while(cover1 + 1 < N && F[cover1 + 1] - F[j] <= T[0])
                    cover1++;
                while(cover2 + 1 < N && F[cover2 + 1] - F[j] <= T[1])
                    cover2++;
                dp[cover1+1] = min(dp[cover1+1], dp[j] + T[0]);
                dp[cover2+1] = min(dp[cover2+1], dp[j] + T[1]);
            }
            ret = min(ret, dp[N]);
            swap(F[0], F[N]);
            F[N] += C;
            for(int j = 0; j < N; j++)
                F[j] = F[j+1];
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
5 20 2 3
2 5 8 11 15
4 20 12 9
1 2 3 13
2 10 3 2
0 9
2 10 3 2
0 2
2 10 3 2
0 3
*/
Read More +
解題區/解題區 - UVa

UVa 12648 - Boss

Problem

給一個管理階層圖 (DAG)，一名員工可能被很多上司管理

  • 員工之間可能會交換職位
  • 詢問某名員工最年輕的上司年紀為何 (包含上司的上司 …)

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
7 8 9
21 33 33 18 42 22 26
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
P 7
T 4 2
P 7
P 5
T 1 4
P 7
T 4 7
P 2
P 6
6 5 6
10 20 30 40 50 60
1 5
1 4
3 6
2 5
4 5
P 1
P 5
P 6
T 1 6
P 1
P 4

Sample Output

1
2
3
4
5
6
7
8
9
10
11
18
21
18
18
*
26
*
10
30
30
60

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 <string.h>
#include <vector>
using namespace std;
int visited[512];
int age[512];
vector<int> g[512], boss[512];
void dfs(int u, int em) {
    visited[u] = 1, boss[em].push_back(u);
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(visited[v])	continue;
        dfs(v, em);
    }
}
int main() {
    int N, M, I, x, y, em;
    char cmd[10];
    while(scanf("%d %d %d", &N, &M, &I) == 3) {
        for(int i = 1; i <= N; i++) {
            scanf("%d", &age[i]);
            g[i].clear(), boss[i].clear();
        }
        for(int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            g[y].push_back(x);
        }
        
        int mp[512];
        for(int i = 1; i <= N; i++) {
            mp[i] = i;
            memset(visited, 0, sizeof(visited));
            visited[i] = 1;
            for(int j = 0; j < g[i].size(); j++)
                if(!visited[g[i][j]])
                    dfs(g[i][j], i);
        }
        
        for(int i = 0; i < I; i++) {
            scanf("%s", cmd);
            if(cmd[0] == 'P') {
                scanf("%d", &em);
                int ret = 0x3f3f3f3f;
                em = mp[em];
                for(int i = 0; i < boss[em].size(); i++)
                    ret = min(ret, age[boss[em][i]]);
                if(ret == 0x3f3f3f3f)
                    puts("*");
                else
                    printf("%d\n", ret);
            } else {
                scanf("%d %d", &x, &y);
                swap(age[mp[x]], age[mp[y]]);
                swap(mp[x], mp[y]);
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12489 - Combating cancer

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
7
1 2
2 3
3 4
4 5
6 2
7 3
1 2
2 3
3 4
4 5
6 2
7 4
6
1 2
1 3
2 4
2 5
3 6
2 4
5 3
6 4
1 4
5 6

Sample Output

1
2
N
S

Solution

找到樹的最小表示法，用括號來表示一棵樹，則可以對所有的子樹的最小表示法做排序，就可以構成這個樹的最小表示法。一直遞歸下去就可以得到最小表示法。

但是這個最小表示法只能用在有根樹，因此對於無根樹利用拓樸排序找到樹的中心 (一個或者是兩個)。

因此最後相互比較中心的情況。

這一題為了加快可以使用 hash，而把字串比較和排序撇開，但是千萬不要拿不同中心兩個 hash 取最小值，再進行同構比較。原因會發生在於中心的取捨，如果直接定義拓樸最後兩個點作為中心，則有可能一點不是中心，那麼就會造成分析上的錯誤。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int dfsMinExp(int u, int p, vector<int> g[]) {
    vector<int>	branch;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v == p)	continue;
        branch.push_back(dfsMinExp(v, u, g));
    }
    sort(branch.begin(), branch.end());
//	string exp = "";
//	for(int i = 0; i < branch.size(); i++)
//		exp += branch[i];	
//	return "(" + exp + ")";	
    int a = 63689, b = 378551;
    int ret = 0;
    branch.push_back(1);
    for(int i = 0; i < branch.size(); i++)
        ret = ret * a + branch[i], a *= b;
    return ret;
}
vector<int> getTreeMinExp(vector<int> g[], int n) {
    if(n == 1)	return vector<int>({1});
    int deg[10005] = {}, u, v;
    int topo[10005] = {}, idx = 0;
    queue<int> Q;
    for(int i = 1; i <= n; i++) {
        deg[i] = g[i].size();
        if(deg[i] == 1)	Q.push(i);
    }
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        topo[idx++] = u;
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(--deg[v] == 1)
                Q.push(v);
        }
    }
    vector<int> ret;
    ret.push_back(dfsMinExp(topo[idx-1], -1, g));
    ret.push_back(dfsMinExp(topo[idx-2], -1, g));
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, x, y;
    vector<int> g1[65536], g2[65536];
    while(scanf("%d", &n) == 1) {
        for(int i = 1; i <= n; i++)
            g1[i].clear(), g2[i].clear();
        for(int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g1[x].push_back(y);
            g1[y].push_back(x);
        }
        for(int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g2[x].push_back(y);
            g2[y].push_back(x);
        }
        vector<int> hash1 = getTreeMinExp(g1, n);
        vector<int> hash2 = getTreeMinExp(g2, n);
        int same = 0;
        for(int i = 0; i < hash1.size(); i++)
            for(int j = 0; j < hash2.size(); j++)
                same |= hash1[i] == hash2[j];
        puts(same ? "S" : "N");
//		printf("%d %d\n", hash1, hash2);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12486 - Space Elevator

Problem

將所有數字中出現 4 或者是 13 為子字串排除，將剩餘數字排序後，根據輸入輸出 i-th 的結果為何。(傳統避諱的樓層命名方式)

Sample Input

1
2
3
4
5
1
4
11
12
440

Sample Output

1
2
3
4
5
1
5
12
15
666

Solution

  • dp[i][0] 表示長度為 i 的情況下，不以 3 開頭的所有符合數字
  • dp[i][1] 表示長度為 i 的情況下，以 3 開頭的所有符合數字

接著，企圖添加 digit 在長度為 i-1 的數字前面，只要不添加 1 湊出 13 即可。直接禁用 4 就沒有什麼問題。

而隨後要輸出 i-th 的時候，用扣的方式依序得到 lower_bound。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    unsigned long long n;
    unsigned long long dp[30][2] = {};
    unsigned long long sum[30] = {};
    dp[0][0] = 1; // [1-9^3], dp[i][1] - [3(0-9)*]
    for(int i = 1; i < 30; i++) {
        for(int j = 0; j < 2; j++) {
            dp[i][0] = 8 * dp[i-1][0] + 7 * dp[i-1][1];
            dp[i][1] = dp[i-1][0] + dp[i-1][1];
        }
    }
    for(int i = 1; i < 30; i++)
        sum[i] = sum[i-1] + (dp[i-1][0] + dp[i-1][1])* 7 + dp[i][1] - dp[i-1][1];
    while(scanf("%llu", &n) == 1) {
        int len = 0;
        for(len = 1; sum[len] <= n; len++);
        int prev = 0;
        n -= sum[len-1];
        for(int i = len; i >= 1; i--) {
            int last = -1;
            for(int j = (i == len); j <= 9; j++) {
                if(j == 4 || (prev == 1 && j == 3))	continue;
                if(j == 1) { // [1] - [0-9^3]
                    if(n > dp[i-1][0]) {
                        n -= dp[i-1][0], last = j;
//						printf("%llu test\n", dp[i-1][0]);
                    } else {
                        break;
                    }
                } else {
                    if(n > dp[i-1][0] + dp[i-1][1]) {
                        n -= dp[i-1][0] + dp[i-1][1], last = j;
//						printf("%llu test\n", dp[i-1][0] + dp[i-1][1]);
                    } else
                        break;
                }
            }
            last++;
            if(last == 4)	last++;
            if(i == len && last == 0)	last = 1;
            if(prev == 1 && last == 3)	last = 5;
            printf("%d", last), prev = last;
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12484 - Cards

Problem

每一個序列，每次只能拿走首元素或者尾元素，Alberto 和 Wanderley 輪流取牌，由 Alberto 先手，請問遊戲最後 Alberto 最高能得多少分，而 Wanderley 會盡力阻止她。

Sample Input

1
2
3
4
5
6
4
0 -3 5 10
4
0 -3 5 7
4
47 50 -3 7

Sample Output

1
2
3
10
7
57

Solution

照著 dp 的思路下去，因為要輪流取，而 Wanderley 只會想要最小化 Alberto 分數，不會考慮自己的分數，因此轉移的時候會盡可能地小。

dp[i][j] 表示當前剩餘長度為 i, 起始首元素為 j，由於狀態太多，必須靠滾動數組來完成 dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int n, a[10005];
    long long dp[2][10005];
    while(scanf("%d", &n) == 1) {
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j + i < n; j++) {
                if((i&1) == 1)
                    dp[0][j] = max(dp[1][j+1] + a[j], dp[1][j] + a[j+i]);
                else
                    dp[1][j] = min(dp[0][j+1], dp[0][j]);
            }
        }
        printf("%lld\n", dp[0][0]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12483 - Toboggan of Marbles

Problem

給彈珠檯的高度和寬度，以及左右兩側延伸出的平台，問彈珠滾落的最大直徑為何？

Sample Input

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

Sample Output

1
2
2.00
1.41

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double 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;
}
double 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) {
        double 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*/
        double 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() {
    int n;
    double L, H;
    LINE2D D[1024];
    while(scanf("%d", &n) == 1) {
        scanf("%lf %lf", &L, &H);
        for(int i = 0; i < n; i++) {
            D[i].s.x = i&1 ? L : 0;
            scanf("%lf %lf %lf", &D[i].s.y, &D[i].e.x, &D[i].e.y);
            D[i].type = SEGMENT;
        }
        
        LINE2D wall1, wall2;
        wall1.type = wall2.type = LINE;
        wall1.s.x = wall1.e.x = 0;
        wall1.s.y = 1, wall1.e.y = 0;
        
        wall2.s.x = wall2.e.x = L;
        wall2.s.y = 1, wall2.e.y = 0;
        
        double r = L;
        for(int i = 0; i < n; i++) {
            if(i&1)
                r = min(r, closest(wall1, D[i]));
            else
                r = min(r, closest(wall2, D[i]));
            if(i + 1 < n) {
                r = min(r, closest(D[i], D[i+1]));
            }
        }
        printf("%.2lf\n", r);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12446 - How Many... in 3D!

Problem

Given a 2x2xN box, in how many ways can you fill it with 1x1x2 blocks?
Input Format

The input starts with an integer T - the number of test cases (T <= 10,000). T cases follow on each subsequent line, each of them containing the integer N (1 <= N <= 1,000,000).

Output Format

For each test case, print the number of ways to fill the box modulo 1,000,000,007

Sample Input

1
2
3
4
3
1
2
3

Sample Output

1
2
3
2
9
32

Solution

把幾種情況畫出來，會發現有一種特別的之之型，最後會接上一個 1x2 的來湊滿一個 2 x 2 x N 的情況，為此我們必須要知道有多少這種之之型可以從哪裡拆分出來。

會在代碼中發現一個變數 c 存放的便是以之之型結束的方法數，之之型可以把最後一個 1x2 拿走，繼續延伸。

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 <algorithm>
using namespace std;
long long dp[1048576] = {};
const long long mod = 1000000007LL;
int main() {
    dp[0] = 1, dp[1] = 2, dp[2] = 9, dp[3] = 32;
    long long c = 4;
    for(int i = 4; i <= 1000000; i++) {
        c = (c + dp[i-3] * 4)%mod; // {ZigZag}
        dp[i] = (dp[i-1] * 2 + dp[i-2] * 5 + c)%mod; 
    }
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
    return 0;
}
/*
1000
1
2
3
4
5
6
7
2
9
32
121
450
1681
6272
*/
Read More +