解題區/解題區 - UVa

UVa 10799 - OOPS! They did it Again...

Problem

在區間 [l, r] 中挑出 k 個數字，並且挑出數字的間隔要相同，總問總和為 k 個倍數有多少種。

Sample Input

1
2
3
4
5
1 10 4  
2 10 4
1 48 2
1222 2329228 2
0 0 0

Sample Output

1
2
3
4
Case 1: 4
Case 2: 3
Case 3: 552
Case 4: 1354902984009

Solution

首先，可以窮舉間隔 d 與首項 a，根據等差公式可以推導得到 $(2 a + (K - 1)d) K /2 = aK + (K - 1)d K /2$，為了使之成立，必須滿足 K 整除的需求。為了加速運算考慮只窮舉間隔 d，找到合法的 a 解區間。

即便這樣 d 的範圍仍然很大，再仔細觀察一下運算，解區間的解個數呈現等差，觀察後直接計算即可。

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
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    long long L, R, K;
    int cases = 0;
    while (scanf("%lld %lld %lld", &L, &R, &K) == 3 && L + R + K) {
        long long ret = 0, N = R - L;
//		for (int d = 1; d <= N; d++) {
//			if (K * (K-1) * d %2 == 0 && K * (K-1) * d / 2 % K == 0) {
//				int ra0 = R - (K-1) * d, la0 = L;
//				if (la0 <= ra0)
//					ret += ra0 - la0 + 1, printf("%d\n", ra0 - la0 + 1);
//				else
//					break;
//			}
//		}
        
        long long b0 = -1, bn = -1, bd = -1;
        for (long long d = 1; d <= N/(K-1); d++)  {
            if (K * (K-1) * d %2 == 0 && K * (K-1) * d / 2 % K == 0) {
                long long ra0 = R - (K-1) * d, la0 = L;
                if (la0 <= ra0) {
                    if (b0 == -1)
                        b0 = ra0 - la0 + 1;
                    else {
                        bd = b0 - (ra0 - la0 + 1);
                        break;
                    }
                }
            }
        }
        for (long long d = N / (K-1); d >= 1; d--)  {
            if (K * (K-1) * d %2 == 0 && K * (K-1) * d / 2 % K == 0) {
                long long ra0 = R - (K-1) * d, la0 = L;
                if (la0 <= ra0) {
                    bn = ra0 - la0 + 1;
                    break;
                }
            }
        }
        
        if (b0 != -1) {
            ret = (b0 + bn) * ((b0 - bn) / bd + 1)/2;
        }
//		printf("%lld %lld %lld\n", b0, bn, bd);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
1 20000000 10000000
1 20000000 100000
*/
Read More +
解題區/解題區 - UVa

UVa 10766 - Organising the Organisation

Problem

給定組織每個人的關係圖，(x, y) 之間若有邊，表示彼此之間不能互為上司和下屬關係，請問將組織變成樹狀階層關係，總共有多少種方式。

Sample Input

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

Sample Output

1
2
3
3
8
3

Solution

先把沒有邊變成有邊、有邊變成沒邊，接著找到有多少種生成樹。

利用 Kirchhoff’s theorem 來完成，證明看 wiki。

先將鄰接矩陣轉換成拉普拉斯矩陣 L (Laplacian matrix)，其對角線上是每一個節點的度數，若 (x, y) 之間有邊，則標記 -1。接著將矩陣 L 去掉其中一行或一列，計算 L* 的行列值就是生成樹個數。

實際上拉普拉斯矩陣 L 可以被表示成 incidence matrix E (行: 頂點 x, 列: 邊編號 e)，$L = EE^T$。令 F 為 E 刪除第一行 (row) 的結果，則 $M_{11} = FF^T$，藉由 Cauchy–Binet formula 進行行列式展開，會從 m 條邊抓 n-1 條邊出來，拆分成 $\binom{m}{n-1}$ 項，對於每一項的結果，若圖連通則行列式為 1，反之為 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
95
96
97
98
99
100
101
102
// Kirchhoff's theorem, Matrix Tree Theorem, determinant value
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
// const long long PRIME_MOD = 1000000007LL;
const long long PRIME_MOD = 1000000000000037LL; // > 1e+15
const int MAXN = 64;
long long Q[MAXN][MAXN] = {}, L[MAXN][MAXN] = {};
int cg[MAXN][MAXN];
long long mul(long long a, long long b, long long mod) {
    if (b < 0)
        return -mul(a, -b, mod);
    long long ret = 0;
    for ( ; b != 0; b>>=1, (a<<=1)%=mod)
        if (b&1) (ret += a) %= mod;
    return ret;
}
// ax + by = g
void exgcd(long long x, long long y, long long &g, long long &a, long long &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
long long llabs(long long x) {
    return x < 0 ? -x : x;
}
long long det(long long A[][MAXN], int n) {
    long long sum = 1;
    long long g, a, b;
    for (int i = 0; i < n; i++) {
        exgcd(A[i][i], PRIME_MOD, g, a, b);
        long long inv = a;
        if (g < 0)  inv = -inv;
        for (int j = i+1; j < n; j++) {
            for (int k = n - 1; k >= i; k--) {
                A[j][k] = A[j][k] - mul(mul(A[i][k], A[j][i], PRIME_MOD), inv, PRIME_MOD);
                A[j][k] = (A[j][k]%PRIME_MOD + PRIME_MOD) %PRIME_MOD;
            }
        }
        sum = mul(sum, A[i][i], PRIME_MOD);
        if (sum == 0)
            return 0;
    }
    if (sum < 0)    sum = (sum % PRIME_MOD + PRIME_MOD) %PRIME_MOD;
    return llabs(sum);
}
int main() {
//    long long g, a, b, llx = 70, lly = 11;
//    exgcd(llx, lly, g, a, b);
//    printf("%lld %lld + %lld %lld = %lld\n", llx, a, lly, b, g);
    int N, M, K;
    int x, y;
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        memset(cg, 0, sizeof(cg));
        memset(Q, 0, sizeof(Q));
        memset(L, 0, sizeof(L));
        
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            cg[x][y] = cg[y][x] = 1;
        }
        
        // construct the Laplacian matrix Q
        for (int i = 0; i < N; i++) {
            int deg = 0;
            for (int j = 0; j < N; j++) {
                if (i != j && cg[i][j] == 0)  // has edge
                    Q[i][j] = -1, deg++;
            }
            Q[i][i] = deg;
        }
        
        // deleting row 1 and column 1 yields
        for (int i = 1; i < N; i++)
            for (int j = 1; j < N; j++)
                L[i-1][j-1] = Q[i][j];
        
        printf("%lld\n", det(L, N-1));
    }
    return 0;
}
/*
 5 5 2
 3 1
 3 4
 4 5
 1 4
 5 3
 
 4 1 1
 1 4
 
 3 0 2
 
 */
