解題區/解題區 - UVa

UVa 11243 - Texas Trip

Problem

After a day trip with his friend Dick, Harry noticed a strange pattern of tiny holes in the door of his SUV. The local American Tire store sells fiberglass patching material only in square sheets. What is the smallest patch that Harry needs to fix his door?

Assume that the holes are points on the integer lattice in the plane. Your job is to find the area of the smallest square that will cover all the holes.

Input

The first line of input contains a single integer T expressed in decimal with no leading zeroes, denoting the number of test cases to follow. The subsequent lines of input describe the test cases.

Each test case begins with a single line, containing a single integer n expressed in decimal with no leading zeroes, the number of points to follow; each of the following n lines contains two integers x and y, both expressed in decimal with no leading zeroes, giving the coordinates of one of your points.

You are guaranteed that T <= 30 and that no data set contains more than 30 points. All points in each data set will be no more than 500 units away from (0,0).

Output

Print, on a single line with two decimal places of precision, the area of the smallest square containing all of your points. An answer will be accepted if it lies within 0.1 of the correct answer.

Sample Input

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

Sample Output

1
2
4.00
242.00

Solution

題目描述：

給平面上 N 個點，找到最小面積的正方形覆蓋所有點。

題目解法：

做一次凸包，得到逆時針的點順序，對於每一個凸包頂點進行，使用三分搜索找到相對應的寬。

進行三分搜索的線段為如下圖所示

p11243.png

