解題區/解題區 - UVa

UVa 1558 - Number Game

Problem

給予 2 到 20 的內數字，兩名玩家輪流挑一個數字 x，並且將 x 的倍數遮蔽、x 倍數和已經被遮蔽的數字和也應該被遮蔽。

被遮蔽的數字將無法被使用。無法選擇任何數字的人輸。給定盤面上剩餘可選的數字，請問先手在第一步可以選擇哪幾個數字獲得勝利。

Sample Input

1
2
3
4
5
2
1
2
2
2 3

Sample Output

1
2
3
4
5
Scenario #1:
The winning moves are: 2.
Scenario #2:
There is no winning move.

Solution

由於數字量很小，可以進行 bitmask 壓縮，來得知數字的使用情況。接著套用博弈 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
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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1<<20];
int pick(int state, int x) {
    for (int i = x; i <= 20; i += x)
        if ((state>>(i-2))&1)
            state ^= 1<<(i-2);
    
    for (int i = x; i <= 20; i++) {
        if ((state>>(i-2))&1) {
            if (i - x >= 2) {
                if (((state>>(i - x -2))&1) == 0)
                    state ^= 1<<(i-2);
            }
        }
    }
    return state;
}
int dfs(int state) {
    if (state == 0)	
        return 0;
    if (dp[state] != -1)	
        return dp[state];
    int &ret = dp[state];
    ret = 0;
    for (int i = 2; i <= 20; i++) {
        if ((state>>(i-2))&1) {
            int v = dfs(pick(state, i));
            ret |= !v;
            if (ret) break;
        }
    }
    return ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        int mask = 0, x;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            mask |= 1<<(x-2);
        }
        
        printf("Scenario #%d:\n", ++cases);
        vector<int> ret;
        for (int i = 2; i <= 20; i++) {
            if ((mask>>(i-2))&1) {
                int v = dfs(pick(mask, i));
                if (v == 0)
                    ret.push_back(i);
            }
        }
        if (ret.size() == 0)
            puts("There is no winning move.");
        else {
            printf("The winning moves are:");
            for (int i = 0; i < ret.size(); i++)
                printf(" %d", ret[i]);
            puts(".");
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1557 - Calendar Game

Problem

給一個起始日期，兩名玩家輪流操作，操作方式有兩種，將日期往後延一天，將月份往後延一個月，抵達 November 4, 2001 的人獲勝，如果發生移動到不合法的日期則視為無效。

必須考慮閏年變化。

Sample Input

1
2
3
4
3
2001 11 3
2001 11 2
2001 10 3

Sample Output

1
2
3
YES
NO
NO

Solution

由於年份差最多 100，可以直接根據年月日做狀態搜索。要處理移動時，發生跨年、跨月，這方面會稍微麻煩一點。閏年要額外處理對 2/29 的日期判斷，並且移動時不可超出指定的日期之後。

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>
using namespace std;
const int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int dp[128][16][32], used[128][16][32], dcases = 0;
int validDate(int yyyy, int mm, int dd) {
    if (mm < 1 || mm > 12)	
        return 0;
    if ((yyyy%4 == 0 && yyyy%100 != 0) || (yyyy%400) == 0) {
        if (mm == 2) {
            if (dd < 1 || dd > 29)	
                return 0;
        } else {
            if (dd < 1 || dd > mday[mm])
                return 0;
        }			
    } else {
        if (dd < 1 || dd > mday[mm])
            return 0;
    }
    return 1;
}
int complete(int yyyy, int mm, int dd) {
    return yyyy == 2001 && mm == 11 && dd == 4;
}
int fail(int yyyy, int mm, int dd) {
    if (!validDate(yyyy, mm, dd))
        return 1;
    if (yyyy > 2001)	return 1;
    if (yyyy < 2001)	return 0;
    if (mm > 11)		return 1;
    if (mm < 11)		return 0;
    if (dd > 4)			return 1;
    if (dd < 4)			return 0;
    return 0;
}
void nextMonth(int &yyyy, int &mm, int &dd) {
    mm++;
    if (mm == 13)	yyyy++, mm = 1;
}
void nextDay(int &yyyy, int &mm, int &dd) {
    int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if ((yyyy%4 == 0 && yyyy%100 != 0) || (yyyy%400) == 0)
        mday[2] = 29;
    dd++;
    if (dd > mday[mm])
        mm++, dd = 1;
    if (mm == 13)	yyyy++, mm = 1;
}
int dfs(int yyyy, int mm, int dd) {
    if (fail(yyyy, mm, dd))
        return 0;
    if (complete(yyyy, mm, dd))
        return 1;
    if (used[yyyy-1900][mm][dd] == dcases)
        return dp[yyyy-1900][mm][dd];
    int &ret = dp[yyyy-1900][mm][dd];
    int y, m ,d;	
    ret = 0, used[yyyy-1900][mm][dd] = dcases;
    
    y = yyyy, m = mm, d = dd;
    nextMonth(y, m, d);
    if (complete(y, m, d))
        ret = 1;
    if (!fail(y, m, d))
        ret |= !dfs(y, m, d);
    
    y = yyyy, m = mm, d = dd;
    nextDay(y, m, d);
    if (complete(y, m, d))
        ret = 1;
    if (!fail(y, m, d))
        ret |= !dfs(y, m, d);
    return ret;
}
int main() {
    int testcase;
    int yyyy, mm, dd;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &yyyy, &mm, &dd);
        dcases ++;
        printf("%s\n", dfs(yyyy, mm, dd) ? "YES" : "NO");
    }
    return 0;
}
/*
3
2001 11 3
2001 11 2
2001 10 3
*/
Read More +
解題區/解題區 - UVa