Read More +
解題區/解題區 - UVa

UVa 1091 - Barcodes

條碼中有一種編碼方式為 Code 11，只會針對數字 0 - 9 以及 - 進行編碼。對於每一個編碼結果都使用 5 個黑白相間 (BWBWB)的條紋表示，用 5 個 bits 表示黑白線的狀態，若 bit 為 1 則表示為粗線，反之為細線。為了間隔相鄰，都會使用白色細線間隔。

對應表如下

Character Encoding
0 00001
1 10001
2 01001
3 11000
4 00101
5 10100
6 01100
7 00011
8 10010
9 10000
- 00100
Start/Stop 00110

由於條碼掃描時，可能由左往右或由左往右掃描，藉由 START/STOP 來包裹內容，藉由非回文的編碼來導正順序。例子 START-1-3-2-STOP。

同時會加入兩個檢查碼，分別為 C, K 公式如題目所附，所以會變成 START-1-3-3-C-K-STOP。

現在給定一組條碼寬度陣列 (BWBWB …)，粗線寬度為細線寬度的兩倍，可能會發生誤差，誤差範圍為標準寬度的 5% 以內。請問是否存在合法的條碼。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
59 
10 20 20 10 10 10 20 10 10 20
10 10 10 10 20 10 20 10 10 10
20 10 20 10 20 10 20 10 10 10
10 10 20 10 10 10 10 10 10 20
20 10 20 10 10 20 10 10 20 10
10 10 20 10 10 20 20 10 10
35 
10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
10 10 10 10 10
35 
10 10 20 20 10 10 20 10 10 10
20 10 10 20 10 10 20 10 10 10
20 10 20 10 20 10 10 10 10 10
10 10 20 20 10 
0

Sample Output

1
2
3
Case 1: 123-45 
Case 2: bad code 
Case 3: bad K

Solution

由於要加入檢查碼，保證輸入的解碼至少 4 個字元 (START-C-K-STOP)，由於必須在字元編碼之間加入細白線，加設編碼 n 個字元，則陣列大小為 5n + n - 1。

接著要找細線、粗線到底使用什麼寬度，可以考慮把所有寬度找到，找一組合適的閥值 ((max_value + min_value)/2) 區分兩者，接著考慮粗線和細線的寬度是否能在 5% 內，由於是兩倍，放大兩倍之後誤差也會放大兩倍，那麼統一大小後，查看範圍是否落在 0.95 ~ 1.05 之間。

