解題區/解題區 - UVa

UVa 905 - Tacos Panchita

Problem

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

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

Sample Input

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

Sample Output

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

測資參考圖

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

Solution

範例輸出有錯，一開始以為自己寫錯。

由於盤面不大，可以直接進行全盤著色，分成四個象限去著色。當然如果盤面大一點，則必須考慮用外積等方式去完成象限判斷。由於是網格狀，邊界上會比較麻煩，方便起見還是直接著色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h> 
#include <string.h>
#include <assert.h>
const int MAXN = 128;
int g[MAXN][MAXN], ret[MAXN][MAXN];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int main() {
    int px, py, w, h;
    int cases = 0;
    while (scanf("%d %d %d %d", &px, &py, &w, &h) == 4) {
        assert(w < MAXN && h < MAXN);
        if (cases++)	puts("");
        
        memset(g, 0, sizeof(g));
        memset(ret, 0, sizeof(ret));
        for (int i = 0; i < MAXN; i++) {
            int x, y;
            x = px - i - 1, y = py + i + 1;
            for (int j = 0; j < 2 * (i + 1); j++) {
                if (x >= 0 && x <= w && y >= 0 && y <= h)
                    g[x][y] = 1;
                y -= 1;
            }
            x = px - i, y = py + i + 1;
            for (int j = 0; j < 2 * (i + 1); j++) {
                if (x >= 0 && x <= w && y >= 0 && y <= h)
                    g[x][y] = 2;
                x += 1;
            }
            x = px + i + 1, y = py + i;
            for (int j = 0; j < 2 * (i + 1); j++) {
                if (x >= 0 && x <= w && y >= 0 && y <= h)
                    g[x][y] = 3;
                y -= 1;
            }
            x = px - i - 1, y = py - i - 1;
            for (int j = 0; j < 2 * (i + 1); j++) {
                if (x >= 0 && x <= w && y >= 0 && y <= h)
                    g[x][y] = 4;
                x += 1;
            }
        }
        
        for (int i = h; i >= 1; i--) {
            int n, x;
            scanf("%d", &n);
            for (int j = 0; j < n; j++) {
                scanf("%d", &x);
                int tx, ty;
                tx = x + dx[g[x][i] - 1];
                ty = i + dy[g[x][i] - 1];
                ret[tx][ty] = 1;
            }
        }
//		for (int i = 1; i <= w; i++, puts(""))
//			for (int j = 1; j <= h; j++)
//				printf("%d", g[i][j]);
                
        printf("%d %d %d %d\n", px, py, w, h);
        for (int i = h; i >= 1; i--) {
            int n = 0;
            for (int j = 1; j <= w; j++)
                n += ret[j][i];
            printf("%d", n);
            for (int j = 1; j <= w; j++)
                if (ret[j][i])
                    printf(" %d", j);
            puts("");
        }
    }
    return 0;
}
/*
3 3 7 6
1 6
1 2
0
1 6
1 2
1 5
*/
Read More +
解題區/解題區 - UVa

UVa 11284 - Shopping Trip

Problem

宅宅喜歡收集 DVD，居住在編號 0 的地方，移動在街道之間需要成本。現在已知到某些店家可以獲得比網購還便宜的價錢，請問出門的最大獲益為何？

可以選擇經過某些店家而不入門購買，每一家店獲得利益後，不能再次獲得利益。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4 5
0 1 1.00
1 2 3.00
1 3 2.00
2 4 4.00
3 4 3.25
3
2 1.50
3 7.00
4 9.00
1 1
0 1 1.50
1
1 2.99

Sample Output

1
2
Daniel can save $3.50
Don't leave the house

Solution

街道圖最多 50 個節點，但是能獲得利益的店家最多 12 家，窮舉拜訪順序需要 $O(12!)$ ，但這樣的速度肯定太慢。先將點之間做最短路徑，只把挑選店家的部分抓出，移動花費就從最短路徑中得到。