UVa 1534 - Taekwondo

Problem

題目模型與 Zerojudge a192 接線問題 一樣。

題目背景在跆拳道選手，有兩團人馬，希望兩兩配對，體重差的絕對值總和越小越好。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2  
2 3
44.9 
50.0 
77.2 
86.4 
59.8 
4 2  
44.9 
50.0 
77.2 
86.4 
59.8 
58.9

Sample Output

1
2
42.1 
23.8

Solution

按照以前的思路來看，維護的是前一個最後匹配到的人是誰，這樣的效率保證是 $O(N^2)$，這樣的效能已經相當快，中間運用到維護最小值的技巧，由於前 i-1 個人匹配到前 j 個人的最小值，那麼 i 匹配到 k 時，需要的是 min(dp[i-1][0 <= j < k])，邊掃描邊維護。

看到網路上有一個不錯的定義，採用失匹配幾個人，較多人數的那一方，將會有幾個人無法匹配，也因此紀錄第 i 個人時，另一團人有 j 個人沒匹配到，那麼當前第 i 個人，必然要與編號 i + j 的人匹配。

忘了提及，一定要先排序，轉換到接線問題時，交錯匹配的距離會比較長，這部分屬於貪心。

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
#include <stdio.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
int dp[512][512]; // dp[i-th match in A][#miss match in B]
void solve(vector<int> A, vector<int> B) {
    assert(A.size() <= B.size());
    int n1 = A.size(), n2 = B.size();
    int diff = n2 - n1;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    for (int i = 0; i < n1; i++) {
        int mn = 0x3f3f3f3f;
        for (int j = 0; j <= diff; j++) {
            if (i == 0)
                mn = 0;
            else
                mn = min(mn, dp[i-1][j]);
            dp[i][j] = mn + abs(A[i] - B[i + j]);
        }
    }
    
    int ret = 0x3f3f3f3f;
    for (int i = 0; i <= diff; i++)
        ret = min(ret, dp[n1-1][i]);
    printf("%d.%d\n", ret/10, ret%10);
}
int main() {
    int testcase;
    int n1, n2, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n1, &n2);
        vector<int> A, B;
        for (int i = 0; i < n1; i++) {
            scanf("%d.%d", &x, &y);
            A.push_back(x * 10 + y);
        } 
        for (int i = 0; i < n2; i++) {
            scanf("%d.%d", &x, &y);
            B.push_back(x * 10 + y);
        } 
        
        if (n1 < n2)
            solve(A, B);
        else
            solve(B, A);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 996 - Find the Sequence

