解題區►解題區 - UVa

UVa 1105 - Coffee Central

Problem

給一個網格狀的地圖，每一個地點都有其相對應的人數，現在要建造一個咖啡廳，而咖啡廳所在位置可以引來在曼哈頓距離為 m 以內的所有網格上的人數。

對於每一組詢問，回報咖啡廳應該建在哪裡可以引來最多的人。

Sample Input

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

Sample Output

1
2
3
4
Case 1:
3 (3,4)
4 (2,2)
5 (3,1)

Solution

由於單一組詢問數量不到 20，想必可以使用 O(n^2) 去應付每一組詢問。

窮舉每一個可能的位置，並且去計算該位置能引來多少的人。為了加速統計人數，曼哈頓距離內，是一個 45 度的正方形，紀錄上非常不方便。利用旋轉矩陣，將整個平面紀錄轉 45 度，讓每一次的區域統計變成平行於兩軸的區域，如此一來就可以在 O(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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 2048;
int sum[MAXN][MAXN];
void rotate(int x, int y, int &tx, int &ty, int dx, int dy) {
	tx = x - y + dy, ty = x + y;
}
void query(int limit, int dx, int dy) {
	int ret = 0, ret_x = 1, ret_y = 1;
	int tx, ty;
	for (int j = 1; j <= dy; j++) {
		for (int i = 1; i <= dx; i++) {
			rotate(i, j, tx, ty, dx, dy);
			int lx, rx, ly, ry, cnt;
			lx = max(tx - limit, 1);
			ly = max(ty - limit, 1);
			rx = min(tx + limit, dx + dy);
			ry = min(ty + limit, dx + dy);
			cnt = sum[rx][ry] - sum[rx][ly-1] - sum[lx-1][ry] + sum[lx-1][ly-1];
			if (cnt > ret) {
				ret = cnt, ret_x = i, ret_y = j;
			}
		}
	}
	printf("%d (%d,%d)\n", ret, ret_x, ret_y);
}
int main() {
	int dx, dy, n, q;
	int x, y, tx, ty, limit, cases = 0;
	while (scanf("%d %d %d %d", &dx, &dy, &n, &q) == 4 && dx) {
		// rotate matrix, rotate 45 degree
//		for (int i = 1; i <= dx; i++) {
//			for (int j = 1; j <= dy; j++) {
//				printf("(%d %d) -> (%d %d)\n", i, j, i - j + dy, i + j);
//			} 
//		}
		memset(sum, 0, sizeof(sum));
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &x, &y);
			rotate(x, y, tx, ty, dx, dy);
			sum[tx][ty]++;
		}
		
		for (int i = 1; i <= dx + dy; i++) {
			for (int j = 1, s = 0; j <= dx + dy; j++) {
				s += sum[i][j];
				sum[i][j] = sum[i-1][j] + s;
			}
		}
		
		printf("Case %d:\n", ++cases);
		for (int i = 0; i < q; i++) {
			scanf("%d", &limit);
			query(limit, dx, dy);
		}
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 10476 - Spam or Not Spam

Problem

判斷訊息是否為垃圾訊息。

給數組垃圾訊息、非垃圾訊息，從中統計語言的出現頻率。例如 ABCDEFG 取 k-shingle 中 k = 3，那麼總共出現 ABC、BCD、CDE、DEF … 等。

接著按照題目給定的公式，計算輸入的訊息離垃圾訊息比較接近、還是非垃圾訊息。

n-gram 通常指的是以單詞 (word) 為切割單位，而 k-shingle 則是以字符 (char) 為切割單位。在巨量資料的開放課程中，以 shingle 去描述這樣的切割方式。

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
2 1 1
AAAA
BBBB CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE
2 1 2
AAAA
BBBB CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE
AAABB
ENDMESSAGE
0 0 0

Sample Output

1
2
3
4
5
6
7
8
Set 1:
0.21822 0.73030
non-spam
Set 2:
0.21822 0.73030
non-spam
0.21822 0.73030
non-spam

Solution

相當有趣的題目，終於把自然語言學習到的部分拿出來玩。但可惜題目沒有巨量資料那樣瘋狂，用 hash 去失真的操作，由於記憶體不夠，用 1-pass/2-pass 找 frequent items 之類的。

為了加速運算，改成 hash 會比較快，但只要一碰撞輸出機率時就會炸掉，所以還是別貿然嘗試。

特別用了 std::inner_product 來寫中間的數學運算，但仔細想想如果是兩個 std::map 要進行 std::inner_product() 仍然會因為元素不見得都會在兩個的 key set 而無法運作。std::inner_product 內建實作中只有單純的迭代，用在 vector 類型比較合適。

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
// NLP, n-gram, shingle
#include <stdio.h> 
#include <map>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <string.h>
using namespace std;
int map_product(pair<string, int> l, pair<string, int> r) {
	return l.second * r.second;
}
class Stat {
public:
	int kShingle;
	int sqsum;
	map<string, int> count;
	void init(int k) {
		kShingle = k, sqsum = 0;
		count.clear();
	}
	string toKey(string &s) { // retain for hash function
		return s;
	}
	void add(char s[]) {
		if (s[0] == '\0' || s[1] == '\0')	
			return;
		char end = '\0';
		for (int i = 2; s[i]; i++) {
			swap(s[i+1], end);
			string shingle = s+i-2;
			swap(s[i+1], end);
			count[toKey(shingle)] ++;
		}
	}
	void flush() {
		sqsum = inner_product(count.begin(), count.end(), count.begin(), 0,
           plus<int>(), map_product);
	}
	double distance(Stat &other) {
		double sum = 0;
		for (map<string, int>::iterator it = count.begin(), jt;
			it != count.end(); it++) {
			jt = other.count.find(it->first);
			if (jt != other.count.end()) {
				sum += it->second * jt->second;
			}
		}
		return (double) sum / sqrt((double) sqsum * other.sqsum);
	}
} spam, nonspam, msg;
const int MAXN = 1048576;
char buf[MAXN];
int main() {
	int cases = 0;
	int n, m, q;
	while (scanf("%d %d %d", &n, &m, &q) == 3 && n + m + q) {
		
		while (getchar() != '\n');
		spam.init(3), nonspam.init(3);
		
		for (int i = 0; i < n; i++) {
			while(gets(buf) && strcmp("ENDMESSAGE", buf))
				spam.add(buf);
		}
		for (int i = 0; i < m; i++) {
			while(gets(buf) && strcmp("ENDMESSAGE", buf))
				nonspam.add(buf);
		}
		spam.flush(), nonspam.flush();
			
		printf("Set %d:\n", ++cases);
		for (int i = 0; i < q; i++) {
			msg.init(3);
			while(gets(buf) && strcmp("ENDMESSAGE", buf))
				msg.add(buf);
			msg.flush();
			
			double spam_dist = msg.distance(spam);
			double nonspam_dist = msg.distance(nonspam);
			printf("%.5lf %.5lf\n", spam_dist, nonspam_dist);
			puts(spam_dist > nonspam_dist + 1e-10 ? "spam" : "non-spam");
		}
	}
	return 0;
}
/*
2 1 1
AAAA
BBBB CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE
2 1 2
AAAA
BBBB CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE
AAABB
ENDMESSAGE
0 0 0
*/
Read More +
解題區►解題區 - UVa

UVa 10498 - Happiness

Problem

每個人對於每種食材都有其滿意度，目標滿意度總和不超過上限。

準備一人份食材時，每單位的食材都各自有不同的花費，盡可能花最多的錢。

請問總共要花多少錢。

Sample Input

1
2
3
4
5
3 3
1 0.67 1.67
1 2 1 430
3 0 2 460
1 4 0 420

Sample Output

1
Nasa can spend 1354 taka.

Solution

每個人都花費相同的金額，因此把目標函數最大化後，乘上總人數即可。

現在要把問題轉換成線性規劃的模型，隨後套用 Simplex algorithm (單純形法)，可以參考 李宇骞《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》的簡報，概略說明模型的架構。資料網路上很多，不談論標準的處理程序。

接著閒聊自己的看法。

利用數形轉換的概念，從幾何概念下手，從三個變數來看，單純形法相當於在一個空間上，拿一個物體與平面找接觸，為了使目標函數最大化，會將物體表面的頂點帶入嘗試。

但是要將所有頂點找出來是相當消耗時間，因此爬行法可能會稍微好一點，也就是說，沿著物體表面，藉由一條邊爬行到更好位置上的頂點。由於線性約束，使得物體一定是凸多面體，在更高維度也是一樣的，不斷地爬升到更好的頂點後，最後一定會在最高點停止。

為了使爬行速度加快，每一次找爬升最多的鄰近點，相當於根據某一個約束，盡可能放大某一個維度上的變數 (有可能會將別的變數變小)，使得目標函數增加的值盡可能地多。根據原始的約束寫法，要找到計算仍然相當困難。

定義一個轉軸操作，讓整個問題的空間座標進行變換，方便撰寫。

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
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 64;
const int MAXM = 128;
const double eps = 1e-10, INF = 1e+30;
/*
	n: #variable
	m: #inequality constraint
	#inequality constraint format : \sum{a(j, i) xi} <= bj
	for all xi >= 0
 */
class Simplex {
public:
    int n, m;
    int N[MAXN], M[MAXM];
    double a[MAXM][MAXN], b[MAXM], c[MAXN];
    double xval[MAXN], z;
    void init(int n, int m) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        memset(xval, 0, sizeof(xval));
        z = 0;
        this->n = n + m;
        this->m = m;
        
        for (int i = 0; i < m; i++)
            a[i][n+i] = 1;
        for (int i = 0; i < n; i++)
            N[i] = i;
        for (int i = 0; i < m; i++)
            M[i] = n + i;
    }
    int cmpZero(double v) {
        if (fabs(v) < eps)	return 0;
        return v < 0 ? -1 : 1;
    }
    void compute_xval() {
        for (int i = 0; i < n - m; i++) {
            xval[i] = 0;
            for (int j = 0; j < m; j++) {
                if (M[j] == i)
                    xval[i] = b[j];
            }
        }
    }
    void print() {
        printf("c ");
        for (int i = 0; i < n; i++)
            printf("%6.3lf ", c[i]);
        printf("%6.3lf\n", z);
        
        for (int i = 0; i < m; i++) {
            printf("a ");
            for (int j = 0; j < n; j++)
                printf("%6.3lf ", a[i][j]);
            printf("%6.3lf\n", b[i]);
        }
        puts("--");
        
        compute_xval();
        printf("x ");
        for (int i = 0; i < n - m; i++)
            printf("%6.3lf ", xval[i]);
        puts("");
    }
    void pivot(int row, int col) {
        double e = a[row][col];
        // normalization
        b[row] /= e;
        for (int i = 0; i < n; i++)
            a[row][i] /= e;
        // gaussian elimination
        for (int i = 0; i < m; i++) {
            if (i == row)
                continue;
            double t = a[i][col];
            b[i] = b[i] - t * b[row];
            for (int j = 0; j < n; j++)
                a[i][j] = a[i][j] - t * a[row][j];
        }
        z -= b[row] * c[col];
        
        double t = c[col];
        for (int i = 0; i < n; i++)
            c[i] = c[i] - t * a[row][i];
        swap(N[col], M[row]);
//        print();
    }
    void simplex() {
        double mx;
        int select_col, select_row, mn_row;
        // climb
        do {
            mx = -INF, select_col = select_row = mn_row = -1;
            for (int i = 0; i < n; i++) {
                if (cmpZero(c[i]) > 0) {
                    double mn = INF;
                    // find minmum increase with inequality constraint
                    for (int j = 0; j < m; j++) {
                        if (cmpZero(a[j][i]) > 0) {
                            if (b[j] / a[j][i] < mn)
                                mn = b[j] / a[j][i], mn_row = j;
                        }
                    }
                    // find maxmum climb with axis
                    if (mx < mn * c[i]) {
                        mx = mn * c[i];
                        select_col = i, select_row = mn_row;
                    }
                }
            }
            if (select_col != -1)
                pivot(select_row, select_col);
        } while (select_col != -1);
        
        compute_xval();
    }
} g;
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        g.init(n, m);
        
        for (int i = 0; i < n; i++)
            scanf("%lf", &g.c[i]);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                scanf("%lf", &g.a[i][j]);
            scanf("%lf", &g.b[i]);
        }
        
        g.simplex();
        