利用狀態壓縮得到 dp[i][j]，表示已經經過的店家狀態 i、最後一個走訪店家的編號 j，這個狀態的花費就是從編號 0 出發，經過 i 狀態的所有店家，最後停留在 j，接著窮舉下一個店家 k，則 

1
dp[i|(1<<k)][k] = max(dp[i][j] - g[j][k] + profit[k])

g[i][j] 表示編號 i 到編號 j 的花費 (寫的時候注意對應點與壓縮後的編號)。

由於沒必要經過所有的店家，針對每一格狀態都嘗試返回原點 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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 64;
int main() {
    int testcase;
    int N, M, P;
    int u, v, a, b;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        
        int g[MAXN][MAXN], profit[MAXN] = {};
        int dp[1<<12][12];
        memset(g, 0x3f, sizeof(g));
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d.%d", &u, &v, &a, &b);
            g[u][v] = min(g[u][v], a * 100 + b);
            g[v][u] = min(g[v][u], a * 100 + b);
        }
        
        scanf("%d", &P);		
        for (int i = 0; i < P; i++) {
            scanf("%d %d.%d", &u, &a, &b);
            profit[u] += a * 100 + b;
        }
        
        // floyd algorithm
        for (int i = 0; i <= N; i++)
            g[i][i] = 0;
        for (int k = 0; k <= N; k++)
            for (int i = 0; i <= N; i++) 
                for (int j = 0; j <= N; j++)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                    
        // get store
        vector<int> S;
        for (int i = 0; i <= N; i++) {
            if (profit[i] > 0)
                S.push_back(i);
        }
        
        // run dp
        vector< pair<int, int> > o;
        for (int i = 0; i < (1<<S.size()); i++) {
            for (int j = 0; j < S.size(); j++)
                dp[i][j] = -0x3f3f3f3f;
            o.push_back(make_pair(__builtin_popcount(i), i));
        }
                
        int ret = -0x3f3f3f3f;
        for (int i = 0; i < S.size(); i++) {
            u = S[i];
            dp[1<<i][i] = -g[0][u] + profit[u];
        }
        
        sort(o.begin(), o.end());
        for (int i = 0; i < o.size(); i++) {
            int state = o[i].second;
            for (int j = 0; j < S.size(); j++) {
                if (dp[state][j] == -0x3f3f3f3f)
                    continue;
                    
                u = S[j];
                ret = max(ret, dp[state][j] - g[u][0]);
                for (int k = 0; k < S.size(); k++) {
                    if ((state>>k)&1)
                        continue;
                    v = S[k];
                    dp[state|(1<<k)][k] = max(dp[state|(1<<k)][k], dp[state][j] - g[u][v] + profit[v]);
                }
            }
        }
        
        if (ret > 0)
            printf("Daniel can save $%d.%02d\n", ret/100, ret%100);
        else
            printf("Don't leave the house\n");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11932 - Net Profit

Problem

兩個人在玩一場工廠收購遊戲，工廠之間呈現一張連通圖。先手可以隨機挑一個工廠開始，之後兩個人輪流收購在附近的工廠 (只能選擇盤面上已經收購工廠附近相鄰的工廠)，收購工廠帶來的利益有正、有負。

請問兩邊都是完美玩家，則最多可以贏對方多少分。

Sample Input

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

Sample Output

1
2
3
First player wins! 25 to -20.
Second player wins! 15 to 10.
Tie game! 30 all.

Solution