對於通過 B 點的所有線段，考慮與下一個凸包頂點所夾的角度( < 180 度)，如圖範例所示即三分再 45 度的區域之中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
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
#include <stdio.h>
#include <stdio.h>
#include <math.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) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    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 val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
double distProjection(Pt as, Pt at, Pt s) {
    double a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
struct Seg {
    Pt s, e;
};
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double d, dx, dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    d = a1*b2 - a2*b1;
    dx = c1*b2 - c2*b1;
    dy = a1*c2 - a2*c1;
    if(fabs(d) < eps) // NONE or LINE
        return 0;
    p.x = dx / d, p.y = dy / d;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
    printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
    printf("%lf %lf\n", p.x, p.y);*/
    return onSeg(a.s, a.e, p) && onSeg(b.s, b.e, p);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x * p[i+1].y - p[i].y * p[i+1].x;
    return fabs(ret)/2;
}
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;
}
#define INF 1e+30 
// ternary search
double calcSquare(double m, Pt p, Pt ch[], int n) {
    double a, b, c, lab;
    double w = 0, hl = 0, hr = 0, h;
    a = sin(m), b = -cos(m), c = - (a * p.x + b * p.y), lab = hypot(a, b);
    
    int pp = 0, qq = 0;
    for(int i = 0; i < n; i++) {
        double d = fabs(a * ch[i].x + b * ch[i].y + c) / lab;
        w = max(w, d);
        if(a * ch[i].x + b * ch[i].y + c < - 1e-6)
            pp++;
        if(a * ch[i].x + b * ch[i].y + c > 1e-6)
            qq++;
    }
//	printf("%d %d\n", pp, qq);
    a = cos(m), b = sin(m), c = - (a * p.x + b * p.y), lab = hypot(a, b);
    for(int i = 0; i < n; i++) {
        double d = fabs(a * ch[i].x + b * ch[i].y + c) / lab;
        if(a * ch[i].x + b * ch[i].y + c < 0)
            hl = max(hl, d);
        else
            hr = max(hr, d);
    }
    h = hl + hr;
    return max(w, h) * max(w, h);
}
const double pi = acos(-1);
double ternary_search(double l, double r, Pt p, Pt ch[], int n) {
    double mid, midmid, md, mmd;
    double ret = INF;
    while(fabs(l-r) > eps) {
        mid = (l+r)/2;
        midmid = (mid+r)/2;
        md = calcSquare(mid, p, ch, n);
        mmd = calcSquare(midmid, p, ch, n);
        ret = min(ret, md);
        ret = min(ret, mmd);
        if(md < mmd)
            r = midmid;
        else
            l = mid;
    }
//	printf("best %lf %lf\n", l / pi * 180, ret);
    return ret;
}
double smallSquare(int n, Pt ch[]) {
    double ret = INF;
    
    for(int i = 0, j = n-1; i < n; j = i++) {
//		printf("pt[%lf %lf]\n", ch[i].x, ch[i].y);
        double l = atan2(ch[j].y - ch[i].y, ch[j].x - ch[i].x);
        double r = atan2(ch[(i+1)].y - ch[i].y, ch[(i+1)].x - ch[i].x) - pi;
//		printf("l r [%lf %lf]\n", l, r);
        r = l + fmod(fmod(r - l, 2 * pi) + 2 * pi, 2 * pi);
        if(l <= r) {
            ret = min(ret, ternary_search(l, r, ch[i], ch, n));
        } else {
            ret = min(ret, ternary_search(l, pi, ch[i], ch, n));
            ret = min(ret, ternary_search(-pi, r, ch[i], ch, n));
        }
    }
    return ret;
}
int main() {
    Pt p[2048], ch[2048];
    int n, m;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d", &n);
    	for(int i = 0; i < n; i++)
    		scanf("%lf %lf", &p[i].x, &p[i].y);
        m = monotone(n, p, ch);
//        for(int i = 0; i < m; i++)
//        	printf("%lf %lf\n", ch[i].x, ch[i].y);
    	
    	if(m == 1) {
    		printf("%.2lf\n", 0);
    		continue;
    	}
        double ret = smallSquare(m, ch);
        printf("%.2lf\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11215 - How Many Numbers

Problem

You might have heard the game of 24: given 4 integers, you’re to make an expression to get the number 24. For example, given 4, 4, 10, 10, you can write (1010-4)/4=24, given 1, 5, 5, 5, you can write (5-1/5)5=24.

In this problem, your task is a little bit harder: count the number of numbers that can be made. Don’t forget to count negative numbers and non-integers. You can use binary additions, subtractions, multiplications and divisions with parenthesis (unary operations are not allowed). Numbers cannot be concatenated to form a larger number (e.g. you cannot concatenate 1 and 2 to get 12).

For example, given two 1’s, exactly 3 numbers can be made: 1+1=2, 1-1=0, 1*1=1. You cannot get 11 or -1.

Input

The input consists of at most 30 test cases. Each case begins with a line containing a single integer n (1 < n < 7), the number of integers given. The next line contains n non-negative integers not greater than 10. The last case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the number of numbers that can be made.

Sample Input

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

Output for the Sample Input

1
2
3
Case 1: 3
Case 2: 47
Case 3: 255

Solution

題目描述：

對於給定的數字，考慮所有加減乘除括號的所有計算方案，計算出有多少不同種的運算結果。

題目解法：

類似矩陣鏈乘積，考量每一種排列方式。

對於其中一種排列方式，紀錄狀態 [l, r] 之間所有可能的運算結果，當要合併兩個區間時，枚舉兩個區間的所有可能，並且將其兩兩合併。

[l, r] = [l, k](+-*/)[k+1, r]

使用 double 以為小數點誤差影響不太，但怎麼做都 WA，最後直接用分數的方式進行計算，最後拿了很慢的 AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h> 
#include <algorithm>
#include <set>
#include <math.h>
using namespace std;
#define eps 1e-3
struct Fraction {
    long long a, b;
    Fraction(long long x=0, long long y=1) {
        long long g = __gcd(x, y);
        a = x / g;
        b = y / g;
        if(b < 0)	a = -a, b = -b;
    }
    Fraction operator+(const Fraction &x) const {
        return Fraction(a * x.b + x.a * b, b * x.b);
    }
    Fraction operator-(const Fraction &x) const {
        return Fraction(a * x.b - x.a * b, b * x.b);
    }
    Fraction operator*(const Fraction &x) const {
        return Fraction(a * x.a, b * x.b);
    }
    Fraction operator/(const Fraction &x) const {
        return Fraction(a * x.b, b * x.a);
    }
    bool operator<(const Fraction &x) const {
        return a * x.b < b * x.a;
    }
};
int main() {
    int n, cases = 0, A[10];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        set<Fraction> ret;
        sort(A, A+n);
        do {
            set<Fraction> dp[10][10];
            for(int i = 0; i < n; i++)
                dp[i][i].insert(Fraction(A[i]));
            for(int i = 1; i < n; i++) {
                for(int j = 0; i + j < n; j++) {
                    for(int k = j; k < j+i; k++) {
                        for(set<Fraction>::iterator it = dp[j][k].begin();
                            it != dp[j][k].end(); it++)
                        for(set<Fraction>::iterator jt = dp[k+1][j+i].begin();
                            jt != dp[k+1][j+i].end(); jt++) {
                            Fraction a = *it, b = *jt;
                            dp[j][j+i].insert(a+b);
                            dp[j][j+i].insert(a-b);
                            dp[j][j+i].insert(a*b);
                            if(b.a)
                                dp[j][j+i].insert(a/b);
                        }
                    }
                }
            }
            for(set<Fraction>::iterator it = dp[0][n-1].begin();
                it != dp[0][n-1].end(); it++)
                ret.insert(*it);
        } while(next_permutation(A, A+n));
        printf("Case %d: %d\n", ++cases, ret.size());
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11200 - Sapitaur's labyrinth

Background

In the distant planet Omicron Persei 8, there is a huge ocean of rotten dark water. In the middle of the ocean, there is the island of Nevreturn, where the damned Omicronian prisoners are sent. And on the island, there is an intricate labyrinth; only those prisoners who are able to escape from the labyrinth are given the merciful death. The labyrinth is surrounded by a deep abysm, where the mythical Sapitaur –half frog, half bull– lives, eating all those Omicronians who took a wrong course in the labyrinth.

You are an unfortunate Omicronian prisoner. Will you be able to escape from the labyrinth?
The Problem

Sapitaur’s Labyrinth consists of a matrix of cells. There are two kinds of cells, as shown in the figure below:

  • NOWSE. There is a wall extending from the North-West of the cell to the South-East.

  • NESOW. There is a wall extending from the North-East of the cell to the South-West.

Left: the two kinds of cells. Middle: a sample labyrinth with 3x3 cells, and 2 paths to escape. Right: a labyrinth with 15x10 cells, and only 1 path to escape (in red).

As you can see in the figure above, the entrance to the labyrinth is in the north (the upper row of the matrix), the exit is in the south (the lower row of the matrix), and the abysm extends along both sides of the labyrinth (beyond the first and last column of the matrix).

You have to count how many different paths exist to go from the entrance to the exit of the labyrinth. Obviously, these paths cannot go through the abysm.

The Input

The first line of the input contains an integer M, indicating the number of test cases.

For each test case, the first line contains two integers N M, between 1 and 500, where N is the width of the labyrinth (number of columns) and M is the height (number of rows). M lines follow; each line has N characters: “\” for NOWSE cells; and “/“ for NESOW cells.

The Output

For each test case, the output should consist of an integer indicating the number of different paths from the entrance to the exit of the labyrinth.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3 3
///
\\\
///
15 10
////\\\////\\//
/\\\\\/\/\/\\/\
\\\//\\\/\////\
//\\\/\///\//\\
\/\//\\/\\\\/\\
////////\\///\/
\\\\\\//\\\\\/\
\\/\//////\\///
\/\\/////\/\/\/
\///\///\\\\//\

Sample Output

1
2
2
1

Solution

題目描述：

給定用 \、/ 構成的迷宮，找到從上方進入且可以抵達下方的路徑總數。

題目解法：

這題目看似非常難，由於在建表處理上非常不方便。

但是仔細想想，考慮當前所在的格子類型，再考慮進來的方向，就能推出下一步會到達的格子。
(類似於鏡子反射的現象)

路徑總數不會太多，直接使用 DFS 進行搜索枚舉即可。

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> 
#include <string.h>
char g[512][512];
int ret = 0, n, m;
const int dx[] = {1, 0, -1, 0}; // N, E, S, W
const int dy[] = {0, 1, 0, -1};
void dfs(int x, int y, int fdir) {
    if(x == n)	ret++;
    if(x < 0 || y < 0 || x >= n || y >= m)
        return;
    int dir = 0;
    if(g[x][y] == '\\') {
        switch(fdir) {
            case 0: dir = 1; break;
            case 1: dir = 0; break;
            case 2: dir = 3; break;
            case 3: dir = 2; break;
        }
    } else {
        switch(fdir) {
            case 0: dir = 3; break;
            case 3: dir = 0; break;
            case 1: dir = 2; break;
            case 2: dir = 1; break;
        }
    }
    dfs(x + dx[dir], y + dy[dir], dir);
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &m, &n);
        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);
            
        ret = 0;
        for(int i = 0; i < m; i++)
            dfs(0, i, 0);
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10173 - Smallest Bounding Rectangle

Problem

Given the Cartesian coordinates of n (> 0) 2-dimensional points, write a program that computes the area of their smallest bounding rectangle (smallest rectangle containing all the given points).

Input

The input file may contain multiple test cases. Each test case begins with a line containing a positive integer n (< 1001) indicating the number of points in this test case. Then follows n lines each containing two real numbers giving respectively the x- and y-coordinates of a point. The input terminates with a test case containing a value 0 for n which must not be processed.

Output

For each test case in the input print a line containing the area of the smallest bounding rectangle rounded to the 4th digit after the decimal point.

Sample Input

1
2
3
4
5
6
7
8
9
10
3
-3.000 5.000
7.000 9.000
17.000 5.000
4
10.000 10.000
10.000 20.000
20.000 20.000
20.000 10.000
0

Sample Output

1
2
80.0000
100.0000

Solution

題目描述：

給予平面上 N 個點，找到一個最小矩形覆蓋所有點座標。

題目解法：

做一次單調鏈，得到逆時針的凸包順序，接著第一步找到四邊平行 XY 軸的最小矩形。

接著對於卡邊四邊上的頂點，找到矩形邊與凸包邊夾角最小的頂點，進行向量的旋轉，然後再進行計算矩形的長寬。

對於矩形的長寬，直接套用點線投影公式。

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
#include <stdio.h>
#include <stdio.h>
#include <math.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) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    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 val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
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);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
double distProjection(Pt as, Pt at, Pt s) {
    double a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
struct Seg {
    Pt s, e;
};
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double d, dx, dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    d = a1*b2 - a2*b1;
    dx = c1*b2 - c2*b1;
    dy = a1*c2 - a2*c1;
    if(fabs(d) < eps) // NONE or LINE
        return 0;
    p.x = dx / d, p.y = dy / d;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
    printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
    printf("%lf %lf\n", p.x, p.y);*/
    return onSeg(a.s, a.e, p) && onSeg(b.s, b.e, p);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x * p[i+1].y - p[i].y * p[i+1].x;
    return fabs(ret)/2;
}
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;
}
#define INF 1e+30 
double smallRect(int n, Pt ch[]) {
    double lx, ly, rx, ry;
    int up, down, left, right;
    double ret = INF;
    lx = ly = INF;
    rx = ry = -INF;
    
    up = down = left = right = 0;
    for(int i = 0; i < n; i++) {
        if(ch[i].x > rx)	rx = ch[i].x, right = i;
        if(ch[i].y > ry)	ry = ch[i].y, up = i;
        if(ch[i].x < lx)	lx = ch[i].x, left = i;
        if(ch[i].y < ly)	ly = ch[i].y, down = i;
    }
    
    int corner[] = {up, down, left, right};
    Pt vec[] = {Pt(-1, 0), Pt(1, 0), Pt(0, -1), Pt(0, 1)};
    
    ret = (rx - lx) * (ry - ly);
    for(int j = 0; j < 4; j++) {
        while(true) {
            Pt a = ch[corner[j]], b = ch[(corner[j]+1)%n], c = vec[j];
            if(fabs(cross2(b - a, c)) < eps)
                corner[j] = (corner[j] + 1)%n;
            else
                break;
        }
    }
//	for(int j = 0; j < 4; j++) {
//		Pt a = ch[corner[j]], b = vec[j];
//		printf("Pt[%lf %lf], Vector[%lf %lf]\n", a.x, a.y, b.x, b.y);
//	}	
    for(int i = 0; i < n; i++) {
        double mxVal = -INF, cos, sin;
        int mxIdx = 0;
        for(int j = 0; j < 4; j++) {
            Pt a = ch[corner[j]], b = ch[(corner[j]+1)%n], c = vec[j];
            double cosA = dot(b - a, c) / dist(b, a) / dist(c, Pt(0, 0));
            if(mxVal < cosA)
                mxVal = cosA, mxIdx = j;
//			printf("cos %lf\n", cosA);
        }
        cos = mxVal, sin = sqrt(1 - cos * cos);
//		printf("sin %lf cos %lf\n", sin, cos);
        for(int j = 0; j < 4; j++) {
            double tx, ty;
            tx = vec[j].x * cos - vec[j].y * sin;
            ty = vec[j].x * sin + vec[j].y * cos;
            vec[j] = Pt(tx, ty);
//			printf("%lf %lf\n", tx, ty);
        }
//		for(int j = 0; j < 4; j++) {
//			Pt a = ch[corner[j]], b = vec[j];
//			printf("Pt[%lf %lf], Vector[%lf %lf]\n", a.x, a.y, b.x, b.y);
//		}		
        for(int j = 0; j < 4; j++) {
            while(true) {
                Pt a = ch[corner[j]], b = ch[(corner[j]+1)%n], c = vec[j];
                if(fabs(cross2(b - a, c)) < eps)
                    corner[j] = (corner[j] + 1)%n;
                else
                    break;
            }
        }
        double w = distProjection(ch[corner[0]], ch[corner[0]]+vec[0], ch[corner[1]]);
        double h = distProjection(ch[corner[2]], ch[corner[2]]+vec[2], ch[corner[3]]);
//		printf("w %lf h %lf area %lf\n\n", w, h, w * h);
        ret = min(ret, w * h);
    }
    return ret;
}
int main() {
    Pt p[2048], ch[2048];
    int n, m;
    int testcase, cases = 0;
    while(scanf("%d", &n) == 1 && n) {
    	for(int i = 0; i < n; i++)
    		scanf("%lf %lf", &p[i].x, &p[i].y);
        m = monotone(n, p, ch);
//        for(int i = 0; i < m; i++)
//        	printf("%lf %lf\n", ch[i].x, ch[i].y);
    	
    	if(m < 3) {
    		printf("%.4lf\n", 0);
    		continue;
    	}
        double ret = smallRect(m, ch);
        printf("%.4lf\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10148 - Advertisement

Problem

The Department of Recreation has decided that it must be more profitable, and it wants to sell advertising space along a popular jogging path at a local park. They have built a number of billboards (special signs for advertisements) along the path and have decided to sell advertising space on these billboards. Billboards are situated evenly along the jogging path, and they are given consecutive integer numbers corresponding to their order along the path. At most one advertisement can be placed on each billboard.

A particular client wishes to purchase advertising space on these billboards but needs guarantees that every jogger will see it’s advertisement at least K times while running along the path. However, different joggers run along different parts of the path.

Interviews with joggers revealed that each of them has chosen a section of the path which he/she likes to run along every day. Since advertisers care only about billboards seen by joggers, each jogger’s personal path can be identified by the sequence of billboards viewed during a run. Taking into account that billboards are numbered consecutively, it is sufficient to record the first and the last billboard numbers seen by each jogger.

Unfortunately, interviews with joggers also showed that some joggers don’t run far enough to see K billboards. Some of them are in such bad shape that they get to see only one billboard (here, the first and last billboard numbers for their path will be identical). Since out-of-shape joggers won’t get to see K billboards, the client requires that they see an advertisement on every billboard along their section of the path. Although this is not as good as them seeing K advertisements, this is the best that can be done and it’s enough to satisfy the client.

In order to reduce advertising costs, the client hires you to figure out how to minimize the number of billboards they need to pay for and, at the same time, satisfy stated requirements.

Input

The first line of the input consist of an integer indicating the number of test cases in theinput. Then there’s a blank line and the test cases separated by a blank line.

The first line of each test case contains two integers K and N (1 ≤ K, N ≤ 1000) separated by a space. K is the minimal number of advertisements that every jogger must see, and N is the total number of joggers.

The following N lines describe the path of each jogger. Each line contains two integers Ai and Bi (both numbers are not greater than 10000 by absolute value). Ai represents the first billboard number seen by jogger number i and Bi gives the last billboard number seen by that jogger. During a run, jogger i will see billboards Ai, Bi and all billboards between them.

Output

On the first line of the output fof each test case, write a single integer M. This number gives the minimal number of advertisements that should be placed on billboards in order to fulfill the client’s requirements. Then write M lines with one number on each line. These numbers give (in ascending order) the billboard numbers on which the client’s advertisements should be placed. Print a blank line between test cases.

Sample input

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

Sample output for the sample input

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

Solution

題目描述：

現在有 N 個慢跑者，每位慢跑者每天都會在固定的區間 [l, r] 中慢跑，廣告商希望每位跑者都能在跑的過程中見到 K 次廣告。

請問至少要在幾個整數點座標上放置廣告，才能使得每個跑者看到 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
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int testcase, N, K, l, r;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &K, &N);
        vector< pair<int, int> > D;
        for(int i = 0; i < N; i++) {
            scanf("%d %d", &l, &r);
            if(l > r)	swap(l, r);
            D.push_back(make_pair(r, l));
        }
        sort(D.begin(), D.end());
        
        int used[20005] = {}, ret = 0;
        const int shift = 10000;
        for(int i = 0; i < N; i++) {
            int has = 0, l = D[i].second, r = D[i].first;
            for(int j = l; j <= r; j++)
                has += used[j + shift];
            for(int j = r; j >= l && has< K; j--)
                if(!used[j + shift])
                    has++, used[j + shift] = 1, ret++;
        }
        printf("%d\n", ret);
        for(int i = 0; i < 20005; i++)
            if(used[i])
                printf("%d\n", i - shift);
        if(testcase)
            puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10123 - No Tipping

Problem

As Archimedes famously observed, if you put an object on a lever arm, it will exert a twisting force around the lever’s fulcrum. This twisting is called torque and is equal to the object’s weight multiplied by its distance from the fulcrum (the angle of the lever also comes in, but that does not concern us here). If the object is to the left of the fulcrum, the direction of the torque is counterclockwise; if the object is to the right, the direction is clockwise. To compute the torque around a support, simply sum all the torques of the individual objects on the lever.

The challenge is to keep the lever balanced while adjusting the objects on it. Assume you have a straight, evenly weighted board, 20 meters long and weighing three kilograms. The middle of the board is the center of mass, and we will call that position 0. So the possible positions on the board range from -10 (the left end) to +10 (the right end). The board is supported at positions -1.5 and +1.5 by two equal fulcrums, both two meters tall and standing on a flat floor. On the board are six packages, at positions -8, -4, -3, 2, 5 and 8, having weights of 4, 10, 10, 4, 7 and 8 kilograms, respectively as in the picture below.

Your job is to remove the packages one at a time in such a way that the board rests on both supports without tipping. The board would tip if the net torque around the left fulcrum (resulting from the weights of the packages and the board itself) were counterclockwise or if the net torque around the right fulcrum were clockwise. A possible solution to this problem is: first remove the package at position -4, then the package at 8, then -8, then 5, then -3 and finally 2.

You are to write a program which solves problems like the one described above. The input contains multiple cases. Each case starts with three integers: the length of the board (in meters, at least 3), the weight of the board (in kilograms) and n the number of packages on the board (n <= 20). The board is supported at positions -1.5 and +1.5 by two equal fulcrums, both two meters tall and standing on a flat floor. The following n lines contain two integers each: the position of a package on board (in meters measured from the center, negative means to the left) and the weight of the package (in kilograms). A line containing three 0’s ends the input. For each case you are to output the number of the case in the format shown below and then n lines each containing 2 integers, the position of a package and its weight, in an order in which the packages can be removed without causing the board to tip. If there is no solution for a case, output a single line Impossible. There is no solution if in the initial configuration the board is not balanced.

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
20 3 6
-8 4
-4 10
-3 10
2 4
5 7
8 8
20 3 15
1 10 
8 5
-6 8
5 9
-8 4
8 10
-3 10
-4 5
2 9
-2 2
3 3
-3 2
5 1
-6 1
2 5
30 10 2
-8 100
9 91
0 0 0

Possible Output for 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
Case 1:
-4 10
8 8
-8 4
5 7
-3 10
2 4
Case 2:
1 10 
8 5
-6 8
5 9
-8 4
8 10
-3 10
-4 5
2 9
-2 2
3 3
-3 2
5 1
-6 1
2 5
Case 3:
Impossible

Solution

題目描述：

給定一個木板，有兩個支撐點位於 -1.5 和 1.5 上，現在還附加了許多物件在木板上，要如何依序將物件拿起，同時不會讓木板因為不平衡而倒塌。

題目解法：

如何才能算是不平衡？

對於左支持點失去平衡為－其左力矩大於右力矩，因此向左傾斜
對於右支持點失去平衡為－其右力矩大於左力矩，因此向右傾斜

因此，根據貪婪的想法，中間 [-1.5, 1.5] 之間的物件肯定是最後才移走 (移走將減少力矩，因為它們貢獻給左支撐點的右力矩和右支持點的左力矩)。

之後，窮舉其他沒辦法判定的物件，依照產生的力矩由小到大依序窮舉，每一次決策要拿走左方還是右方最小力矩的物件，考慮較大力矩物件是沒有意義的。

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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
int L, W, N, M;
vector< pair<int, int> > LEFT, RIGHT, D;
int find_flag; 
pair<int, int> path[128], pick[128];
int check(int n) {
    double LL, LR, RL, RR;
    LL = LR = RL = RR = 0;
    LL = RR = (L/2.0 - 1.5) * (L/2.0 - 1.5) * W / (double)L / 2;
    LR = RL = (L/2.0 + 1.5) * (L/2.0 + 1.5) * W / (double)L / 2;
    for(int i = 0; i < M; i++) {
        if(pick[i].first < -1.5) {
            LL += fabs(pick[i].first - (-1.5)) * pick[i].second;
        } else {
            LR += fabs(pick[i].first - (-1.5)) * pick[i].second;
        }
        if(pick[i].first < 1.5) {
            RL += fabs(pick[i].first - (1.5)) * pick[i].second;
        } else {
            RR += fabs(pick[i].first - (1.5)) * pick[i].second;
        }
    }
    for(int i = 0; i <= n; i++) {
        if(path[i].first < -1.5) {
            LL += fabs(path[i].first - (-1.5)) * path[i].second;
        } else {
            LR += fabs(path[i].first - (-1.5)) * path[i].second;
        }
        if(path[i].first < 1.5) {
            RL += fabs(path[i].first - (1.5)) * path[i].second;
        } else {
            RR += fabs(path[i].first - (1.5)) * path[i].second;
        }
    }
    return LL <= LR && RR <= RL;
}
void dfs(int l, int r, int dep) {
    if(l == LEFT.size() && r == RIGHT.size()) {
        find_flag = 1;
        for(int i = dep-1; i >= 0; i--)
            printf("%d %d\n", path[i].first, path[i].second);		
        for(int i = 0; i < M; i++)
            printf("%d %d\n", pick[i].first, pick[i].second);
        return;
    }
    if(l < LEFT.size()) {
        path[dep] = D[LEFT[l].second];
        if(check(dep))
            dfs(l+1, r, dep+1);
        if(find_flag)	return;
    }
    if(r < RIGHT.size()) {
        path[dep] = D[RIGHT[r].second];
        if(check(dep))
            dfs(l, r+1, dep+1);
        if(find_flag)	return;
    }
}
int main() {
    int cases = 0, p, q;
    while(scanf("%d %d %d", &L, &W, &N) == 3 && L + W + N) {
        LEFT.clear(), RIGHT.clear(), D.clear();
        M = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d %d", &p, &q);
            D.push_back(make_pair(p, q));
            if(abs(p) < 1.5) {
                pick[M++] = make_pair(p, q);
                continue;
            }
            if(p < 0) {
                LEFT.push_back(make_pair((fabs(2*p) - 3) * q, i));
            } else {
                RIGHT.push_back(make_pair((fabs(2*p) - 3) * q, i));
            }
        }
        sort(LEFT.begin(), LEFT.end());
        sort(RIGHT.begin(), RIGHT.end());
        find_flag = 0;
        printf("Case %d:\n", ++cases);
        dfs(0, 0, 0);
        if(!find_flag)
            puts("Impossible");
    }	
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1314 - Hidden Password

Problem

Some time the programmers have very strange ways to hide their passwords. See for example how Billy “Hacker” Geits hide his password. Billy chooses a string S composed of small Latin letters with length L. Then he makes all L- 1 one-letter left cyclic shifts of the string and takes as a password one prefix of the lexicographically first of the obtained strings (including S). For example let consider the string alabala. The cyclic one-letter left shifts (including the initial string) are:

alabala
labalaa
abalaal
balaala
alaalab
laalaba
aalabal

and lexicographically first of them is the string aalabal. The first letter of this string is in position 6 in the initial string (the positions in the string are counted from 0).

Write a program that for given string S finds the start position of the smallest lexicographically one-letter left cyclic shift of this string. If the smallest lexicographically left shift appears more than once then the program have to output the smallest initial position.

Input

Your program has to be ready to solve more than one test case. The first line of the input file will contains only the number T of the test cases. Each of the following T lines will describe one test case - first the length L of the string (5 <= L <= 100000) and then, separated by one space, the string S itself.

Output

The output file have to contain exactly T lines with a single number each - the initial position found by your program.

Sample Input

1
2
3
2
6 baabaa
7 alabala

Sample Output

1
2
1
6

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
#include <stdio.h>
#include <string.h>
int MinExp(const char *s, const int slen) {
    int i = 0, j = 1, k = 0, x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)	x -= slen;
        if(y >= slen)	y -= slen;
        if(s[x] == s[y]) {
            k++;
        } else if(s[x] > s[y]) {
            i = j+1 > i+k+1 ? j+1 : i+k+1;
            k = 0;
            tmp = i, i = j, j = tmp;
        } else {
            j = i+1 > j+k+1 ? i+1 : j+k+1;
            k = 0;
        }
    }
    return i;
}
int main() {
    int testcase, n;
    char s[100005];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %s", &n, s);
        printf("%d\n", MinExp(s, n));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1194 - Machine Schedule

Problem

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.

There are two machines A and B . Machine A has n kinds of working modes, which is called mode0 , mode1 , … , moden-1 , likewise machine B has m kinds of working modes, mode0 , mode1 , … , modem-1 . At the beginning they are both work at mode0 .

For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode3 or in machine B at mode4 , job 1 can either be processed in machine A at mode2 or in machine B at mode4 , and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y) , which means it can be processed either in machine A at modex , or in machine B at modey .

