解題區/解題區 - 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 +
解題區/解題區 - 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 +