工廠數量最多 16 個，可以狀態壓縮 dp[2^16]，最大化分差下去完成。

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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int profit[16], dp[1<<16];
int g[16], used[1<<16];
int dfs(int s, int n) {
    if (used[s])	return dp[s];
    if (s == 0)		return 0;
    used[s] = 1;
    int &ret = dp[s];
    int vs = (1<<n)-1 - s;
    ret = -0x3f3f3f3f;
    for (int i = 0; i < n; i++) {
        if (s == (1<<n)-1 || ((g[i]&vs) && ((s>>i)&1))) {
            ret = max(ret, profit[i] - dfs(s^(1<<i), n));
        }
    }
    return ret;
}
int main() {
    int n, m, x, y;
    while (scanf("%d", &n) == 1 && n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &profit[i]);
            g[i] = 0, sum += profit[i];
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            g[x] |= 1<<y, g[y] |= 1<<x;
        }
        
        memset(used, 0, sizeof(used));
        int mxDiff = dfs((1<<n)-1, n);
        if (mxDiff == 0) {
            printf("Tie game! %d all.\n", sum/2);
        } else if (mxDiff > 0) {
            printf("First player wins! %d to %d.\n", (sum + mxDiff)/2, (sum - mxDiff)/2);
        } else {
            printf("Second player wins! %d to %d.\n", (sum - mxDiff)/2, (sum + mxDiff)/2);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11919 - Hybrid Salientia

Problem

青蛙在荷葉上跳躍，現在要跳 N - 1 次，將所有荷葉都經過，每一次跳躍距離會是前一次的 0.9 倍，請問一開始跳躍距離至少為何。

荷葉有圓形和正方形，在荷葉內部移動不消耗任何成本，可以走到荷葉邊緣再進行跳躍。

Sample Input

1
2
3
4
5
6
7
8
2
2
C 0 0 5
C 10 0 2
3
C 0 0 2
S 10 1 4
S 3 1 2

Sample Output

1
2
3.000000
5.555556

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
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
#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());
}	
double distSeg2Point(Pt a, Pt b, Pt p) {
    Pt c, vab;
    vab = a - b;
    if (between(a, b, p)) {
        c = getIntersect(Seg(a, b), Seg(p, Pt(p.x+vab.y, p.y-vab.x)));
        return (p - c).length();
    }
    return min((p - a).length(), (p - b).length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
const double pi = acos(-1);
// this problem
int n;
double dist[16][16], R[16];
Pt XY[16];
char type[16][16];
void placeSquare(Pt LR, double r, Pt A[]) {
    A[0] = LR;
    A[1] = Pt(LR.x, LR.y+r);
    A[2] = Pt(LR.x+r, LR.y+r);
    A[3] = Pt(LR.x+r, LR.y);
}
double calcDistance(int p, int q) {
    if (type[p][0] == 'C' && type[q][0] == 'C') {
        Pt vab = XY[p] - XY[q];
        return vab.length() - R[p] - R[q];
    }
    if (type[p][0] == 'S' && type[q][0] == 'S') {
        double ret = 1e+30;
        Pt a[4], b[4], vab, c;
        placeSquare(XY[p], R[p], a);
        placeSquare(XY[q], R[q], b);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                ret = min(ret, distSeg2Point(a[i], a[(i+1)%4], b[j]));
                ret = min(ret, distSeg2Point(b[i], b[(i+1)%4], a[j]));
            }
        } 
        return ret;
    }
    double ret = 1e+30, r;
    Pt a[4], b;
    if (type[p][0] == 'S')
        placeSquare(XY[p], R[p], a), b = XY[q], r = R[q];
    else
        placeSquare(XY[q], R[q], a), b = XY[p], r = R[p];
        
    for (int i = 0; i < 4; i++) {
        ret = min(ret, distSeg2Point(a[i], a[(i+1)%4], b) - r);
    }
    return ret;
}
void buildDistance() {
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            dist[i][j] = dist[j][i] = calcDistance(i, j);
        }
        dist[i][i] = 0;
    }
}
double dp[1<<15][15];
int main() {
    const double INF = 1e+30;
    double Pow9[32];
    Pow9[0] = 1;
    for (int i = 1; i < 16; i++)
        Pow9[i] = Pow9[i-1] / 0.9;
    int testcase;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%s %lf %lf %lf", type[i], &x, &y, &R[i]);
            XY[i] = Pt(x, y);
        }
        
        buildDistance();
        
        /*
		for (int i = 0; i < n; i++, puts("")) {
			for (int j = 0; j < n; j++) {
				printf("%lf ", dist[i][j]);
			}
		}
		*/
        
        vector< pair<int, int> > A;
        for (int i = 0; i < (1<<n); i++) {
            A.push_back(make_pair(__builtin_popcount(i), i));
            for (int j = 0; j < n; j++)
                dp[i][j] = INF;
        }
        sort(A.begin(), A.end());
        
        dp[1<<0][0] = 0;
        
        for (int p = 0; p < A.size(); p++) {
            int s = A[p].second, t = A[p].first - 1;
            for (int i = 0; i < n; i++) {
                if (dp[s][i] >= INF)	continue;
                for (int j = 0; j < n; j++) {
                    if ((s>>j)&1)
                        continue;
                    dp[s|(1<<j)][j] = min(dp[s|(1<<j)][j], max(dp[s][i], dist[i][j] * Pow9[t]));
                }
            }
        }
         
        double ret = INF;
        for (int i = 0; i < n; i++)
            ret = min(ret, dp[(1<<n)-1][i]);
        printf("%.6lf\n", ret);
    }
    return 0;
}
/*
2
2
C 0 0 5
C 10 0 2
3
C 0 0 2
S 10 1 4
S 3 1 2
*/
Read More +
解題區/解題區 - UVa