Problem

這一題是 UVa 997 - Show the Sequence 的反運算，給定序列找到操作的產生方法。

Sample Input

1
2
3 10 30 30 -30 90 -450 3150
2 2 6 36 360 5400 113400

Sample Output

1
2
[2*[5+[-2]]]
[0]

Solution

由於每一個數字不算大，而且從操作方法中得知，數字大小的增長速度非常快，對於累加的部分可以 O(1) 窮舉，但是對於乘積部分需要窮舉因數來得知。

由於題目不是 special judge 也擔心就算找到答案是不是唯一解，按著 Dfs 搜索的順序就 AC 了。之前寫的版本還真是有點微妙。

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
#include <stdio.h>
#include <set>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
string num2str(int x) {
    string s;
    stringstream sin(s);
    sin << x;
    return sin.str();
}
int dfs(vector<int> A, int M, string &solution) {
//    printf("[");
//    for (int i = 0; i < A.size(); i++)
//        printf("%d ", A[i]);
//    puts("]");
    int same = 1;
    for (int i = 1; i < A.size(); i++)
        same &= A[i] == A[0];
    if (same == 1) {
        solution = "[" + num2str(A[0]) + "]";
        return 1;
    }
    if (M <= 0)  return 0;
    int g = A[0];
    for (int i = 0; i < A.size(); i++) {
        if (A[i] == 0) {
            g = 0;
            break;
        }
        g = __gcd(g, A[i]);
    }
    for (int i = 1; i < A.size(); i++) {
        if (A[i-1] != 0 && A[i]%A[i-1] != 0)
            g = 0;
        if (A[i-1] == 0 && A[i] != 0)
            g = 0;
    }
    if (g < 0)  g = -g;
    if (g > 0) {
        for (int m = 1; m <= g; m++) {
            if (g%m == 0) {
                vector<int> nA;
                nA.push_back(A[0] / m);
                for (int j = 1; j < A.size(); j++) {
                    if (A[j-1] == 0)
                        nA.push_back(0);
                    else
                        nA.push_back(A[j] / A[j-1]);
                }
                if (dfs(nA, M-1, solution)) {
                    solution = "[" + num2str(m) + "*" + solution + "]";
                    return 1;
                }
                nA.clear();
                nA.push_back(A[0] / (-m));
                for (int j = 1; j < A.size(); j++) {
                    if (A[j-1] == 0)
                        nA.push_back(0);
                    else
                        nA.push_back(A[j] / A[j-1]);
                }
                if (dfs(nA, M-1, solution)) {
                    solution = "[" + num2str(-m) + "*" + solution + "]";
                    return 1;
                }
            }
        }
    }
    vector<int> nA;
    for (int i = 1; i < A.size(); i++)
        nA.push_back(A[i] - A[i-1]);
    if (dfs(nA, M-1, solution)) {
        solution = "[" + num2str(A[0]) + "+" + solution + "]";
        return 1;
    }
    return 0;
}
int main() {
    int M, x;
    string line;
    while (getline(cin, line)) {
        stringstream sin(line);
        sin >> M;
        vector<int> A;
        while (sin >> x)
            A.push_back(x);
        string solution;
        int f = dfs(A, M, solution);
        if (f == 0)
            puts("[0]");
        else
            puts(solution.c_str());
    }
    return 0;
}
/*
 3 10 30 30 -30 90 -450 3150
 2 2 6 36 360 5400 113400
*/
Read More +
解題區/解題區 - UVa

UVa 953 - The Incredible Pile Machine

Problem

現在有 N 堆，總共有 N 種物品，希望移動最少次，使得每一堆只具有單一種物品。

輸出最小的組合方案。按照第 i 種物品放置在第 j 堆的字典順序最小。

Sample Input

1
2
3
4
5
6
7
4
3 2 3 4 0 0 2 1 3 1
3 66 66 0 66 66 0 66 66 66
6 476 357 874 50 594 394 320 803 817 348 252 940 453 500 647 299
94 143 800 947 561 885 389 172 301 276 612 130 540 731 774 306 96
239 227 907
2 99 1 1 99

Sample Output