接著小心解碼，要支持順或逆的方式去讀，也要滿足每個編碼都存在，而且檢查碼要正確，同時要符合 START-???-C-K-STOP 的格式 … 等。

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map> 
#include <vector>
#include <algorithm>
using namespace std;
class Code11 {
public:
    map<string, int> code;
    Code11() {
        code["00001"] = 0, code["10001"] = 1;
    	code["01001"] = 2, code["11000"] = 3;
    	code["00101"] = 4, code["10100"] = 5;
    	code["01100"] = 6, code["00011"] = 7;
    	code["10010"] = 8, code["10000"] = 9;
    	code["00100"] = 10; // -
    	code["00110"] = -1;
    }
    string scan(int n, int b[]) { 
        if (n%6 != 5)		return "bad code";
        if ((n + 1)/6 < 5)	return "bad code";	// S?CKE
        int m = (n + 1)/6;
        int mxw, mnw;
        mxw = 0, mnw = 0x3f3f3f3f;
        for (int i = 0; i < n; i++)
            mxw = max(mxw, b[i]), mnw = min(mnw, b[i]);
        double t = (mnw + mxw) / 2.0;
        mxw = 0, mnw = 0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
            int v = 0;
            if (b[i] < t)
                v = b[i] * 2;
            else
                v = b[i];
            mxw = max(mxw, v), mnw = min(mnw, v);
        }
        if (mxw * 95 > mnw * 105) 	// 5% larger or smaller than intended
            return "bad code";
        string bcode[256];
        for (int i = 0, j = 0; i < n; i += 6, j++) {
            bcode[j] = "";
            for (int k = i; k < i+5; k++) {
                if (b[k] < t)
                    bcode[j] = bcode[j] + "0";
                else
                    bcode[j] = bcode[j] + "1";
            }
            if (i+5 < n && b[i+5] >= t)	// separate bar = 0 
                return "bad code";
        }
        if (bcode[0] == "01100") {		// modify decode order to START-XXX-STOP
            reverse(bcode, bcode + m);
            for (int i = 0; i < m; i++)
                reverse(bcode[i].begin(), bcode[i].end());
        }
        if (bcode[0] != "00110" || bcode[m-1] != "00110")
            return "bad code";
        for (int i = 0; i < m; i++) { 	// undefine code
            if (!code.count(bcode[i]))
                return "bad code";
            if (i > 0 && i < m-1 && code[bcode[i]] == -1)
                return "bad code";
        }
        
        int C = 0, K = 0;
        for (int i = 1; i < m - 3; i++)
            C = (C + (((m - 4) - i)%10 + 1) * code[bcode[i]])%11;
        for (int i = 1; i < m - 2; i++)
            K = (K + (((m - 4) - i + 1)%9 + 1) * code[bcode[i]])%11;
        
        if (C != code[bcode[m - 3]])
            return "bad C";
        if (K != code[bcode[m - 2]])
            return "bad K";
        