//        for (int i = 0; i < n; i++) {
//            printf("x[%d] = %lf\n", i, g.xval[i]);
//        }
        printf("Nasa can spend %d taka.\n", (int) ceil(-g.z * m));
    }
    return 0;
}
/*
 Max x1 + 14*x2 + 6*x3
 s.t.
 x1 + x2 + x3 	<= 4
 x1              <= 2
 x3              <= 3
 3*x2   + x3     <= 6
 x1 , x2 , x3 , x4 , x5 , x6 , x7 >= 0
 
 3 4
 1 14 6
 1 1 1  4
 1 0 0  2
 0 0 1  3
 0 3 1  6
 
 2 2
 1 1
 2 1 12
 1 2 9
 
 2 2
 -1 -1
 2 1 12
 1 2 9
 
 3 3
 1 0.67 1.67
 1 2 1 430
 3 0 2 460
 1 4 0 420
 
 3 1
 30 10 20
 30 1 3 30
 
 3 3
 30 10 20
 30 1 3 30
 30 1 3 30
 30 1 3 30
 */
Read More +
解題區►解題區 - 其他題目

2015 Google Code Jam Round 1A

\感謝諸神們替蒟蒻翻譯 GCJ 題目，巨人們/，看完第一題就過了一個小時。

windows format to linux format 

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