1
2
3
4
021 9
012 264
251340 12741
01 2

Solution

很明顯地答案會是在某一堆 X 指派給 A 物品，那麼可以減少的移動次數是 X 原本具有 A 的數量。因此答案會是物品述兩總和扣除最大權匹配。

但是答案特別要求輸出字典順序要最小，所以用 KM 算法、最少費用流會稍微麻煩一點，也許多做 $O(N^2)$ 次的窮舉也可以完成。這裡使用 bitmask 的方式去找到最順序最小的最大權匹配。

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>
#include <algorithm>
using namespace std;
const int MAXN = 10;
int dp[MAXN][1<<MAXN], used[MAXN][1<<MAXN];
int main() {
    int testcase, N;
    int type[20][20];
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d", &N);
    	
    	int sum = 0;
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++)
    			scanf("%d", &type[i][j]), sum += type[i][j];
    	}
    	    	
    	memset(dp, 0, sizeof(dp));
    	memset(used, 0, sizeof(used));
    	for (int i = 0; i < N; i++)
    		dp[0][1<<i] = type[0][i];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < (1<<N); j++) {
                for (int k = 0; k < N; k++) {
                    if ((j>>k)&1)	continue;
                    dp[i+1][j|(1<<k)] = max(dp[i+1][j|(1<<k)], dp[i][j] + type[i+1][k]);
                }
            }
        }
        
        used[N-1][(1<<N) - 1] = 1;
        for (int i = N-2; i >= 0; i--) {
            for (int j = 0; j < (1<<N); j++) {
                for (int k = 0; k < N; k++) {
                    if ((j>>k)&1)	continue;
                    if (used[i+1][j|(1<<k)] && dp[i+1][j|(1<<k)] == dp[i][j] + type[i+1][k])
                        used[i][j] = 1;
                }
            }
        }
        int ret = dp[N-1][(1<<N)-1];
        for (int i = 0, p, q = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if ((q>>j)&1)
                    continue;
                if (used[i][q|(1<<j)]) {
                    p = j, q |= 1<<j;
                    break;
                }
            }
            printf("%d", p);
        }
        printf(" %d\n", sum - ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 905 - Tacos Panchita

Problem

類似磁性場，所有的指針位置都會指向目的地。不過這題的感覺比較像是風向儀，從目的地往外吹動，三角形是風向儀所在的位置，正方形則表示旗幟飄揚的位置。

給定三角形位置，請問正方形的位置在哪裡。

Sample Input

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

Sample Output

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

測資參考圖

1
2
3
4
5
6
7
6 M   P
5 P
4
3  X  PM
2 P
1 M  PM
 1234567

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
#include <stdio.h> 
#include <string.h>
#include <assert.h>
const int MAXN = 128;
int g[MAXN][MAXN], ret[MAXN][MAXN];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int main() {
    int px, py, w, h;
    int cases = 0;
    while (scanf("%d %d %d %d", &px, &py, &w, &h) == 4) {
        assert(w < MAXN && h < MAXN);
        if (cases++)	puts("");
        
        memset(g, 0, sizeof(g));
        memset(ret, 0, sizeof(ret));
        for (int i = 0; i < MAXN; i++) {
            int x, y;
            x = px - i - 1, y = py + i + 1;
            for (int j = 0; j < 2 * (i + 1); j++) {
                if (x >= 0 && x <= w && y >= 0 && y <= h)
                    g[x][y] = 1;
                y -= 1;
            }
            x = px - i, y = py + i + 1;
            for (int j = 0; j < 2 * (i + 1); j++) {
                if (x >= 0 && x <= w && y >= 0 && y <= h)
                    g[x][y] = 2;
                x += 1;
            }
            x = px + i + 1, y = py + i;
            for (int j = 0; j < 2 * (i + 1); j++) {
                if (x >= 0 && x <= w && y >= 0 && y <= h)
                    g[x][y] = 3;
                y -= 1;
            }
            x = px - i - 1, y = py - i - 1;
            for (int j = 0; j < 2 * (i + 1); j++) {
                if (x >= 0 && x <= w && y >= 0 && y <= h)
                    g[x][y] = 4;
                x += 1;
            }
        }
        
        for (int i = h; i >= 1; i--) {
            int n, x;
            scanf("%d", &n);
            for (int j = 0; j < n; j++) {
                scanf("%d", &x);
                int tx, ty;
                tx = x + dx[g[x][i] - 1];
                ty = i + dy[g[x][i] - 1];
                ret[tx][ty] = 1;
            }
        }
//		for (int i = 1; i <= w; i++, puts(""))
//			for (int j = 1; j <= h; j++)
//				printf("%d", g[i][j]);
                
        printf("%d %d %d %d\n", px, py, w, h);
        for (int i = h; i >= 1; i--) {
            int n = 0;
            for (int j = 1; j <= w; j++)
                n += ret[j][i];
            printf("%d", n);
            for (int j = 1; j <= w; j++)
                if (ret[j][i])
                    printf(" %d", j);
            puts("");
        }
    }
    return 0;
}
/*
3 3 7 6
1 6
1 2
0
1 6
1 2
1 5
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 F - No challenge No life

Problem

這次要挑戰的題目為 UVa 12647 - Balloon，由於網路上有一些線段樹的作法，如

http://www.cnblogs.com/yours1103/p/3426212.html

這裡可以看到有一些人利用線段樹來完成操作，實際上的做法根據掃描線，y 座標從高度低到高、或者是高到低的線段依序放入，到時候查找第一個獲最後一個覆蓋的線段編號。

UVa 12647 - Balloon 主要是在問，給予一些天花板，請問放置一個氣球，氣球會沿著天花板歪斜的地方移動 (如果沒歪則停止)，詢問最後停留的位置。有可能會飛到無窮遠，則輸出最後的 x 座標，反之輸出停留的 (x, y) 地點。如果發生一個地點有數個天花板，發生擦邊情況，則氣球會依據第一個碰觸到的天花板進行移動。

Solution

既然發現它們 (搜尋可以找到至少兩個大大的線段樹寫法) 基本上都是按照覆蓋的方式，找到覆蓋編號去完成移動、建造飛行的所有可能。

明顯地，由於天花板線段的斜率有正有負，不能保證根據 y 座標排序可以決定飛行到下一個的高度的 x 範圍。因此交錯 y 座標線段，讓覆蓋方案失效。

下面有數組測資，可以讓史蒂芙掉測資、也會讓網址中的代碼掉。史蒂芙認為覆蓋不好，那用最大最小值去維護如何！這樣也許就好點了吧？但不幸地，這麼做一樣會遇到排序 y 的問題，不管怎麼排序，都會造成建構方法不正確。

challenge 的題目還不太會傳，中間有點小問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h> 
int main() {
//	puts("4 1");
//	puts("3 1 12 4");
//	puts("5 2 2 3");
//	puts("1 4 4 3");
//	puts("7 5 14 5");
//	puts("4");
    puts("3 3");
    puts("5 5 10 4");
    puts("2 2 6 4");
    puts("0 3 4 4");
    puts("0");
    puts("1");
    puts("2");
//	puts("7 4");
//	puts("3 1 12 4");
//	puts("5 2 2 3");
//	puts("1 4 4 3");
//	puts("7 5 14 5");
//	puts("25 5 30 4");
//	puts("22 2 26 4");
//	puts("20 3 24 4");
//	puts("4");
//	puts("20");
//	puts("21");
//	puts("22");
    return 0;
}
/*
3 3
5 5 10 4
2 2 6 4
0 3 4 4
0
1 
2
4 1
3 1 12 4
5 2 2 3
1 4 4 4
7 5 14 5
4
4 1
3 1 12 4
5 2 2 3
1 4 4 3
7 5 14 5
4
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 G - Strange Permutations

Problem

排列 1 到 n 的整數，使得相鄰兩數互質，部分位置一定要填入某些數字，請問剩餘數字的填法方案數為何？

Sample Input

1
2
3
1
8
1 2 0 0 0 0 7 8

Sample Output

1
2

Solution

bitmask 下去 dp[N][1<<N][N]，dp[i][j][k] 表示前 i 個位置，已經使用的數字狀態 j，最後一個數字 k。不曉得需不需要滾動，記憶體用量驚人。萬萬沒想到，撰寫過程中坑了一個建表的 gcd[20][20]，當 n = 20 時，直接 index out of bound，先撇開這個蠢錯。滾動數組下去玩，真是誘人的時間限制，再次得到 9.990s TLE 的事蹟 ！仔細想想，運算過程中只出現加法，將 mod 運算替換成條件判斷 + 減法，

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 20;
int dp[2][1<<MAXN][MAXN], used[2][1<<MAXN][MAXN], ucases = 0;
int g[MAXN+20][MAXN+20];
int vaild(int i, int a, int b) { // a contract b
    if (i == 0)	return 1;
    return g[a+1][b+1];
}
int main() {
    for (int i = 1; i <= MAXN; i++) {
        for (int j = 1; j <= MAXN; j++)
            g[i][j] = __gcd(i, j) == 1;
    }
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int cant = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            if (A[i])
            	cant |= 1<<(A[i]-1);
        }
        
        int flag = 0;
        int mask = (1<<n)-1;
        int ret = 0;
//        memset(dp, 0, sizeof(dp));
        ucases++;
        used[flag][0][0] = ucases;
        dp[flag][0][0] = 1;
        for (int i = 0; i < n; i++) {
            int p = flag, q = !flag;
            flag = 1 - flag;
            ucases++;
//            for (int j = mask; j >= 0; j--)
//            	for (int k = 0; k < n; k++)
//            		dp[q][j][k] = 0;
            for (int j = (1<<n)-1; j >= 0; j--) {
            	for (int k = 0; k < n; k++) {
            		if (used[p][j][k] != ucases-1)
            			continue;
            		int ways = dp[p][j][k];
            		if (ways == 0)
            			continue;
            		if (A[i] == 0) {
            			for (int p = 0; p < n; p++) {
            				if ((j>>p)&1)
            					continue;
            				if (!vaild(i, k, p))
            					continue;
            				if (used[q][j|(1<<p)][p] != ucases)
            					used[q][j|(1<<p)][p] = ucases, dp[q][j|(1<<p)][p] = 0;
            				dp[q][j|(1<<p)][p] += ways;
            				if (dp[q][j|(1<<p)][p] >= MOD)
            					dp[q][j|(1<<p)][p] -= MOD;
            			}
            		} else {
            			for (int p = A[i]-1; p <= A[i]-1; p++) {
            				if ((j>>p)&1)
            					continue;
            				if (!vaild(i, k, p))
            					continue;
            				if (used[q][j|(1<<p)][p] != ucases)
            					used[q][j|(1<<p)][p] = ucases, dp[q][j|(1<<p)][p] = 0;
            				dp[q][j|(1<<p)][p] += ways;
                            if (dp[q][j|(1<<p)][p] >= MOD)
            					dp[q][j|(1<<p)][p] -= MOD;
            			}
            		}
            	}
            }
        }
        
        for (int i = 0; i < n; i++) {
        	if (used[flag][(1<<n)-1][i] != ucases)
        		continue;
        	ret += dp[flag][(1<<n)-1][i];
        	ret %= MOD;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
10
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4
0 2 4 0
8
1 3 5 0 0 0 0 0
8
1 2 0 0 0 0 7 8
8
1 0 5 8 0 0 0 0
8
0 2 0 7 0 0 0 8
8
0 2 0 0 0 0 0 8
8
0 2 0 0 0 0 0 0
8
0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0
1
0
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 E - Kirino in Google Code Jam

Problem

2015 Google Code Jam Round 1A 中，C - Logging 有點嚴重的問題！很多精準度不高的代碼都通過了！現在要求去找到測資 tricky cases，讓他們通通 WA！

原題是對於任意平面點，找到要移除最小的平面點，使得自己在凸包邊緣上。標準的極角排序，維護 180 度以內 (半平面) 的點個數。

atan2 esp = 1e-12 not enough for $x, y \in \left [0, 10^6 \right]$，極角排序替代方案！快來戳我的講法，看 POJ 類似的題目，精準度要壓到 1e-16 呢，所以誤差還要抓更小才行。

Solution

等等，challenge 這一題時，自己的代碼也 WA 了！

一開始誤以為是 index out of bound，assert() 下去都沒發生。後來估計是 atan2(y, x) 的誤差，對此誤差早有耳聞，解題撞壁的機會很低。咱很蠢，隨機生了 1000 萬個平面點，按照 atan2 排序，檢查相鄰兩個座標的外積 (叉積) 是否為逆時針，跑一次隨機生成大概能爆出一個誤差的相鄰點，十來次得到 n 個點，隨機組合這 n 個點於四個象限，再亂撒少數個點，再跟自己撰寫的代碼做比對 (中間又測了上萬組)。

atan2 誤差測試

atan2_eps_test
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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <time.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}	
double distSeg2Point(Pt a, Pt b, Pt p) {
    Pt c, vab;
    vab = a - b;
    if (between(a, b, p)) {
        c = getIntersect(Seg(a, b), Seg(p, Pt(p.x+vab.y, p.y-vab.x)));
        return (p - c).length();
    }
    return min((p - a).length(), (p - b).length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
const double pi = acos(-1);
int main() {
    srand ( time(NULL));
    
    vector< pair<double, Pt> > V;
    for (int i = 0; i < 10000000; i++) {
        int X, Y;
        X = (rand()*rand())%2000000 - 1000000;
        Y = (rand()*rand())%2000000 - 1000000;
        V.push_back(make_pair(atan2(Y, X), Pt(X, Y)));
    }
    sort(V.begin(), V.end());
    for (int i = 0; i+1 < V.size(); i++) {
        if (cross2(V[i].second, V[i+1].second) != 0 && fabs(V[i].first - V[i+1].first) < 1e-12)
            printf("%.0lf %.0lf %.0lf %.0lf\n", V[i].second.x, V[i].second.y, V[i+1].second.x, V[i+1].second.y);
    }
//	long long a = 599430;
//	long long b = 1428722;
//	long long c = 648824;
//	long long d = 1546451;
//	long long a = 885828;
//	long long b = 737167;
//	long long c = 898961;
//	long long d = 748096;
//
//	printf("%lld\n", a * d - b * c);
//	printf("%lf %lf, %d\n", atan2(b, a), atan2(d, c), fabs(atan2(b, a) - atan2(d, c)) < 1e-12);
    return 0;
}
/*
885828 737167 898961 748096
854425 732894 706721 606199
-971645 988877 -838743 853618
993753 -652232 991850 -650983
620105 659001 916399 973880
*/

誤差數據產生

testdata
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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <set>
#include <algorithm>
using namespace std;
double random() {
    int r = rand();
    return (double) r / RAND_MAX;
}
int vvv[20] = {885828, 737167, 898961, 748096,
854425, 732894, 706721, 606199,
-971645, 988877, -838743, 853618,
993753, -652232, 991850, -650983,
620105, 659001, 916399, 973880};
main() {
    int n, m, t, a, b, c, tmp;
    int z, i, j, k, l, p, q;
    srand ( time(NULL));
    freopen("in.txt", "w+t", stdout);
    
    int T = 10000;
    printf("%d\n", T);
    while(T--) {
        int n = 30, m = rand()%n + 1;
        printf("%d\n", n);
        set< pair<int, int> > S;
        S.insert(make_pair(0, 0));
        printf("%d %d\n", 0, 0);
        for (int i = 1; i < n; i++) {
            int x, y;
            do {
                if (rand()%10 < 8) {
                    x = vvv[rand()%20], y = vvv[rand()%20];
                    if (rand()%2)	x = -x;
                    if (rand()%2)	y = -y;
                } else {
                    x = rand()%100 - 50, y = rand()%100 - 50;
                }
            } while (S.count(make_pair(x, y)));
            S.insert(make_pair(x, y));
            printf("%d %d\n", x, y);
        }		
    }
    
    return 0;
}

對照組

利用外積的計算方案，誤差情況會更小。又因為是整數座標，基本上是不產誤差。

fixed-bug-Problem-C-Logging
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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
    double x, y;
    int label;
    Pt(double a = 0, double b = 0, int c = 0):
    x(a), y(b), label(c) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt D[4096];
bool cmp(const Pt& p1, const Pt& p2)
{
    if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
    if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
    if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
    if (p1.y * p2.y < 0) return p1.y > p2.y;
    double c = cross2(p1, p2);
    return c > 0 || c == 0 && fabs(p1.x) < fabs(p2.x);
}
int main() {
    int N, testcase, cases = 0;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        printf("Case #%d:\n", ++cases);
        
        if (N == 1) {
            puts("0");
            continue;
        }
        
        for (int i = 0; i < N; i++) {
            vector< Pt > A;
            for (int j = 0; j < N; j++) {
                if (i == j)
                    continue;
                Pt p = D[j] - D[i];
                A.push_back(p);
            }
            sort(A.begin(), A.end(), cmp);
            int M = (int)A.size();
            int l = 0, r = 0, cnt = 1;
            int ret = 0;
            for (l = 0; l < M; l++) {
                if (l == r)
                    r = (r+1)%M, cnt++;
                while (l != r && cross2(A[l], A[r]) >= 0) {
                    r = (r+1)%M, cnt++;
                }
                ret = max(ret, cnt);
                cnt--;
            }
            printf("%d\n", N - ret);
        }
    }
    return 0;
}