        string res;
        for (int i = 1; i < m - 3; i++) {
            int v = code[bcode[i]];
            if (v < 10)	res += (char)(v + '0');
            else		res += (char)('-');
        }
        return res;
            
    } 
} g;
int main() {
    int n, b[256], cases = 0;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%d", &b[i]);
        string response = g.scan(n, b);
        printf("Case %d: %s\n", ++cases, response.c_str());
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 982 - Cube

Problem

有一天醒來，發現自己身處一個方體房間，六個面上都有門可以通往其他房間，不幸地是這裏沒有食物，若不趕緊走出去就會死在這裡。

搜索途中遇到其他人，他們說有些房間藏著陷阱，一碰到就會致死。為了逃離這裡，發現每個房間的角落都有一個數字，這個數字隱藏著出口的方向，指引著下一個要打開的門，但即使這樣，仍然不知道門後的房間是否有致死陷阱。

若房間的數字為 N 時，下一個門的座標為

  • x = (N 出現幾次偶數位數) / (N 的總位數)
  • y = (N 出現幾次質數位數) / (N 的總位數)
  • z = (N 出現幾次小於 5 的奇數位數) / (N 的總位數)
  • 化簡分數，保證測資只會產生 0, 1/2, 1 三種情況
  • 得到 (x, y, z)。接著，再計算一個向量 (vx, vy, vz)
    • vx = N 的第一位數 / N 的第二位數
    • vy = N 的第三位數 / N 的第四位數
    • vz = N 的第五位數 / N 的第六位數
  • 內積 (x, y, z)(vx, vy, vz) = x * vx + y * vy + z * vz 化簡若發生分子為合數 (非質數非 1 的數)，則保證下一個房間是安全的。

例如給定數字

1
2
3
4
5
6
7
8
9
10
11
N = 24556789
x = |[2, 4, 6, 8]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 1/2
y = |[2, 5, 5, 7]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 1/2
z = |[]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 0
vx = 2 / 4 = 1 / 2
vy = 5 / 5 = 1
vz = 6 / 7
x * vx + y * vy + vz = 3 / 4, 3 is prime, FATAL
1
2
3
4
5
6
7
8
9
10
11
N = 74974652
x = |[4, 4, 6, 2]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 1/2
y = |[7, 7, 5, 2]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 1/2
z = |[]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 0
vx = 7 / 4
vy = 9 / 7
vz = 4 / 6 = 2 / 3
x * vx + y * vy + vz = 7 / 8 + 9 / 14 = 85 / 56, 85 is not prime, SAFE.

Sample Input

1
2
24556789
74974652

Sample Output

1
2
3
4
1/2 1/2 0
FATAL
1/2 1/2 0
SAFE

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
151
152
153
154
155
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
#include <assert.h>
using namespace std;
struct Frac {
    long long x, y;
    Frac(long long a = 0, long long b = 1) {
        x = a, y = b;
        normal();
    }
    void normal() {
        if (y < 0)  x = -x, y = -y;
        long long g = llgcd(x, y);
        x /= g, y /= g;
        if (y < 0)  x = -x, y = -y;
    }
    long long llgcd(long long x, long long y) const {
    	if (x == 0)	return y;
    	if (y == 0)	return x;
        long long t;
        while (x%y)
            t = x, x = y, y = t % y;
        return y;
    }
    Frac operator-(const Frac &a) const {
        long long va = 0, vb = a.y / llgcd(y, a.y) * y;
        va = vb / y * x - vb / a.y * a.x;
        return Frac(va, vb);
    }
    Frac operator+(const Frac &a) const {
        long long va = 0, vb = a.y / llgcd(y, a.y) * y;
        va = vb / y * x + vb / a.y * a.x;
        return Frac(va, vb);
    }
    Frac operator*(const Frac a) const {
        long long g1 = llgcd(x, a.y), g2 = llgcd(a.x, y);
        long long va = 0, vb = 0;
        va = (x / g1) * (a.x / g2);
        vb = (y / g2) * (a.y / g1);
        return Frac(va, vb);
    }
    Frac operator/(const Frac a) const {
        long long g1 = llgcd(y, a.y), g2 = llgcd(x, a.x);
        long long va = 0, vb = 0;
        va = (a.y / g1) * (x / g2);
        vb = (y / g1) * (a.x / g2);
        return Frac(va, vb);
    }
    bool operator==(const Frac &a) const {
        return x - a.x == 0 && y - a.y == 0;
    }
    bool operator<(const Frac &a) const {
        return x * a.y < a.x * y;
    }
    void print() {
        if (y == 1)
            printf("%lld", x);
        else
            printf("%lld/%lld", x, y);
    }
};
Frac getX(char s[]) {
    int a = 0, b = 0;
    for (int i = 0; s[i]; i++) {
        a += (s[i] - '0')%2 == 0;
        b ++;
    }
    return Frac(a, b);
}
Frac getY(char s[]) {
    int a = 0, b = 0;
    for (int i = 0; s[i]; i++) {
        int d = s[i] - '0';
        if (d == 2 || d == 3 || d == 5 || d == 7)
            a++;
        b ++;
    }
    return Frac(a, b);
}
Frac getZ(char s[]) {
    int a = 0, b = 0;
    for (int i = 0; s[i]; i++) {
        int d = s[i] - '0';
        if (d < 5 && d%2 == 1)
            a++;
        b ++;
    }
    return Frac(a, b);
}
int getTestXYZ(char s[], Frac &x, Frac &y, Frac &z) {
    int n = (int) strlen(s);
    if (s[1%n] == '0' || s[3%n] == '0' || s[5%n] == '0')
        return 0;
    x = Frac(s[0%n] - '0', s[1%n] - '0');
    y = Frac(s[2%n] - '0', s[3%n] - '0');
    z = Frac(s[4%n] - '0', s[5%n] - '0');
    return 1;
}
int isprime(int x) {
    if (x == 1)
        return 0;
    for (int i = 2; i * i <= x; i++)
        if (x%i == 0)
            return 0;
    return 1;
}
int main() {
    char s[64];
    while (scanf("%s", s) == 1) {
        Frac x = getX(s), y = getY(s), z = getZ(s);
        Frac rx, ry, rz;
        x.print(), printf(" ");
        y.print(), printf(" ");
        z.print(), printf("\n");
        
        assert(x == Frac(0, 1) || x == Frac(1, 2) || x == Frac(1, 1));
        assert(y == Frac(0, 1) || y == Frac(1, 2) || y == Frac(1, 1));
        assert(z == Frac(0, 1) || z == Frac(1, 2) || z == Frac(1, 1));
        int f = getTestXYZ(s, rx, ry, rz);
        if (!f) {
        	assert(false);
        	continue;
        }
//        rx.print(), printf(" ");
//        ry.print(), printf(" ");
//        rz.print(), printf("\n");
        
        Frac dot = rx * x + ry * y + rz * z;
        if (!isprime((int)dot.x) && dot.x != 1) {
            puts("SAFE");
        } else {
            puts("FATAL");
        }
//        dot.print();
//        puts("");
    }
    return 0;
}
/*
 18540
 385
 1222 
 123456
 1234
 24556789
 74974652
*/
Read More +
解題區/解題區 - UVa

UVa 715 - Substitution Cipher

Problem

給一串加密過後的字典，其這一段字典按照原先的字典順序。假設只使用小寫字母的前 k 個單字，請問是否能正確解密，並且輸出明文是什麼。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
cad
aac
bca
bdac

Output

1
2
abcde
Message cannot be decrypted.

Solution

給定加密過後的字典，可以做相鄰的單詞比較，來得到字母間的大小關係，藉由拓撲排序得到與原先字母的對應關係。為了要正確解密，檢查拓撲過程中的瓶頸，相當於當前 queue 的大小為 1 來保證這個字母的對應關係。若不是瓶頸，則存在模稜兩可的解密。

由於密文不會使用所有的字母，只需要考慮密文使用的字母都能正確解密即可，意即前 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
#include <stdio.h> 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
char word[1024][1024], msg[1024];
char sbox[128];
int sfail[128];
int buildGraph(int n, int m)  {
    vector<int> g[128];
    int indeg[128] = {};
    for (int i = 1; i < n; i++) {
        int p = i-1, q = i;
        for (int j = 0; word[p][j] && word[q][j]; j++) {
            if (word[p][j] != word[q][j]) {
                g[word[p][j]].push_back(word[q][j]);
                indeg[word[q][j]]++;
                break;
            }
        }
    }
    
    deque<int> Q;
    for (int i = 'a'; i < 'a' + m; i++) {
        if (indeg[i] == 0) 
            Q.push_front(i);
    }
            
    int fail[128] = {}, order[128], ocnt = 0, u;
    while (!Q.empty()) {
        u = Q.front(), Q.pop_front();
        if (Q.size() >= 1) {
            for (deque<int>::iterator it = Q.begin();
                it != Q.end(); it++)
                fail[*it] = 1;
        }
        order[ocnt++] = u;
        for (int i = 0; i < g[u].size(); i++) {
            if (--indeg[g[u][i]] == 0) {
                Q.push_back(g[u][i]);
            }
        }
    }
    for (int i = 'a'; i < 'a' + m; i++)
        if (indeg[i] > 0)
            sfail[i] = 1;
        
    for (int i = 0; i < 128; i++)
        sbox[i] = i;
    for (int i = 0; i < ocnt; i++)
        sbox[order[i]] = 'a' + i, sfail[order[i]] = fail[order[i]];
    return 1;
}
int decode(char msg[]) {
    for (int i = 0; msg[i]; i++) {
        if (sfail[msg[i]])
            return 0;
        msg[i] = sbox[msg[i]];
    }
    return 1;
}
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &m, &n);
        for (int i = 0; i < n; i++)
            scanf("%s", word[i]);
        while (getchar() != '\n');
        gets(msg);
        
        buildGraph(n, m);
        int f = decode(msg);
        if (!f) {
            puts("Message cannot be decrypted.");
        } else {
            puts(msg);
        }
    }
    return 0;
}
/*
tricky case:
1
5 5
a
eb
eec
eeed
eeee
e 
*/
Read More +
解題區/解題區 - UVa