Obviously, to accomplish all the jobs, we need to change the machine’s working mode from time to time, but unfortunately, the machine’s working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.

Input

The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n , m (n, m < 100) and k (k < 1000) . The following k lines give the constrains of the k jobs, each line is a triple: i, x, y .

The input will be terminated by a line containing a single zero.

Output

The output should be one integer per line, which means the minimal times of restarting machine.

Sample Input

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

Sample Output

1
3

Solution

題目描述：

有兩台機器 A, B，各自擁有 n 和 m 個模式，在 k 個工作中，每一個工作可以在 A 機器的 a 模式或者是 B 機器的 b 模式下完成。

一開始兩台機器皆處於模式 0，而轉換模式是很費時間，希望轉換次數越少越好來完成所有工作。

題目解法：

由於一開始處於模式 0，所以工作在模式 0 下可以完成的全部忽略！

接著考慮建二分圖，分別對每一個工作所需要的模式 a, b 拉邊，最後會採用最少點集覆蓋所有條邊即可。

二分圖最少點集覆蓋 = 二分圖最大匹配數

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
    int y;
    int next;
} edge[10005];
int e, head[105];
void addEdge(int x, int y) {
    edge[e].y = y;
    edge[e].next = head[x], head[x] = e++;
}
int mx[105], my[105], used[105];
int dfs(int now) {
    int i, x;
    for(i = head[now]; i != -1; i = edge[i].next) {
        x = edge[i].y;
        if(!used[x]) {
            used[x] = 1;
            if(my[x] == -1 || dfs(my[x])) {
                mx[now] = x, my[x] = now;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    int N, M, K, u, v;
    while(scanf("%d %d %d", &N, &M, &K) == 3 && N) {
        e = 0;
    	memset(head, -1, sizeof(head));	
    	for(int i = 0; i < K; i++) {
    		scanf("%*d %d %d", &u, &v);
    		if(u > 0 && v > 0)
    			addEdge(u, v);
    	}
    	memset(mx, -1, sizeof(mx));
        memset(my, -1, sizeof(my));
        int match = 0;
        for(int i = 0; i < N; i++) {
            if(mx[i] == -1) {
                memset(used, 0, sizeof(used));
                if(dfs(i))
                    match++;
            }
        }
        printf("%d\n", match);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1093 - Castles

Problem

Wars have played a significant role in world history. Unlike modern wars, armies in the middle ages were principally concerned with capturing and holding castles, the private fortified residences of lords and nobles. The size of the attacking army was an important factor in an army’s ability to capture and hold one of these architectural masterpieces.

\epsfbox{p4788.eps}

A certain minimum number of soldiers were required to capture a castle. Some soldiers were expected to die during the attack. After capturing the castle, some soldiers were required to remain in the castle to defend it against attacks from another enemy. Of course, those numbers were different for different castles. Commanders of the armies were obliged to consider the number of soldiers required for victory. For example, there are five castles in the region map shown in Figure 2. The castle at the lower right requires at least 20 soldiers to wage a winning attack. None are expected to perish during the attack, and 10 soldiers must be left in the castle when the army moves on.

In this problem you must determine the minimum size of an army needed to capture and hold all the castles in a particular region. For reasons of security, there is exactly one (bi-directional) route between any pair of castles in the region. Moving into the neighborhood of an uncaptured castle begins an attack on that castle. Any castle can serve as the first castle to be attacked, without regard for how the army got there. Once any castle has been captured, the requisite number of soldiers is left in the castle to defend it, and the remainder of the army moves on to do battle at another castle, if any remain uncaptured. The army may safely pass through the neighborhood of a castle that it has already captured. But because of the potential for attacks, the army may traverse the route between a pair of castles no more than twice (that is, at most once in each direction).

Input

The input contains multiple test cases corresponding to different regions. The description of the castles in each region occupies several lines. The first line contains an integer n$\le$100 that is the number of castles in the region. Each of the next n lines contains three integers a, m, and g (1$\le$a$\le$1000, 0$\le$m$\le$a, 1$\le$g$\le$1000), that give the minimum number of soldiers required to successfully attack and capture a particular castle, the number of soldiers that are expected to die during the attack, and the number of soldiers that must be left at the castle to defend it. The castles are numbered 1 to n, and the input lines describing them are given in increasing order of castle numbers. Each of the remaining n - 1 lines in a test case has two integers that specify the castle numbers of a pair of castles that are connected by a direct route.

A line containing 0 follows the description of the last region.

Output

For each test case, display the case number and the minimum number of soldiers in the army needed to conquer all the castles in the region. Follow the format shown in the sample output.

Sample Input

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

Sample Output

1
2
Case 1: 22 
Case 2: 65

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
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> g[105];
pair<int, int> D[105];
bool cmp(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first)
        return a.first > b.first;
    return a.second < b.second;
}
pair<int, int> dfs(int u, int p) {
    vector< pair<int, int> > branch;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if(v != p)
            branch.push_back(dfs(v, u));
    }
    sort(branch.begin(), branch.end(), cmp);
    int a, b;
    a = D[u].first, b = D[u].second;
    for(int i = 0; i < branch.size(); i++) {
        a = max(a, b + branch[i].first);
        b += branch[i].second;
    }
    return make_pair(max(a, b), b);
    
}
int main() {
    int cases = 0, a, m, gg, u, v;
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf("%d %d %d", &a, &m, &gg);	
            D[i] = make_pair(max(a, m+gg), m + gg);
        }
        for(int i = 1; i <= N; i++)
            g[i].clear();
        for(int i = 1; i < N; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        pair<int, int> ret = make_pair(0x3f3f3f3f, 0x3f3f3f3f);
        for(int i = 1; i <= N; i++) 
            ret = min(ret, dfs(i, -1));
        printf("Case %d: %d\n", ++cases, ret.first);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 246 - 10-20-30

Problem

A simple solitaire card game called 10-20-30 uses a standard deck of 52 playing cards in which suit is irrelevant. The value of a face card (king, queen, jack) is 10. The value of an ace is one. The value of each of the other cards is the face value of the card (2, 3, 4, etc.). Cards are dealt from the top of the deck. You begin by dealing out seven cards, left to right forming seven piles. After playing a card on the rightmost pile, the next pile upon which you play a card is the leftmost pile.

For each card placed on a pile, check that pile to see if one of the following three card combinations totals 10, 20, or 30.

  1. the first two and last one,

  2. the first one and the last two, or

  3. the last three cards.

If so, pick up the three cards and place them on the bottom of the deck. For this problem, always check the pile in the order just described. Collect the cards in the order they appear on the pile and put them at the bottom of the deck. Picking up three cards may expose three more cards that can be picked up. If so, pick them up. Continue until no more sets of three can be picked up from the pile.

For example, suppose a pile contains 5 9 7 3 where the 5 is at the first card of the pile, and then a 6 is played. The first two cards plus the last card (5 + 9 + 6) sum to 20. The new contents of the pile after picking up those three cards becomes 7 3. Also, the bottommost card in the deck is now the 6, the card above it is the 9, and the one above the 9 is the 5.

If a queen were played instead of the six, 5 + 9 + 10 = 24, and 5 + 3 + 10 = 18, but 7 + 3 + 10 = 20, so the last three cards would be picked up, leaving the pile as 5 9.

If a pile contains only three cards when the three sum to 10, 20, or 30, then the pile “disappears” when the cards are picked up. That is, subsequent play skips over the position that the now-empty pile occupied. You win if all the piles disappear. You lose if you are unable to deal a card. It is also possible to have a draw if neither of the previous two conditions ever occurs.

Write a program that will play games of 10-20-30 given initial card decks as input.

Input

Each input set consists of a sequence of 52 integers separated by spaces and/or ends of line. The integers represent card values of the initial deck for that game. The first integer is the top card of the deck. Input is terminated by a single zero (0) following the last deck.

Output

For each input set, print whether the result of the game is a win, loss, or a draw, and print the number of times a card is dealt before the game results can be determined. (A draw occurs as soon as the state of the game is repeated.) Use the format shown in the ``Sample Output” section.

Sample Input

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

Sample Output

1
2
3
Win : 66
Loss: 82
Draw: 73

Solution

給一副牌，按照順序發成七疊
在發了一張牌後，若有
(1) 下面一張與最上面兩張
(2) 下面兩張與最上面一張
(3) 最上面連續三張加起來點數為
10、20 或 30，則把這三張牌收進手牌(J, Q, K, 10)
依 (1)(2)(3) 順序檢查

若某疊牌拿起三張後仍符合上述條件，則一直拿到不符合條件為止，若有某一疊牌被完全拿光，則以後不在往這疊發牌。

請輸出最後結果
(1) win 七疊牌都清空了
(2) lose 手牌空了
(3) draw 進入無窮迴圈

簡單地說，一開始盤面上有七疊牌組，一開始都有兩張牌，接著依序從左邊至右開始發牌，發的同時依序檢查是否可以將牌組的牌符合 10-20-30 的規則收回手牌 (發牌者手上) 中。

最麻煩的地方在於迴圈判斷，在這裡使用一個最簡單的 binary tree 方式。

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
#include <stdio.h> 
#include <string.h>
#include <deque>
#include <queue>
#include <set>
using namespace std;
struct state {
    int v[64];
    state() {
        memset(v, 0, sizeof(v));
    }
    bool operator<(const state &x) const {
        return memcmp(v, x.v, sizeof(state)) < 0;
    }
};
deque<int> pile[7];
queue<int> hand;
set<state> record;
void reduce(deque<int> &pile) {
    while(pile.size() >= 3) {
        int n = pile.size();
        if((pile[0] + pile[1] + pile[n-1])%10 == 0) {
            hand.push(pile[0]), hand.push(pile[1]), hand.push(pile[n-1]);
            pile.pop_front();
            pile.pop_front();
            pile.pop_back();
        } else if((pile[0] + pile[n-2] + pile[n-1])%10 == 0) {
            hand.push(pile[0]), hand.push(pile[n-2]), hand.push(pile[n-1]);
            pile.pop_front();
            pile.pop_back();
            pile.pop_back();
        } else if((pile[n-3] + pile[n-2] + pile[n-1])%10 == 0) {
            hand.push(pile[n-3]), hand.push(pile[n-2]), hand.push(pile[n-1]);
            pile.pop_back();
            pile.pop_back();
            pile.pop_back();
        } else {
            break;
        }
    }
}
int main() {
    int x;
    while(true) {
        while(!hand.empty())
            hand.pop();
        for(int i = 0; i < 7; i++) 
            pile[i].clear();
            
        for(int i = 0; i < 52; i++) {
            scanf("%d", &x);
            if(x == 0)	return 0;
            hand.push(x);
        }
        for(int i = 0; i < 7; i++)
            pile[i].push_back(hand.front()), hand.pop();
        
        for(int i = 0; i < 7; i++)
            pile[i].push_back(hand.front()), hand.pop();
        
        int end = 0, loop = 14;
        while(!end) {
            for(int i = 0; i < 7; i++) {
                if(pile[i].size() == 0)
                    continue;
                loop++;
                pile[i].push_back(hand.front()), hand.pop();
                reduce(pile[i]);
                if(hand.size() == 52) {
                    printf("Win : %d\n", loop);
                    end = 1;
                    break;
                }
                if(hand.size() == 0) {
                    printf("Loss: %d\n", loop);
                    end = 1;
                    break;
                }
                state s;
                int m = 0;
                for(int j = 0; j < 7; j++) {
                    for(int k = 0; k < pile[j].size(); k++)
                        s.v[m++] = pile[j][k];
                    s.v[m++] = 15;
                }
                queue<int> q = hand;
                while(!q.empty())
                    s.v[m++] = q.front(), q.pop();
                s.v[m++] = 15;
                if(record.find(s) != record.end()) {
                    printf("Draw: %d\n", loop);
                    end = 1;
                    break;
                }
                record.insert(s);
            }
        }
    }
    return 0;
}
Read More +