Final

生了 10000 組，終於在裡面發現其中幾組。

final
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
#include <stdio.h>
int main() {
    puts("1\n30\n0 0\n-971645 838743\n748096 -988877\n-652232 -993753\n737167 -838743\n-48 27\n706721 -885828\n606199 854425\n659001 -993753\n898961 885828\n-659001 885828\n748096 -973880\n21 -13\n-748096 606199\n-732894 991850\n13 -12\n659001 -737167\n-32 -32\n737167 -748096\n650983 -971645\n650983 -732894\n854425 -606199\n-606199 885828\n916399 -988877\n652232 -838743\n-606199 988877\n-620105 -652232\n-748096 -737167\n24 -23\n916399 854425\n");
    return 0;
}
/*
1
30
0 0
-971645 838743
748096 -988877
-652232 -993753
737167 -838743
-48 27
706721 -885828
606199 854425
659001 -993753
898961 885828
-659001 885828
748096 -973880
21 -13
-748096 606199
-732894 991850
13 -12
659001 -737167
-32 -32
737167 -748096
650983 -971645
650983 -732894
854425 -606199
-606199 885828
916399 -988877
652232 -838743
-606199 988877
-620105 -652232
-748096 -737167
24 -23
916399 854425
*/
Read More +
解題區/解題區 - 其他題目