UVa 265 - Dining Diplomats

Problem

有 10 個外交官，各自代表自己的國家，並且也存在他們擅長的語言。現在 10 個外交官圍成一桌，相鄰的兩個外交官必須有相同語言，同時彼此的國家要是邦交關係。

提出一種可行的做法。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF USA GBR FRA FRG
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
TLC ADBE TQA DAO FHH NUW FAB PSR FEQ QPA KCW
TQA EB TLC DAO PSR FEQ KCW
DAO B TLC TQA FHH FAB PSR FEQ QPA KCW
FHH B TLC DAO PSR KCW
NUW DBE TLC
FAB D TLC DAO PSR FEQ QPA
PSR AC TLC TQA DAO FHH FAB QPA
FEQ CB TLC TQA DAO FAB QPA
QPA D TLC DAO FAB PSR FEQ KCW
KCW AE TLC TQA DAO FHH QPA

Output

1
2
3
4
5
6
7
8
9
10
11
12
1 F USA E
2 E CHN E
3 E GBR E
4 E KOR E
5 E ISR H
6 H JPN G
7 G POR E
8 E FRG R
9 R USR F
10 F FRA F
NO SOLUTION EXISTS

Solution

簡單的銷售員旅遊問題 (TSP: Travelling salesman problem)，這裏使用動態規劃來完成，殺雞用牛刀，窮舉 O(10!) 也許是可行的。定義 dp[2^n][n] = dp[i][j] 表示當前經過的狀態 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
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
#include <stdio.h> 
#include <string.h>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <assert.h>
#include <algorithm>
using namespace std;
struct State {
    string name, lang;
    set<string> g;
    int lang_mask[128];
    int read() {
        string line;
        if (getline(cin, line)) {
            assert(line.length() > 0);
            g.clear();
            stringstream sin(line);
            sin >> name >> lang;
            while (sin >> line)
                g.insert(line);
            
            g.insert(name); // what the fuck, same country in test data.
            memset(lang_mask, 0, sizeof(lang_mask));
            for (int i = 0; i < lang.length(); i++)
                lang_mask[lang[i]] = 1;
            return 1;
        } else {
            return 0;
        }
    }
    int hasCommon(const State &a) {
        for (int i = 0; i < 128; i++)
            if (lang_mask[i] && a.lang_mask[i])
                return 1;
        return 0;
    }
    char common(const State &a) {
        for (int i = 0; i < 128; i++)
            if (lang_mask[i] && a.lang_mask[i])
                return i;
        return '-';
    }
} C[10];
int g[10][10];
int dp[1<<10][10], from[1<<10][10];
int tsp(int u, int last) {
    if (dp[u][last] != -1)	return dp[u][last];
    int &ret = dp[u][last];
    ret = 0;
    for (int i = 0; i < 10; i++) {
        if (((u>>i)&1) && g[last][i]) {
            int f = tsp(u^(1<<i), i);
            if (f) {
                from[u][last] = i;
                return ret = 1;				
            }
        }
    }
    return ret;
}
int main() {
    while (true) {
        for (int i = 0; i < 10; i++) {
            if (!C[i].read())
                return 0;
        }
        
        memset(g, 0, sizeof(g));
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (C[i].g.count(C[j].name) && C[j].g.count(C[i].name) 
                    && C[i].hasCommon(C[j])) {
                    g[i][j] = 1;
                }
            }
        }
        