UVa 11918 - Traveler of Gridland

Problem

在一個 (-1000000000, -1000000000) x (1000000000, 100000000) 的平面上，有三種怪物，分別佔據點、線、面三種情況，保證都與兩座標軸平行。

現在問起點到終點的最短路徑為何。

Sample Input

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

Sample Output

1
Case 1: 14

Solution

由於盤面相當大，不可能直接進行 bfs，因此必須將盤面縮小，將大多數空白的地點壓縮，也就是離散化處理 (名稱上就不糾結)。

對於出現的座標，紀錄鄰近九宮格的左右 x, y 值，接著將其展開成新的一張圖，每一格之間的長度都是可變的。進行最短路時，就不能使用 bfs 這麼單純，使用 spfa 或者是 dijkstra 算法完成。

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
#include <stdio.h> 
#include <string.h>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
map<int, int> RX, RY;
vector<int> VX, VY;
int sx, sy, ex, ey, M, N, Q;
int x1[128], y1[128], x2[128][2], y2[128][2], x3[128][2], y3[128][2];
int g[605][605];
void record(int x, int y) {
    for (int i = -1; i <= 1; i++) {
        RX[min(max(x + i, -1000000000), 1000000000)] = 0;
        RY[min(max(y + i, -1000000000), 1000000000)] = 0;
    }
}
void buildGrid() {
    VX.clear(), VY.clear();
    for (map<int, int>::iterator it = RX.begin();
        it != RX.end(); it++) {
        it->second = VX.size(), VX.push_back(it->first);
    }
    for (map<int, int>::iterator it = RY.begin();
        it != RY.end(); it++) {
        it->second = VY.size(), VY.push_back(it->first);
    }
    
    memset(g, 0, sizeof(g));
    int ux, uy, vx, vy;
    for (int i = 0; i < M; i++) {
        ux = RX[x1[i]], uy = RY[y1[i]];
        g[ux][uy] = 1;
    }
    for (int i = 0; i < N; i++) {
        ux = RX[x2[i][0]], uy = RY[y2[i][0]];
        vx = RX[x2[i][1]], vy = RY[y2[i][1]];
        if (ux > vx)	swap(ux, vx);
        if (uy > vy)	swap(uy, vy);
        for (int p = ux; p <= vx; p++)
            for (int q = uy; q <= vy; q++)
                g[p][q] = 1;
    }
    for (int i = 0; i < Q; i++) {
        ux = RX[x3[i][0]], uy = RY[y3[i][0]];
        vx = RX[x3[i][1]], vy = RY[y3[i][1]];
        if (ux > vx)	swap(ux, vx);
        if (uy > vy)	swap(uy, vy);
        for (int p = ux; p <= vx; p++)
            for (int q = uy; q <= vy; q++)
                g[p][q] = 1;
    }
//	printf("   |");
//	for (int i = 0; i < VY.size(); i++)
//		printf("%3d|", VY[i]);
//	puts("");
//	for (int i = 0; i < VX.size(); i++, puts("")) {
//		printf("%3d|", VX[i]);
//		for (int j = 0; j < VY.size(); j++) {
//			printf("%3d ", g[i][j]);
//		}
//	}
}
long long dist2pt(int sx, int sy, int ex, int ey) {
    long long dx = abs(VX[sx] - VX[ex]);
    long long dy = abs(VY[sy] - VY[ey]);
    return dx + dy;
}
long long dist[605][605];
int inq[605][605];
long long spfa(int sx, int sy, int ex, int ey) {
    memset(dist, 63, sizeof(dist));
    memset(inq, 0, sizeof(inq));
    long long INF = dist[0][0];
    queue<int> X, Y;
    int x, y, tx, ty;
    
    dist[sx][sy] = 0;
    X.push(sx), Y.push(sy);
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        inq[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || ty < 0 || tx >= VX.size() || ty >= VY.size())
                continue;
            if (g[tx][ty])
                continue;
            if (dist[tx][ty] > dist[x][y] + dist2pt(x, y, tx, ty)) {
                dist[tx][ty] = dist[x][y] + dist2pt(x, y, tx, ty);
                if (!inq[tx][ty]) {
                    if (dist[tx][ty] <= dist[ex][ey])
                        inq[tx][ty] = 1, X.push(tx), Y.push(ty);
                }
            }
        }
    }
    return dist[ex][ey] == INF ? -1 : dist[ex][ey];
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        
        RX.clear(), RY.clear();
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        scanf("%d %d %d", &M, &N, &Q);
        
        record(sx, sy), record(ex, ey);
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x1[i], &y1[i]);
            record(x1[i], y1[i]);
        }
        for (int i = 0; i < N; i++) {
            scanf("%d %d %d %d", &x2[i][0], &y2[i][0], &x2[i][1], &y2[i][1]);
            record(x2[i][0], y2[i][0]);
            record(x2[i][1], y2[i][1]);
        }
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d %d", &x3[i][0], &y3[i][0], &x3[i][1], &y3[i][1]);
            record(x3[i][0], y3[i][0]);
            record(x3[i][1], y3[i][1]);
        }
        
        buildGrid();
        long long ret = spfa(RX[sx], RY[sy], RX[ex], RY[ey]);
        printf("Case %d: ", ++cases);
        if (ret >= 0)	printf("%lld\n", ret);
        else			printf("Impossible\n");
    }
    return 0;
}
/*
2
-1 0 1 0
0 1 0
0 -1000000000 0 1000000000
-2 -1000000000 2 1000000000
0 2 0
-1 -1000000000 -1 999999999
1 -999999999 1 1000000000
*/
Read More +
解題區/解題區 - UVa