題解

  • A. Mushroom Monster
  • B. Haircut
  • C. Logging

［A. Mushroom Monster］O(N)

坑爹的蘑菇蘑菇，友人 A 會偷偷增加盤子上的蘑菇，系統每十秒會記錄盤子上蘑菇數量，也就是說給定的序列是系統紀錄盤子上蘑菇的情況，而不是友人 A 放入的蘑菇。接著少兩策略的最少吃掉數量

吃蘑菇策略一，可以在任何時刻吃掉任何數量，策略二，在任何時刻都以某個速度吃蘑菇每秒 f 個，當盤子空的時候，停止餵食。貪心策略，策略一考慮友人 A 盡可能不加蘑菇，策略二考慮友人 A 盡可能讓盤子空，在最後一個時刻 (系統紀錄前) 才放入蘑菇。

［B. Haircut］O(N log N)

理髮師 i 剪一個人需要 Mi 秒，客人 j 呈現 queue 的訪問方式，當有理髮師閒置時，將客人 j 會排入理髮程序。在同一時刻，若存在多名理髮師閒置，編號小的客人優先選擇編號小的理髮師進行流程。請問當所在位置為 N 時，會被指派給哪位理髮師。

二分自己剪髮時間，利算 sum += floor(time / Mi) + 1，存在 sum >= N 時，表示理髮廳已經解決 sum 個人，並且已經理超過自己。找到最小的時間後，循序找一下適合的理髮師。presum += floor(time / Mi) + (time % Mi != 0)，找到前一個時刻 time - 1 結束瞬間完成的人數，隨後貪心找 time % Mi = 0 分配給 presum + 1 ~ N。

［C. Logging］O(2^N * N log N) -> O(N^2 log N)

松鼠在樹 i 上，請問要砍掉幾棵樹，才能讓自己的樹 i 位於森林邊緣。

最簡單的思路，使用的點集，做一次凸包，查找位於邊上的可能情況，需要凸包算法、線段上判定、bitmask，應付小測資專用。O(2^N * N log N)

接著考慮要砍點使得點 i 在凸包邊緣，那麼必然找到一條線通過點 i，其中一側具有最少的點數。因此對於每一個點 i 當作中心，對其他 N - 1 個點進行極角排序，掃描線算法找半平面 (180 度) 內最少的點數。O(N^2 log N)。

A code

GCJ20151A - Mushroom Monster
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
// Fucking English
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
	int testcase, n, cases = 0;
	long long A[1024];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		
		for (int i = 0; i < n; i++)
			scanf("%lld", &A[i]);
		
		long long retA = 0, retB = 0, mx = 0;
		for (int i = 1; i < n; i++) {
			if (A[i-1] - A[i] > 0) {
				retA += A[i-1] - A[i];
				mx = max(mx, A[i-1] - A[i]);
			}
		}
		for (int i = 0; i < n - 1; i++) {
			if (A[i] > mx)
				retB += mx;
			else
				retB += A[i];
		}
		
		printf("Case #%d: %lld %lld\n", ++cases, retA, retB);
	}
	return 0;
}
/*
4
4
10 5 15 5
2
100 100
8
81 81 81 81 81 81 81 0
6
23 90 40 0 100 9
*/

B code

GCJ20151A - Haircut
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
#include <stdio.h>
int main() {
	int testcase, cases = 0;
	int N, B;
	long long M[1024];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &B, &N);
		for (int i = 0; i < B; i++)
			scanf("%lld", &M[i]);
		
		long long l = 0, r = 100000LL * N, mid, time = 0;
		while (l <= r) {
			mid = (l + r)/2;
			long long cnt = 0;
			for (int i = 0; i < B; i++)
				cnt += mid / M[i] + 1;
			if (cnt >= N)
				r = mid - 1, time = mid;
			else
				l = mid + 1;
		}
		
		long long cnt = 0;
		int id = 0;
		
		for (int i = 0; i < B; i++)
			cnt += time / M[i] +(time % M[i] !=0);
		
		cnt = N - cnt;
//		printf("%lld %lld\n", cnt, time);
		for (int i = 0; i < B; i++) {
			if (time % M[i] == 0) {
				cnt--;
				if (cnt == 0)
					id = i;
			}
		}
		printf("Case #%d: %d\n", ++cases, id + 1);
	}
	return 0;
}