//		for (int i = 0; i < 10; i++, puts(""))
//			for (int j = 0; j < 10; j++)
//				printf("%d ", g[i][j] > 0);
        
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 1;
        int flag = tsp((1<<10)-1, 0);
        if (flag) {
            int p = (1<<10)-1, q = 0;
            int seat[10];
            for (int i = 0; i < 10; i++) {
                seat[i] = q;
                q = from[p][q];
                p = p^(1<<q);
            }
            for (int i = 0; i < 10; i++) 
                printf("%d %c %s %c\n", i+1, C[seat[i]].common(C[seat[(i-1+10)%10]]), 
                    C[seat[i]].name.c_str(), C[seat[i]].common(C[seat[(i+1+10)%10]]));
        } else {
            puts("NO SOLUTION EXISTS");
        }
        puts("");
        
        while (getchar() != '\n');
    }
    return 0;
}
/*
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF USA GBR FRA FRG
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
TLC ADBE TQA DAO FHH NUW FAB PSR FEQ QPA KCW
TQA EB TLC DAO PSR FEQ KCW
DAO B TLC TQA FHH FAB PSR FEQ QPA KCW
FHH B TLC DAO PSR KCW
NUW DBE TLC
FAB D TLC DAO PSR FEQ QPA
PSR AC TLC TQA DAO FHH FAB QPA
FEQ CB TLC TQA DAO FAB QPA
QPA D TLC DAO FAB PSR FEQ KCW
KCW AE TLC TQA DAO FHH QPA
*/
Read More +
解題區/解題區 - UVa

UVa 1548 - The Game of Master-Mind

Problem

擴充版的 1A1B 問題，A 表示猜的數列有多少位置正確，B 表示有多少位置錯，但使用的數字有在正確答案中。現在考慮使用的數字不只有 0 - 9，將會使用 1 - C，同時數列長度為 P，又給定當前的猜測情況，已知數種數列得到的 AB。

找一組滿足所有猜測結果，字典順序最小的那一組答案。

Input

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

Output

1
2
3
1 1 1 3
You are cheating!
9 9 9 9 9 9 9 9

Solution

原題使用黑色和白色數量分別表示 AB。

現在考慮回過頭來思考 A B 如何計算。A 就是序列的交集個數，而 B 是集合的交集個數扣除 A 的答案。

這麼一來，窮舉過程中統計序列交集和集合交集會更為方便。依序窮舉每一位的答案，過程中檢查是否存在 A 或 B 超過某一組猜測。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXM = 128;
const int MAXP = 11;
const int MAXC = 128;
int P, C, M;
int B[MAXM], W[MAXM], G[MAXM][MAXP], CG[MAXM][MAXC];
int path[MAXP], bcnt[MAXM], bwcnt[MAXM], CGcnt[MAXC];
// B[i] = |vector_intersection(G, S)|
// W[i] = |set_intersection(G, S)| - B[i]
// ===>|set_intersection(G, S)| = B[i] + W[i]
int checkValid(int p, int c) {
    for (int i = 0; i < M; i++) {
        if (G[i][p] == c && bcnt[i] == B[i])
            return 0; // BLACK exceeded
        if (CGcnt[c] < CG[i][c] && bwcnt[i] == B[i] + W[i])
            return 0; // |set_intersection(G, S)| > B[i] + W[i]
    }
    return 1;
}
void remove(int p, int c) {
    for (int i = 0; i < M; i++) {
        if (G[i][p] == c)
            bcnt[i]++;
        if (CGcnt[c] < CG[i][c])
            bwcnt[i]++;
    }
    CGcnt[c]++;
}
void resume(int p, int c) {
    for (int i = 0; i < M; i++) {
        if (G[i][p] == c)
            bcnt[i]--;
        if (CGcnt[c] <= CG[i][c])
            bwcnt[i]--;
    }
    CGcnt[c]--;
}
int dfs(int idx) {
    if (idx == P) {
        int ok = 1;
        for (int i = 0; i < M && ok; i++)
            ok &= bcnt[i] == B[i] && bwcnt[i] == B[i] + W[i];
        return ok;
    }
    for (int i = 1; i <= C; i++) {
        if (!checkValid(idx, i))
            continue;
        remove(idx, i);
        path[idx] = i;
        if (dfs(idx+1))
            return 1;
        resume(idx, i);
    }
    return 0;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &P, &C, &M);
        for (int i = 0; i < M; i++) {
            memset(CG[i], 0, sizeof(CG[i]));
            for (int j = 0; j < P; j++) {
                scanf("%d", &G[i][j]);
                CG[i][G[i][j]]++;
            }
            scanf("%d %d", &B[i], &W[i]);
        }
        
        memset(bcnt, 0, sizeof(bcnt));
        memset(bwcnt, 0, sizeof(bwcnt));
        memset(CGcnt, 0, sizeof(CGcnt));
        int f = dfs(0);
        if (f) {
            for (int i = 0; i < P; i++)
                printf("%d%c", path[i], i == P-1 ? '\n' : ' ');
        } else {
            puts("You are cheating!");
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10748 - Knights Roaming

Problem

給予無限大盤面上，每一個騎士擁有自己的起始位置、限定走 k 步，請問盤面上有多少騎士可以抵達的點座標。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
5
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
5
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
4
-1 -1 2
2 2 1
3 3 3
4 4 3
0

Output

1
2
3
5
33
155

Solution

對於所有騎士同時運行 Bfs 很容易造成 TLE。這裏介紹其中一種優化策略，對於獨立的騎士直接計算可抵達的地點總數 (預處理只有一個騎士的盤面的答案)。

獨立騎士能步行的範圍為曼哈頓距離在 3 k[i] 內的所有點，對於兩兩騎士做交集判定，若不存在任何重疊區域，則該騎士為獨立。

為了加速運算，可以使用 hash 來防止重複運算，或者平移座標到可以在 500 x 500 內的陣列中做 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
#include <stdio.h> 
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
const unsigned int hash_mod = 100019;
set< pair<int, int> > R[hash_mod];
unsigned int hash(int x, int y) {
    unsigned int a = 63689, b = 378551;
    unsigned int value = 0;
    int c[4] = {x, y, y, x};
    for (int i = 0; i < 4; i++) {
        value = value * a + c[i];
        a *= b;
    }
    return value % hash_mod;
}
const int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
int bfs(int sx[], int sy[], int dstep[], int n) {		
    for (int i = 0; i < hash_mod; i++)
        R[i].clear();
        
    queue<int> X[64], Y[64];
    int step, tx, ty, x, y;
    
    for (int i = 63; i >= 0; i--) {
        for (int j = 0; j < n; j++) { 
            if (dstep[j] == i) {		
                X[i].push(sx[j]), Y[i].push(sy[j]);
                R[hash(sx[j], sy[j])].insert(make_pair(sx[j], sy[j]));
            } 
        } 
        while (!X[i].empty()) {
            x = X[i].front(), X[i].pop();
            y = Y[i].front(), Y[i].pop();
            
            if (i == 0)	continue;
            for (int k = 0; k < 8; k++) {
                tx = x + dx[k], ty = y + dy[k];
                if (!R[hash(tx, ty)].count(make_pair(tx, ty))) {
                    R[hash(tx, ty)].insert(make_pair(tx, ty));
                    X[i-1].push(tx), Y[i-1].push(ty);
                }
            }
        }
    }	
    
    int ret = 0;	
    for (int i = 0; i < hash_mod; i++)
        ret += R[i].size();
    return ret;
}
int main() {
    int x[64], y[64], step[64];
    int n;
    int h[64] = {};
    for (int i = 0; i <= 50; i++) {
        x[0] = y[0] = 0, step[0] = i;
        h[i] = bfs(x, y, step, 1);
    }
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%d %d %d", &x[i], &y[i], &step[i]);
        
        int independent = 0;
        for (int i = 0; i < n; i++) {
            int d = 0x3f3f3f3f;
            for (int j = 0; j < n; j++) {
                if (i == j)	continue;
                d = min(d, max(abs(x[i] - x[j]) + abs(y[i] - y[j]) - 3 * (step[i] + step[j]), 0));
            }
            if (d > 0)
                independent += h[step[i]], step[i] = -1;
        }
                
        int ret = bfs(x, y, step, n) + independent;
        printf("%d\n", ret);
    }
    return 0;
}
/*
5
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
5
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
4
-1 -1 2
2 2 1
3 3 3
4 4 3
30
0 0 50
1 1000 50
2 2000 50
3 3000 50
4 4000 50
5 5000 50
6 6000 50
7 7000 50
8 8000 50
9 9000 50
10 10000 50
11 11000 50
12 12000 50
13 13000 50
14 14000 50
15 15000 50
16 16000 50
17 17000 50
18 18000 50
19 19000 50
20 20000 50
21 21000 50
22 22000 50
23 23000 50
24 24000 50
25 25000 50
26 26000 50
27 27000 50
28 28000 50
29 29000 50
*/
Read More +
解題區/解題區 - UVa