UVa 11903 - e-Friends

Problem

N 個小夥伴排隊，每一個人都有不想排在某些人後面 (直接排在這個人之後)，對於一個排列將會統計有多少不滿意程度，不滿意程度即為排在他討厭的人後會得到 K 的總和。

詢問數次當不滿意程度小於等於 Q 的排列方法數。

Sample Input

1
2
3
4
5
6
1
2 10 2
1 2
0
10
5

Sample Output

1
2
3
Case 1:
2
1

Solution

每個人的不滿意程度都相同，化成單位 1，那麼不滿意總和最多為 N。

預處理 dp[state][last][K] 表示當前排列的人 state、最後一個人的編號 last、當前的不滿意總和 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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int dp[1<<12][12][12]; // dp[state][last][K] = ways
int main() {
    int testcase, cases = 0;
    int N, K, Q;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &Q);
        int em[16] = {};
        for (int i = 0; i < N; i++) {
            int t, x;
            scanf("%d", &t);
            for (int j = 0; j < t; j++) {
                scanf("%d", &x), x--;
                em[i] |= 1<<x;
            }
        }
        
        vector< pair<int, int> > A;
        for (int i = 0; i < (1<<N); i++)
            A.push_back(make_pair(__builtin_popcount(i), i));
        sort(A.begin(), A.end());
        
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < N; i++)
            dp[1<<i][i][0] = 1;
            
        for (int p = 0; p < A.size(); p++) {
            int s = A[p].second, t = A[p].first;
            for (int i = 0; i < N; i++) { // last
                for (int j = 0; j < t; j++) { // dissatisfaction index
                    if (dp[s][i][j] == 0)
                        continue;
//					printf("%d %d %d - %d\n", s, i, j, dp[s][i][j]);
                    for (int k = 0; k < N; k++) {
                        if ((s>>k)&1)	
                            continue;
                        int tt = j;
                        if ((1<<i)&em[k])	tt++;
                        dp[s|(1<<k)][k][tt] += dp[s][i][j];
                    }
                }
            }
        }
        
        int preCalc[16] = {};
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                preCalc[j] += dp[(1<<N)-1][i][j];
            }
        }
        
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < Q; i++) {
            int x, ret = 0;
            scanf("%d", &x);
            if (K == 0)	x = N;
            else		x /= K;
            for (int j = 0; j <= x && j <= N; j++)
                ret += preCalc[j];
            printf("%d\n", ret);
        }
    }
    return 0;
}
/*
2
5 50 3
2 2 4
2 1 5
1 1
1 5
1 3
60
10
20
2 10 2
1 2
0
10
5
*/
Read More +
解題區/解題區 - UVa