C code

small

GCJ20151A - 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
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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <assert.h>
#include <vector>
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());
}
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);
}
const double pi = acos(-1);
int cmpZero(double v) {
	if (fabs(v) > eps) return v > 0 ? 1 : -1;
	return 0;
}
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;
}
int main() {
	int testcase, cases = 0;
	int n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		Pt P[1024];
		for (int i = 0; i < n; i++)
			scanf("%lf %lf", &P[i].x, &P[i].y);
		
		int ret[16] = {};
		for (int i = 0; i < n; i++)
			ret[i] = n;
		for (int i = 0; i < (1<<n); i++) {
			int m = 0, cnt = 0;
			Pt a[32], ch[32];
			for (int j = 0; j < n; j++) {
				if ((i>>j)&1)
					a[m++] = P[j];
			}
			
			int cn = monotone(m, a, ch);
			for (int p = 0; p < n; p++) {
				if ((i>>p)&1)
				for (int j = 0, k = cn-1; j < cn; k = j++) {
					if (onSeg(ch[j], ch[k], P[p])) {
						ret[p] = min(ret[p], n - m);
					}
				}
			}
		}
		printf("Case #%d:\n", ++cases);
		for (int i = 0; i < n; i++)
			printf("%d\n", ret[i]);
	}
	return 0;
}

large

2015/05/15 修正極角排序誤差

Tricky Test Case

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
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

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
Case #1:
9
0
1
0
3
7
4
2
0
0
2
2
8
1
0
9
7
7
4
3
8
1
2
0
7
0
2
0
9
0

盡可能地少用 atan2()，使用外積的方式進行極角排序。

GCJ20151A - Logging[fast]
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;
}
Read More +
解題區►解題區 - UVa

UVa 1115 - Water Shortage

Problem

根據連通管原理，給定要灌入水的容積，請問最後水位的位置為何？

給定每個水槽的長寬高、以及離地面的高度。

Sample Input

1
2
3
4
5
6
7
8
1
4
11.0 7.0 5.0 1.0
15.0 6.0 4.0 1.0
 5.0 8.0 5.0 1.0
19.0 4.0 8.0 1.0
78.0

Sample Output

1
17.00

Solution

講到連通管原理，很容易想起帕斯卡原理 … 喵帕斯。

二分水位高度，計算容積與目標容積的差異。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h> 
#include <math.h>
#include <assert.h>
#include <algorithm>
using namespace std;
const int MAXN = 1024;
double LV[MAXN], H[MAXN], W[MAXN], D[MAXN], V;
void solve(int n, double V) {
	double l = 0, r = 0, mid;
	double sumV = 0;
	for (int i = 0; i < n; i++) {
		sumV += H[i] * W[i] * D[i];
		r = max(r, LV[i] + H[i]);
	}
	if (sumV < V) {
		puts("OVERFLOW");
		return ;
	}
	
	for (int it = 0; it < 100; it++) {
		mid = (l + r)/2;
		sumV = 0;
		for (int i = 0; i < n; i++) {
			if (mid < LV[i])	continue;
			sumV += W[i] * D[i] * min(H[i], mid - LV[i]);
		}
		if (sumV > V)
			r = mid;
		else
			l = mid;
	}
	printf("%.2lf\n", l);
}
int main() {
	int testcase, n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		assert(n < MAXN);
		for (int i = 0; i < n; i++)
			scanf("%lf %lf %lf %lf", &LV[i], &H[i], &W[i], &D[i]);
		scanf("%lf", &V);
	
		solve(n, V);
		if (testcase)	puts("");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1089 - Suffix-Replacement Grammars

Problem

限定修改後綴，請問至少需要幾次轉換能從起始字串轉換到目標字串。

Sample Input

1
2
3
4
5
6
7
8
9
10
AA BB 4 
A B 
AB BA 
AA CC 
CC BB 
A B 3 
A C 
B C 
c B 
.

Sample Output

1
2
Case 1: 2 
Case 2: No solution

Solution

一開始用 Bfs 下去搜索，發現狀態會是 O(2^len)，這麼轉換就不太行。

將語法中單詞、起始字串、目標字串的後綴按照長度分層，將從長度為 1 的轉換開始，依序完成到 len。將後綴建成一張圖，套用 floyd algorithm 找最少轉換次數。

1
2
A -> B, cost 1
Aaaaaa -> Abbbbb, cost aaaaa -> bbbbb

考慮長度 i 的轉換時，有可能存在給定的語法可以直接進行轉換，或者存在在長度 (i - 1) 時的最少轉換次數。

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
#include <stdio.h> 
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#include <assert.h>
using namespace std;
const int MAXS = 25;
const int MAXR = 105;
const int MAXN = 512;
map<string, int> Rmap[MAXS];
vector<string> Rvec[MAXS];
void addNode(string s) {
	int len = s.length(), label;
	if (!Rmap[len].count(s)) {
		label = Rmap[len].size();
		Rmap[len][s] = label;
		Rvec[len].push_back(s);
		assert(label < MAXN);
	}
}
// floyd
long long dist[MAXN][MAXN], preDist[MAXN][MAXN];
const long long INF = 1LL<<61;
int main() {
	string A, B, x, y;
	int M, N, cases = 0;
	while (cin >> A >> B >> M) {
		if (A == ".")
			return 0;
		set< pair<string, string> > rules;
		for (int i = 0; i < MAXS; i++)
			Rmap[i].clear(), Rvec[i].clear();
			
		for (int i = 0; i < M; i++) {
			cin >> x >> y;
			rules.insert(make_pair(x, y));
			for (int j = 0; j < x.length(); j++) {
				string s1 = x.substr(j), s2 = y.substr(j);
				addNode(s1), addNode(s2);
			}
		}
		
		N = A.length();
		for (int i = 0; i < N; i++) {
			string s1 = A.substr(i), s2 = B.substr(i);
			addNode(s1), addNode(s2);
		}
		
		for (int p = 1; p <= N; p++) {
			int n = Rmap[p].size();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == j)	
						dist[i][j] = 0;
					else {
						dist[i][j] = INF;
						if (rules.count(make_pair(Rvec[p][i], Rvec[p][j]))) {
							dist[i][j] = min(dist[i][j], 1LL); // rule A -> B, cost 1
						}
						if (p > 1 && Rvec[p][i][0] == Rvec[p][j][0]) { // node Aaaaaa -> Abbbbb, cost aaaaa -> bbbbb
							int pi = Rmap[p-1][Rvec[p][i].substr(1)];
							int pj = Rmap[p-1][Rvec[p][j].substr(1)];
							dist[i][j] = min(dist[i][j], preDist[pi][pj]);
						}
					}
				}
			}
			
			// floyd algorithm
			for (int k = 0; k < n; k++) 
				for (int i = 0; i < n; i++)
					for (int j = 0; j < n; j++)
						dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			
			// copy for next loop
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					preDist[i][j] = dist[i][j];
		}
		
		int st = Rmap[N][A], ed = Rmap[N][B];
		long long d = dist[st][ed];
		
		printf("Case %d: ", ++cases);
		if (d >= INF)
			printf("No solution\n");
		else
			printf("%lld\n", d);
	}
	return 0;
}
/*
AAAAAAAAAAAAAAAAAAAA BBBBBBBBBBBBBBBBBBBB 20
ABBBBBBBBBBBBBBBBBBB BAAAAAAAAAAAAAAAAAAA
ABBBBBBBBBBBBBBBBBB  BAAAAAAAAAAAAAAAAAA 
ABBBBBBBBBBBBBBBBB   BAAAAAAAAAAAAAAAAA  
ABBBBBBBBBBBBBBBB    BAAAAAAAAAAAAAAAA   
ABBBBBBBBBBBBBBB     BAAAAAAAAAAAAAAA    
ABBBBBBBBBBBBBB      BAAAAAAAAAAAAAA     
ABBBBBBBBBBBBB       BAAAAAAAAAAAAA      
ABBBBBBBBBBBB        BAAAAAAAAAAAA       
ABBBBBBBBBBB         BAAAAAAAAAAA        
ABBBBBBBBBB          BAAAAAAAAAA         
ABBBBBBBBB           BAAAAAAAAA          
ABBBBBBBB            BAAAAAAAA           
ABBBBBBB             BAAAAAAA            
ABBBBBB              BAAAAAA             
ABBBBB               BAAAAA              
ABBBB                BAAAA               
ABBB                 BAAA                
ABB                  BAA                 
AB                   BA                  
A                    B   
*/
Read More +
解題區►解題區 - UVa