UVa 10725 - Triangular Square

Problem

給三角形的三邊，放置一個最大面積的正方形於三角形中。

求最大面積為何。

Input

1
2
3
2
6 6 6
2 2 2

Output

1
2
7.754051
0.861561

Solution

把三角形的最大邊找到，考慮是鈍角還是銳角三角形，接著把正方形的某一邊貼在三角形上，用幾何計算三角形的三點座標，拉 45 度分角線得到正方形另一點座標，計算正方形邊長。

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 <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.h>
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 {
    	return !(a == *this);
    }
    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);
    }
};
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
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;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) < 0 &&
        cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) < 0)
        return 1;
    return 0;
}
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());
}
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 inPolygon(vector<Pt> &p, Pt q) {
    int i, j, cnt = 0;
    int n = p.size();
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
        q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
        cnt++;
    }
    return cnt&1;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
        area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
    double a, b, c, v;
    a = as.y - ae.y, b = ae.x - as.x;
    c = - (a * as.x + b * as.y);
    v = a * p.x + b * p.y + c;
    return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
int main() {
    int testcase, e[3];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &e[0], &e[1], &e[2]);
        sort(e, e+3);
        
        double sq_len = 0;
        
        if (e[0]*e[0] + e[1]*e[1] <= e[2]*e[2]) { // right/obtuse triangle
            double a = e[2], b = e[1], c = e[0]; // a > b > c
            double theta = acos((a*a + b*b - c*c)/(2*a*b));
            Pt A = rotateRadian(Pt(1, 0), theta) * b;
            Pt vAC = rotateRadian(Pt(0, 0) - A, pi/4), vAB = rotateRadian(Pt(a, 0) - A, -pi/4);
            Pt p = getIntersect(Seg(Pt(0, 0), Pt(a, 0)), Seg(A + vAC, A));
            Pt q = getIntersect(Seg(Pt(0, 0), Pt(a, 0)), Seg(A + vAB, A));
            sq_len = max((A - p).length(), (A - q).length()) / sqrt(2);	
        } else {
            double a = e[2], b = e[1], c = e[0]; // a > b > c
            double s = (a+b+c)/2;
            double area = sqrt(s*(s-a)*(s-b)*(s-c));
            double h = 2 * area / a;
            h = 2 * area / b;
            sq_len = max((b*h) / (b + h), sq_len);
            h = 2 * area / c;
            sq_len = max((c*h) / (c + h), sq_len);
        }
            double a = e[2], b = e[1], c = e[0]; // a > b > c
            double s = (a+b+c)/2;
            double area = sqrt(s*(s-a)*(s-b)*(s-c));
            double h = 2 * area / a;
            // h - x : h = x : a
            // x = ah / (h + a) 
            sq_len = max((a*h) / (a + h), sq_len);
    
        printf("%.6lf\n", sq_len * sq_len);
    }
    return 0;
}
/*
3
3 4 5
6 4 3
6 7 8
2
6 6 6
2 2 2
*/
Read More +
解題區/解題區 - UVa