UVa 11670 - Physics Experiment

Problem

物理加熱實驗，每個粒子在一個長棒上，加熱長棒的一端，粒子水平左右移動速度為 1，當距離加熱粒子小於等於 D 時，加熱狀態就會被傳遞。

給定每一個粒子的位置，現在從座標 0 的位置進行加熱，請問所有粒子都呈現加熱狀態需要幾秒。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5
0.000
3.000
4.500
7.000
10.000
2.500
2
0.000
6.000
3.000
0

Sample Output

1
2
Case 1: 0.250
Case 2: 1.500

Solution

貪心盡可能讓粒子往原點移動，維護一個當前使用時間 t，前 i 個粒子的傳遞時間最短下，最右側的粒子能距離原點最遠為何。

加入下一個粒子時 (不考慮在 t 秒內的移動)，若距離大於 D，且藉由 t 時間內的移動仍然無法接近到加熱粒子 D 以內，則表示需要額外時間來接近加熱粒子 (加熱粒子與未加熱粒子彼此靠近)。反之，則在 t 秒內慢慢移動到加熱粒子恰好能傳遞的距離上 (類似接力賽跑的接棒過程)。如果下一個粒子距離小於 D，表示在 t 秒內可以進可能遠離到恰好接棒的位置。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
// greedy, math
const int MAXN = 100005;
double pos[MAXN], D;
int main() {
    int n, cases = 0;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%lf", &pos[i]);
        scanf("%lf", &D);
        
        sort(pos, pos + n);
        double t = 0;
        for (int i = 1; i < n; i++) {
            if (pos[i] - pos[i-1] > D) { // at t-time, i-th object must move left
                if ((pos[i] - t) - pos[i-1] > D) { // late
                    double move = ((pos[i] - t) - pos[i-1] - D)/2;
                    pos[i] = pos[i] - move - t; // move: move left to be heated, t: greedy move left, at t-time.
                    t += move;
                } else {
                    pos[i] = pos[i-1] + D;
                }
            } else { // i-th object move right
                if (pos[i] + t < pos[i-1] + D)
                    pos[i] = pos[i] + t;
                else
                    pos[i] = pos[i-1] + D;
            }
        }
        printf("Case %d: %.3lf\n", ++cases, t);
    }	 
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11620 - City of Egocentrics