UVa 1084 - Deer-Proof Fence

Problem

給 N 個點，用圍籬將這 N 個點包裹起來，並且每一個點距離圍籬距離至少為 M。

求圍籬總長最少為何。

Sample Input

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

Sample Output

1
2
Case 1: length = 29.13 
Case 2: length = 45.13

Solution

可以將點拆分成好幾個元件，分開進行圍籬。利用高速求出子集的方式，窮舉所有的拆分方式。

dp[s] 表示點 s 所需要的最少圍籬長度，dp[s] = min(dp[u] + cost(s-u))。

圍籬長度為凸包總長加上一個圓的周長 (多邊形外角總和為 360 度)。

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
#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.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());
}
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);
double computeFenceLen(Pt ch[], int n, double r) {
	if (n == 1)
		return r * pi * 2;
	if (n == 2)
		return r * pi * 2 + (ch[0] - ch[1]).length() * 2;
	double ret = 0;
	for (int i = 0, j = n-1; i < n; j = i++)
		ret += (ch[i] - ch[j]).length();
	ret += r * pi * 2;
	return ret;
}
int main() {
    int n, R, cases = 0;
    while (scanf("%d %d", &n, &R) == 2 && n) {
    	Pt D[32], ch[32];
    	for (int i = 0; i < n; i++)
    		scanf("%lf %lf", &D[i].x, &D[i].y);
    	double dp[1024] = {};
    	for (int i = 1; i < (1<<n); i++) {
    		double &val = dp[i];
    		val = 1e+30;
    		for (int j = (i-1)&i; j; j = (j-1)&i)
    			val = min(val, dp[j] + dp[i-j]);
    		
    		int m = 0;
    		Pt A[32];
    		for (int j = 0; j < n; j++) {
    			if ((i>>j)&1)
    				A[m++] = D[j];
    		}
    		
    		int cn = monotone(m, A, ch);
    		double len = computeFenceLen(ch, cn, R);
//    		for (int j = 0; j < cn; j++)
//    			printf("%lf %lf\n", ch[j].x, ch[j].y);
//    		printf("length - %lf\n", len);
    		val = min(val, len);
    	}
    	printf("Case %d: length = %.2lf\n", ++cases, dp[(1<<n)-1]);
    }
    return 0;
}
/*
3 2 
0 0 
2 0 
10 0 
5 3
7 8
9 9
9 9
9 9
2 2
3 3
7 8
9 9
2 2
5 0
4 2
1 5
8 5
2 2
4 9
 */
Read More +
解題區►解題區 - UVa

UVa 1080 - My Bad

Problem

給一個電路圖，有四種閘 AND, OR, XOR, NOT，接著給定閘的輸入端、輸出端，以及預期的輸入和輸出。

請問是否存在電路故障。若只有一個電路故障，輸出故障的情況，否則輸出無法判斷。

故障情況有反向、全為 1、全為 0。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2 2 1 
o i1 i2 
n g1 
2 
2 
1 0 0 
0 0 1 
2 1 1 
a i1 i2 
1 
1 
1 0 1 
2 1 1 
a i1 i2 
1 
2 
1 0 1 
1 1 1 
1 1 1 
n i1 
1 
2 
1 1 
0 0 
3 4 4 
n g4 
a i1 i2 
o i2 i3 
x i3 i1 
2 3 4 1 
4 
0 1 0 0 1 0 1
0 1 1 0 1 1 0
1 1 1 0 1 0 1
0 0 0 0 0 0 1
0 0 0