UVa 10615 - Rooks

Problem

給一個 n x n 個棋盤，放置 * 於棋盤上，著色所有的 * 使得同行同列的 * 都是不同顏色。

使用最小顏色總數，給出一種可行解。

Input

1
2
3
4
5
6
7
8
9
10
11
2
2
*.
**
4
*.*.
*.*.
***.
..**

Output

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

Solution

最小著色數為同行同列的最多 * 總數
為了輸出可行解，進行二分匹配。對於著色座標 (row, column) = (i, j) 拉一條 i->j 的邊，匹配一條邊，相當於著色一個點。

假設最少著色數是 c，則進行補邊，使得二分圖的 X-Y 集合中的每一個點都是 degree = c。

進行 c 次的二分匹配，每一次匹配都是完美匹配，因符合性質｀degree = c。這一次的所有匹配邊 (i, j) 表示相同顏色。
每一次完美匹配，會將所有的 degree - 1，因此便能將所有邊使用完畢。這裏有 Hall’s marriage theorem 的意味在，來保證完美匹配的存在。

如果不補邊，每一次最大匹配若不是完美匹配，最大匹配會造成下一次匹配不一定是最大，c 次二分匹配後，會有殘留的邊！也就是造成點未著色。

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
// Hall's marriage theorem, bipartite graph matching, maxflow
// for all subset X sat. |X| <= |Neighborhood(X)| = |Y|
// 
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int testcase;
    int n, x, y;
    char s[128][128];
    
    scanf("%d", &testcase);
    while (testcase--) {
        
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%s", s[i]);
            
        vector<int> bigraph[128];
        int row_deg[128] = {}, col_deg[128] = {};
        int place_color[128][128];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == '*') {
                    row_deg[i]++, col_deg[j]++;
                    bigraph[i].push_back(j);
                }					
            }
        }
        
        int mx_colors = 0;
        for (int i = 0; i < n; i++) {
            mx_colors = max(mx_colors, row_deg[i]);
            mx_colors = max(mx_colors, col_deg[i]);
        }
        
        // increase edge, make perfect matching
        for (int i = 0; i < n; i++) {
            if (row_deg[i] < mx_colors) {
                for (int j = 0; j < n; j++) {
                    while (row_deg[i] < mx_colors && col_deg[j] < mx_colors) {
                        row_deg[i]++, col_deg[j]++;
                        bigraph[i].push_back(j);
                    }
                }
            }
        }
        
        // bipartite graph matching
        for (int color = 0; color < mx_colors; color++) {
            g.Init(2 * n + 2);
            int source = 2 * n, sink = 2 * n + 1;
            for (int i = 0; i < n; i++) {
                g.Addedge(source, i, 1), g.Addedge(i + n, sink, 1);
                for (int j = 0; j < bigraph[i].size(); j++)
                    g.Addedge(i, bigraph[i][j] + n, 1);
            }
            
            int matching = g.Maxflow(source, sink);
            assert(matching == n); // perfect matching
            // make sure, matching pair won't collision.
            for (int i = 0; i < n; i++) {
                for (Edge *p = g.adj[i]; p != NULL; p = p->next) {
                    int x = i, y = p->v, flow = p->flow;
                    if (flow == 0 && y - n >= 0 && y - n < n) {
                        // match x - (y - n) in bipartite graph
                        int r = x, c = y - n;
                        if (s[r][c] == '*')
                            place_color[r][c] = color;
                        // remove edge
                        bigraph[r].erase(find(bigraph[r].begin(), bigraph[r].end(), c));
                    }
                }
            }
        }
        
        for (int i = 0; i < n; i++)
            assert(bigraph[i].size() == 0);
        
        printf("%d\n", mx_colors);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == '*')	printf("%d", place_color[i][j] + 1);
                else				printf("%d", 0);
                printf("%c", j == n-1 ? '\n' : ' ');
            }
        }
    }
    return 0;
}
/*
9999
4
****
****
****
****
4
***.
.***
.**.
....
4
****
.*.*
..**
...*
4
*...
.*..
..*.
...*
4
*...
.*..
..*.
..*.
2
*.
**
4
*.*.
*.*.
***.
..**
*/
Read More +