Problem

在城市中有一群怪人，以自我為中心地方是居住，城市呈現一個網格，每一格表示居住人數。這些怪人自我為中心的判定方法有四種 水平、垂直、對角、反對角。

對於四種可能的線，選定線上一點，左側和右側的數量和會相同。輸出四種方法各自合適的居住地。

Sample Input

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

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
H
V
D
0 2
2 0
A
0 0
2 2
H
0 1
1 1
2 1
V
1 0
1 1
1 2
D
0 2
1 1
2 0
A
0 0
1 1
2 2
H
2 2
V
1 2
2 2
D
0 3
1 1
1 2
3 0
A
0 0
2 1
2 2
3 3

Solution

利用前綴和在 O(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
#include <stdio.h> 
#include <algorithm>
using namespace std;
const int MAXN = 128;
int A[MAXN][MAXN], B[MAXN][MAXN], n;
int mark[MAXN][MAXN];
void print(char c) {
    printf("%c\n", c);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            if (mark[i][j])
                printf("%d %d\n", i, j);
    }
}
void solve() {
    for (int i = 0; i < n; i++) {
        int sum = 0, l, r;
        for (int j = 0; j < n; j++)
            sum += A[i][j];
        l = 0, r = sum;
        for (int j = 0; j < n; j++) {
            r -= A[i][j];
            mark[i][j] = (l == r);
            l += A[i][j];
        }
    }
    print('H');
    
    for (int i = 0; i < n; i++) {
        int sum = 0, l, r;
        for (int j = 0; j < n; j++)
            sum += A[j][i];
        l = 0, r = sum;
        for (int j = 0; j < n; j++) {
            r -= A[j][i];
            mark[j][i] = (l == r);
            l += A[j][i];
        }
    }
    print('V');
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i-1 >= 0 && j-1 >= 0)
                B[i][j] = B[i-1][j-1] + A[i][j];
            else
                B[i][j] = A[i][j];
        }
    } 
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int l = 0, r = 0;
            if (i-1 >= 0 && j-1 >= 0)
                l = B[i-1][j-1];
            int ex, ey;
            ex = i + min(n-1-i, n-1-j), ey = j + min(n-1-i, n-1-j);
            r = B[ex][ey] - l - A[i][j];
            mark[i][j] = (l == r);
        }
    }
    print('D');
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i-1 >= 0 && j+1 < n)
                B[i][j] = B[i-1][j+1] + A[i][j];
            else
                B[i][j] = A[i][j];
        }
    } 
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int l = 0, r = 0;
            if (i-1 >= 0 && j+1 < n)
                l = B[i-1][j+1];
            int ex, ey;
            ex = i + min(n-1-i, j), ey = j - min(n-1-i, j);
            r = B[ex][ey] - l - A[i][j];
            mark[i][j] = (l == r);
        }
    }
    print('A');
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &A[i][j]);
        
        solve();
    }
    return 0;
}
/*
3
3
1 2 3
4 5 6
7 8 9
3
1 1 1
1 1 1
1 1 1
4
5 7 7 6
2 4 0 8
6 1 0 7
6 8 7 5
*/
Read More +
解題區/解題區 - UVa

UVa 10999 - Crabbles

Problem

有 N 個單詞，現在有 M 張字卡，字卡上有各自的字母、權重。挑選字卡出來排列，若剛好拼出 N 個單詞中的一個，則得分為挑選字卡的權重總和。給定數場不同的字卡集，對於每一場請問最多能獲得多少分。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
abcd
hgfe
1
10
a 1
b 2
c 3
d 4
e 5
f 6
g 7
h 8
i 9
j 10