Sample Output

1
2
3
4
5
Case 1: No faults detected 
Case 2: Unable to totally classify the failure 
Case 3: Gate 1 is failing; output stuck at 1 
Case 4: Gate 1 is failing; output inverted 
Case 5: Gate 2 is failing; output stuck at 0

Solution

如何橋接電路會比較難寫，這裡用 OO 的方式去撰寫，為了方便起見，設計輸入端口只會在 div ~ 512，剩餘在 0 ~ div。

接著窮舉損壞情況，對於每次窮舉，跑一次電路架構。

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
#include <stdio.h> 
#include <vector>
#include <assert.h>
#include <string.h>
#include <algorithm>
using namespace std;
class Circuit {
public:
	enum LOGIC {AND, OR, XOR, NOT, FV, F0, F1};
	struct Gate {
		LOGIC type;
		int p1, p2;
	} gates[1024];
	int inVal[512], outVal[512];
	int visited[512], sick[512];
	LOGIC sickType[512];
	int div = 256;
	void addGate(int id, LOGIC t, int in1, int in2 = 0) {
		gates[id].type = t;
		gates[id].p1 = in1, gates[id].p2 = in2;
	}
	int getInId(int x) {
		return div + x;
	}
	int getId(char s[]) {
		int x;
		sscanf(s+1, "%d", &x);
		return (s[0] == 'i') ? getInId(x) : x;
	}
	int getOutput(int id) {
		if (id > div)		return inVal[id - div];
		if (visited[id])	return outVal[id];
		visited[id] = 1;
		int &val = outVal[id];
		val = 0;
		if (gates[id].type == AND)
			val = (getOutput(gates[id].p1) & getOutput(gates[id].p2));
		if (gates[id].type == OR)
			val = (getOutput(gates[id].p1) | getOutput(gates[id].p2));
		if (gates[id].type == XOR)
			val = (getOutput(gates[id].p1) ^ getOutput(gates[id].p2));
		if (gates[id].type == NOT)
			val = !(getOutput(gates[id].p1));
		if (!sick[id])
			return val;
		if (sickType[id] == FV)
			return val = !val;
		else if (sickType[id] == F0)
			return val = 0;
		else
			return val = 1;
	}
	void clearSick()  {
		memset(sick, 0, sizeof(sick));
	}
	void clear() {
		memset(visited, 0, sizeof(visited));
	}
} g;
int N, G, U, B;
int outGate[128], IN[1024][128], OUT[1024][128];
char s[128], s1[128], s2[128];
int singleTest() {
	int ok = 1;
	for (int i = 0; i < B && ok; i++) {
		g.clear();
		for (int j = 1; j <= N; j++)
			g.inVal[j] = IN[i][j];
		for (int j = 1; j <= U; j++) {
			int v = g.getOutput(outGate[j]);
			ok &= v == OUT[i][j];
		}
	} 
	return ok;
}
void test() {
	g.clearSick();
	if (singleTest()) {
		puts("No faults detected");
		return;
	} 
	
	vector< pair<int, int> > err;
	for (int i = 1; i <= G; i++) {
		g.clearSick();
		g.sick[i] = 1, g.sickType[i] = Circuit::FV;
		if (singleTest())
			err.push_back(pair<int, int>(i, 0));
		g.sick[i] = 1, g.sickType[i] = Circuit::F0;
		if (singleTest())
			err.push_back(pair<int, int>(i, 1));	
		g.sick[i] = 1, g.sickType[i] = Circuit::F1;
		if (singleTest())
			err.push_back(pair<int, int>(i, 2));
		if (err.size() > 1)
			break;
	}
	if (err.size() > 1)
		puts("Unable to totally classify the failure");
	else {
		if (err[0].second == 0)
			printf("Gate %d is failing; output inverted\n", err[0].first);
		else if (err[0].second == 1)
			printf("Gate %d is failing; output stuck at 0\n", err[0].first);
		else if (err[0].second == 2)
			printf("Gate %d is failing; output stuck at 1\n", err[0].first);
	}
}
int main() {
	int cases = 0;
	while (scanf("%d %d %d", &N, &G, &U) == 3 && N) {
		for (int i = 1; i <= G; i++) {
			scanf("%s", s);
			if (s[0] == 'a') {
				scanf("%s %s", s1, s2);
				g.addGate(i, Circuit::AND, g.getId(s1), g.getId(s2));
			} else if (s[0] == 'o') {
				scanf("%s %s", s1, s2);
				g.addGate(i, Circuit::OR, g.getId(s1), g.getId(s2));
			} else if (s[0] == 'x') {
				scanf("%s %s", s1, s2);
				g.addGate(i, Circuit::XOR, g.getId(s1), g.getId(s2));
			} else {
				scanf("%s", s1);
				g.addGate(i, Circuit::NOT, g.getId(s1));
			}
		}
		
		for (int i = 1; i <= U; i++)
			scanf("%d", &outGate[i]);
		scanf("%d", &B);
		assert(B < 1024);
		for (int i = 0; i < B; i++) {
			for (int j = 1; j <= N; j++)
				scanf("%d", &IN[i][j]);
			for (int j = 1; j <= U; j++)
				scanf("%d", &OUT[i][j]);
		}
		
		printf("Case %d: ", ++cases);
		test();
	}
	return 0;
}
/*
2 2 1 
o i1 i2 
n g1 
2 
2 
1 0 0 
0 0 1 
2 1 1 
a i1 i2 
1 
1 
1 0 1 
2 1 1 
a i1 i2 
1 
2 
1 0 1 
1 1 1 
1 1 1 
n i1 
1 
2 
1 1 
0 0 
3 4 4 
n g4 
a i1 i2 
o i2 i3 
x i3 i1 
2 3 4 1 
4 
0 1 0 0 1 0 1
0 1 1 0 1 1 0
1 1 1 0 1 0 1
0 0 0 0 0 0 1
0 0 0
*/
Read More +
解題區►解題區 - UVa