[Tmt514] Beverage Cup 2 D - A Parking Problem

Problem

停車場有 n 個位置呈現單方向，由入口到出口分別編號為 1 到 n，現在有 m 名駕駛準備要停車，每名駕駛的停車方案都會先開到偏愛的車位上，如果發現已經有人停過，則會往後找一個空車位。由於駕駛入停車場任意順序。請問從 m 個駕駛中挑出 n 個駕駛，任意進入停車場，按照他們各自偏愛的停車方法，每一位都有停車位的合法選擇駕駛的方案數。

Sample Input

1
2
3
1
3
2 1 2

Sample Output

1
7

Solution

維護前 i 個位置中，挑選 j 名駕駛的方法數！dp[i][j] 表示前 i 個位置，挑選 j 個駕駛的方法數，並且滿足 j >= i，否則會有留空一格造成後續的非法解。窮舉下一個位置挑選的人數 k，得到 dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;

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
#include <stdio.h>
const int MOD = 1000000007;
const int MAXN = 64;
long long C[MAXN][MAXN] = {};
int main() {
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
    }
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        long long dp[MAXN][MAXN] = {};
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j <= n; j++) {
                for (int k = 0; k <= A[i+1] && j+k <= n; k++) {
                    dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;
                    dp[i+1][j+k] %= MOD;
                }
            }
        }
        printf("%lld\n", dp[n][n]);
    }
    return 0;
}
/*
 1
 3
 2 1 2
*/
Read More +