Sample Output

1
26

Solution

由於 N 非常大，M 非常小，詢問次數非常多。

每次窮舉單詞來進行最大權匹配相當浪費時間，每個詢問是 $O(N)$ 次窮舉。因此考慮窮舉挑選的字卡，接著在快速的時間 $O(2^M)$內進行單詞查找。

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#define MAXCHAR 26 
#define MAXS (4096)
#define MAXNODE (1048576<<2)
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt;
        void init() {
            cnt = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        return c - 'a';
    }
    // merge trie
    void merge_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;
                merge_dfs(u, v);
            }
        }
    }
    void merge(const Trie &other) {
        merge_dfs(root, other.root);
    }
    // basis operation
    void insert(const char str[], int w) {
        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 += w;
    }
    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 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;
        }
    }
} tool;
char S[MAXS], buf[MAXS];
int main() {
    int n, m, q;
    while (scanf("%d", &n) == 1) {
        tool.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", S);
            int m = strlen(S);
            sort(S, S+m);
            tool.insert(S, 1);
        }
        
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d", &m);
            
            char letter[26][2];
            int val[26];
            for (int j = 0; j < m; j++)
                scanf("%s %d", letter[j], &val[j]);
                
            // brute
            int max_score = 0;
            for (int j = (1<<m)-1; j >= 0; j--) {
                int idx = 0, sum = 0;
                for (int k = 0; k < m; k++) {
                    if ((j>>k)&1) 
                        buf[idx++] = letter[k][0], sum += val[k];
                }
                buf[idx] = '\0';
                sort(buf, buf + idx);
                if (tool.find(buf))
                    max_score = max(max_score, sum);
            }
            printf("%d\n", max_score);
        }
        tool.free();    
    }
    return 0;
}
/*
 */
Read More +
解題區/解題區 - UVa

UVa 10987 - Antifloyd

Problem

給定經由 n 個節點的無向圖，任兩點之間的最短路結果，請問原圖中的邊為何？用最少數量的邊完成。如果有可能無解則輸出 Need better measurements.

Sample Input

1
2
3
4
5
6
7
2
3
100
200 100
3
100
300 100

Sample Output

1
2
3
4
5
6
7
Case #1:
2
1 2 100
2 3 100
Case #2:
Need better measurements.

Solution

最短路徑符合三角不等式，否則將會有更短的邊，檢查 f[i][j] <= f[i][k] + f[k][j]，窮舉所有可能進行檢查，$O(n^3)$ 完成。接著窮舉找到任兩個相鄰點 i, j 之間是否存在內點。若不存在內點，則表示 i, j 在原圖上有一條邊權重為 f[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
// floyd
#include <stdio.h> 
#include <algorithm>
using namespace std;
const int MAXN = 128;
int f[MAXN][MAXN];
int anti_floyd(int n) {
    int adj[MAXN][MAXN] = {};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            adj[i][j] = 1;
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (f[i][k] + f[k][j] < f[i][j]) {
                    puts("Need better measurements.");
                    return 0;
                }
                if (i == j || i == k || j == k)
                    continue;
                if (f[i][k] + f[k][j] == f[i][j])
                    adj[i][j] = 0;
            }
        }
    }
    
    int e = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (i == j)	continue;
            e += adj[i][j];
        }
    }
    
    printf("%d\n", e);
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++)
            if (adj[i][j])
                printf("%d %d %d\n", i+1, j+1, f[i][j]);
    }
    return 1;
}
int main() {
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++)
                scanf("%d", &f[i][j]), f[j][i] = f[i][j];
            f[i][i] = 0;
        }
        
        printf("Case #%d:\n", ++cases);
        int valid = anti_floyd(n);
        puts("");
    }
    return 0;
}
Read More +