UVa 1078 - Steam Roller

Problem

駕駛蒸氣機在道路上，啟動蒸汽機通過道路需要時間。當要進行轉彎時，必須在轉彎口前進行煞車、出了轉彎口後開始加速，煞車和加速會造成所需時間變成兩倍，在起點出發必須加速、抵達終點時必須減速。

請問最少花費時間需要多少。

Sample Input

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

Sample Output

1
2
Case 1: 100 
Case 2: Impossible

Solution

定義狀態 dist[i][j][dir][k] 在轉彎口 (i, j)，前一次進入轉彎口的方向為 dir，在此之前是否有煞車 k。

隨後進行最短路徑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
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 <algorithm>
#include <string.h>
#include <queue>
using namespace std;
const int MAXN = 128;
int cg[MAXN][MAXN][4];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int dist[MAXN][MAXN][4][2], inq[MAXN][MAXN][4][2];
int spfa(int r1, int c1, int r2, int c2) {
	if (r1 == r2 && c1 == c2)
		return 0;
	queue<int> X, Y, D, F;
	int d1, f1, x, y, w;
	memset(dist, 63, sizeof(dist));
	memset(inq, 0, sizeof(inq));
	for (int i = 0; i < 4; i++) {
		if (!cg[r1][c1][i])	continue;
		x = r1 + dx[i], y = c1 + dy[i];
		dist[x][y][i][1] = 2 * cg[r1][c1][i];
		inq[x][y][i][1] = 1;
		X.push(x), Y.push(y), D.push(i), F.push(1);
	}
	
	while (!X.empty()) {
		r1 = X.front(), X.pop();
		c1 = Y.front(), Y.pop();
		d1 = D.front(), D.pop();
		f1 = F.front(), F.pop();
		inq[r1][c1][d1][f1] = 0;
//		printf("%d %d %d %d - %d\n", r1, c1, d1, f1, dist[r1][c1][d1][f1]); 
		for (int i = 0; i < 4; i++) {
			if (!cg[r1][c1][i])	continue;
			x = r1 + dx[i], y = c1 + dy[i];
//			printf("-> %d %d\n", x, y);
			if (f1 == 1) {
				if (i == d1) {
					w = cg[r1][c1][i] + dist[r1][c1][d1][f1];
					if (dist[x][y][i][0] > w) {
						dist[x][y][i][0] = w;
						if (!inq[x][y][i][0]) {
							inq[x][y][i][0] = 1;
							X.push(x), Y.push(y), D.push(i), F.push(0);
						}
					}
				}
				w = 2 * cg[r1][c1][i] + dist[r1][c1][d1][f1];					
				if (dist[x][y][i][1] > w) {
					dist[x][y][i][1] = w;
					if (!inq[x][y][i][1]) {
						inq[x][y][i][1] = 1;
						X.push(x), Y.push(y), D.push(i), F.push(1);
					}
				}
			} else {
				if (i != d1)	continue;
				w = cg[r1][c1][i] + dist[r1][c1][d1][f1];
				if (dist[x][y][i][0] > w) {
					dist[x][y][i][0] = w;
					if (!inq[x][y][i][0]) {
						inq[x][y][i][0] = 1;
						X.push(x), Y.push(y), D.push(i), F.push(0);
					}
				}
				
				w = 2 * cg[r1][c1][i] + dist[r1][c1][d1][f1];					
				if (dist[x][y][i][1] > w) {
					dist[x][y][i][1] = w;
					if (!inq[x][y][i][1]) {
						inq[x][y][i][1] = 1;
						X.push(x), Y.push(y), D.push(i), F.push(1);
					}
				}
			}
		}
	}
	
	int ret = 0x3f3f3f3f;
	for (int i = 0; i < 4; i++)
		ret = min(ret, dist[r2][c2][i][1]);
	return ret == 0x3f3f3f3f ? -1 : ret;
}
int main() {
	int R, C, r1, c1, r2, c2;
	int x, cases = 0;
	while (scanf("%d %d %d %d %d %d", &R, &C, &r1, &c1, &r2, &c2) == 6 && R) {
		memset(cg, 0, sizeof(cg));
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C - 1; j++) {
				scanf("%d", &x);
				cg[i][j][0] = cg[i][j+1][1] = x;
			}
			if (i != R - 1) {
				for (int j = 0; j < C; j++) {
					scanf("%d", &x);
					cg[i][j][2] = cg[i+1][j][3] = x;
				}
			}
		}
		
		r1--, c1--, r2--, c2--;
		int d = spfa(r1, c1, r2, c2);
		printf("Case %d: ", ++cases);
		if (d >= 0)
			printf("%d\n", d);
		else
			printf("Impossible\n");
	}
	return 0;
}
/*
4 4 4 3 2 4
 7 6 2 
4 5 0 4 
 6 4 1 
4 4 2 2 
 9 4 4 
5 5 3 2 
 9 6 9 
4 4 1 1 4 4 
 10  10  10 
9  0  0  10 
  0  0  0 
9  0  0  10 
  9  0  0 
0  9  0  10 
  0  9  9 
4 4 1 1 1 2
 10  10  10 
9  0  0  10 
  0  0  0 
9  0  0  10 
  9  0  0 
0  9  0  10 
  0  9  9 
  
4 4 1 1 4 4
 10  10  10 
9  0  0  10 
  0  0  0 
9  0  0  10 
  9  0  0 
0  9  0  0 
  0  9  9 
*/
Read More +
解題區►解題區 - UVa

UVa 1076 - Password Suspects

Problem

給定 N 個單字，請問在長度為 M 的密碼中，密碼符合出現這 N 個單詞的情況有多少種。

在密碼個數少於 42 種時，將所有密碼輸出。

Sample Input

1
2
3
4
5
6
7
10 2 
hello 
world 
10 0 
4 1 
icpc 
0 0

Sample Output

1
2
3
4
5
6
Case 1: 2 suspects 
helloworld 
worldhello 
Case 2: 141167095653376 suspects 
Case 3: 1 suspects 
icpc

Solution

建立 AC 自動機，使用 AC 自動機上的 dp，對於每一個 node 將單字用 2^N 來表示 dp 狀態，因此每一個 node 的狀態為 dp[len][1<<N] 表示匹配長度 len，並且已經 match 到的狀態。

由於要輸出 42 以內的密碼可能，在輸出答案前，進行回溯標記，確保下一步可以抵達到可行解，接著進行 dfs 搜索。

1
2
3
4
5
6
7
8
9
1 2
a
a
1 0
2 2
b
ab

特別小心測資存在兩個單詞相同、一個單詞是另一個單詞的 substring。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#define MAXCHAR 26
#define MAXS (1024)
#define MAXNODE 256
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class ACmachine {
public:
    struct Node {
        Node *next[MAXCHAR], *fail;
        int cnt, val, id;
        long long dp[30][1024];
		int dpable[30][1024];
        void init() {
            fail = NULL;
            cnt = val = 0;
            id = 0;
            memset(next, 0, sizeof(next));
            memset(dp, 0, sizeof(dp));
            memset(dpable, 0, sizeof(dp));
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    int toIndex(char c) {
        return c - 'a';
    }
    void dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt |= v->cnt;
                dfs(u, v);
            }
        }
    }
    void merge(const ACmachine &other) {
        dfs(root, other.root);
    }
    void insert(const char str[], int sid) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt = 1;
        if (sid >= 0)	p->id |= 1<<sid;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    void build() { // AC automation
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] == NULL)
                    continue;
                Q.push(u->next[i]);
                p = u->fail;
                while (p != NULL && p->next[i] == NULL)
                    p = p->fail;
                if (p == NULL)
                    u->next[i]->fail = root;
                else
                    u->next[i]->fail = p->next[i];
                u->next[i]->val = u->next[i]->fail->val + u->next[i]->cnt;
                u->next[i]->id = u->next[i]->fail->id | u->next[i]->id;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next[idx] == NULL && u != root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    long long dp(int len, int N) {
    	queue<Node*> Q;
    	Node *u, *p;
    	root->dp[0][0] = 1;
    	long long ret = 0;
    	for (int k = 0; k <= len; k++) {
    		Q.push(root), ret = 0;
    		while (!Q.empty()) {
    			u = Q.front(), Q.pop();
    			ret += u->dp[len][(1<<N)-1];
    			if (u->dp[len][(1<<N)-1])
    				u->dpable[len][(1<<N)-1] = 1;
    			for (int i = 0; i < (1<<N); i++) {
    				if (i && u->dp[k][i] == 0) 
    					continue;
    				for (int j = 0; j < MAXCHAR; j++) {
    					if (u->next[j] != NULL)
    						if (i == 0)	Q.push(u->next[j]);
    					if (u->dp[k][i] == 0)
    						continue;
    					p = u;
						while (p != root && p->next[j] == NULL)
							p = p->fail;
						p = p->next[j];
						if (p == NULL)	continue;
						if (p->id)
    						p->dp[k+1][i|p->id] += u->dp[k][i];
    					else
    						p->dp[k+1][i] += u->dp[k][i];
    				}
    			}
    		} // <end queue>
    	}
    	
    	// backtrack
    	for (int k = len-1; k >= 0; k--) {
    		Q.push(root);
    		while (!Q.empty()) {
    			u = Q.front(), Q.pop();
    			for (int i = 0; i < (1<<N); i++) {
    				if (i && u->dp[k][i] == 0) 
    					continue;
    				for (int j = 0; j < MAXCHAR; j++) {
    					if (u->next[j] != NULL)
    						if (i == 0)	Q.push(u->next[j]);	
    					if (u->dp[k][i] == 0)
    						continue;
    					p = u;
						while (p != root && p->next[j] == NULL)
							p = p->fail;
						p = p->next[j];
						if (p == NULL)	continue;
						if (p->id >= 0) {
    						if (p->dpable[k+1][i|p->id])
    							u->dpable[k][i] = 1;
    					} else {
    						if (p->dpable[k+1][i])
    							u->dpable[k][i] = 1;
    					}
    				}
    			}
    		} // <end queue>
    	}
    	return ret;
    }
    void dpSearch(Node *u, int s, int len, int N, string str, vector<string> &ret) {
    	if (str.length() == len) {
    		if (s == (1<<N)-1)
    			ret.push_back(str);
    		return ;
    	}
    	if (u->dpable[str.length()][s] == 0)
    		return ;
    	Node *p; 
    	for (int i = 0; i < MAXCHAR; i++) {
			p = u;
			while (p != root && p->next[i] == NULL)
				p = p->fail;
			p = p->next[i];
			if (p == NULL)	continue;
    		int ns = s;
    		if (p->id >= 0)	
				ns = s|p->id;
    		dpSearch(p, ns, len, N, str + (char) (i + 'a'), ret);
    	}
    	
    }
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
};
ACmachine g;
int main() {
	int M, N, cases = 0;
	char s[1024];
    while (scanf("%d %d", &M, &N) == 2 && M+N) {
       	g.init();
       	for (int i = 0; i < N; i++) {
       		scanf("%s", s);
       		g.insert(s, i);
       	}
       	
       	for (int i = 'a'; i <= 'z'; i++) {
       		s[0] = i, s[1] = '\0';
       		g.insert(s, -1);
       	}
       	g.build();
       	long long way = g.dp(M, N);
       	printf("Case %d: %lld suspects\n", ++cases, way);
       	if (way <= 42) {
       		vector<string> pwd;
       		g.dpSearch(g.root, 0, M, N, "", pwd);
       		sort(pwd.begin(), pwd.end());
       		for (int i = 0; i < pwd.size(); i++)
       			printf("%s\n", pwd[i].c_str());
       	}
        g.free();
    }
    return 0;
}
/*
10 2 
hello 
world 
10 0 
4 1 
icpc 
10 3
mo
mom
omsi
4 4
a
b
c
d
4 3
ab
bc
ca
1 2
a
a
1 0
2 2
b
ab
0 0
 */
Read More +