解題區►解題區 - UVa

UVa 11990 - ``Dynamic'' Inversion

Problem

You are given a permutation {1,2,3,…,n}. Remove m of them one by one, and output the number of inversion pairs before each removal. The number of inversion pairs of an array A is the number of ordered pairs (i,j) such that i < j and A[i] > A[j].

Input

The input contains several test cases. The first line of each case contains two integers n and m (1<=n<=200,000, 1<=m<=100,000). After that, n lines follow, representing the initial permutation. Then m lines follow, representing the removed integers, in the order of the removals. No integer will be removed twice. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each removal, output the number of inversion pairs before it.

Sample Input

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

Output for the Sample Input

1
2
3
4
5
2
2
1

Explanation

(1,5,3,4,2)->(1,3,4,2)->(3,4,2)->(3,2)->(3)

Solution

題目描述：

找尋一維數列的逆序對總數，每一次詢問請輸出當時的逆序對個數，隨後將該數字從數列中移除。

題目解法：

一開始可以利用傳統的 D&C 或者是線段樹之類的區間查詢來完成全部的逆序對總數。

隨後要移除某個特定的數字時，要查找該數字前面有多少比它大的數字，以及後面有多少比它小的數字。也就是說，找尋前綴大於某個數字的個數，和找尋後綴小於某個數字的個數，算出有多少對逆序對減少。

這裡使用類似歸併樹的做法，類似合併排序，將會切分成數個區間做排序。並且在每一個區間中會建立一棵離散化後的 binary indexed tree，如果一來記憶體可以在 O(n log n) 解決。

由於我們只需要前綴和後綴的操作，所以說是線段樹可能還有所不及。

每次將前綴拆分成線段樹的數個區間，利用 binary indexed tree，查找當前有多少小於該數字 x 數字被刪除，得到有多少小於 x 的數字還存在 … 之後就可以得到需要的個數。

詳見代碼。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 200005
int N, M, DEL;
int ST[20][MAXN], BIT[20][MAXN];
int MP[MAXN];
long long invPair;
void modifySUM(int BIT[], int x, int v, int L) {
	while(x <= L) {
		BIT[x] += v;
		x += x&(-x);
	}
} 
int querySUM(int BIT[], int x) {
	int ret = 0;
	while(x) {
		ret += BIT[x];
		x -= x&(-x); 
	} 
	return ret;
} 
void buildST(int k, int l, int r, int dep) {
	for(int i = l; i <= r; i++)
		ST[dep][i] = ST[dep-1][i], BIT[dep][i] = 0;
	if(l >= r)	return ;
	int m = (l + r)/2;
	buildST(k<<1, l, m, dep+1);
	buildST(k<<1|1, m+1, r, dep+1);
	sort(ST[dep] + l, ST[dep] + r+1);
}
void queryPrefix(int k, int l, int r, int dep, int x, int y, int val) {
	if(x <= l && r <= y) {
		int pos = upper_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
		int pre = querySUM(BIT[dep]+l-1, pos - l);
		invPair -= (r - pos + 1) - (querySUM(BIT[dep]+l-1, r-l + 1) - pre);
		return ;
	}
	if(l >= r)	return ;
	int m = (l + r)/2;
	if(x <= m)
		queryPrefix(k<<1, l, m, dep+1, x, y, val);
	if(y > m)
		queryPrefix(k<<1|1, m+1, r, dep+1, x, y, val);
}
void querySuffix(int k, int l, int r, int dep, int x, int y, int val) {
	if(x <= l && r <= y) {
		int pos = upper_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
		int pre = querySUM(BIT[dep]+l-1, pos - l);
		invPair -= (pos - l) - pre;
		return ;
	}
	if(l >= r)	return ;
	int m = (l + r)/2;
	if(x <= m)
		querySuffix(k<<1, l, m, dep+1, x, y, val);
	if(y > m)
		querySuffix(k<<1|1, m+1, r, dep+1, x, y, val);
}
void update(int k, int l, int r, int dep, int x, int val) {
	if(l == r) {
		modifySUM(BIT[dep]+l-1, 1, 1, r-l+1);
		return;
	}
	if(l >= r)	return ;
	int m = (l + r)/2;
	if(x <= m)
		update(k<<1, l, m, dep+1, x, val);
	else
		update(k<<1|1, m+1, r, dep+1, x, val);
	int pos = lower_bound(ST[dep] + l, ST[dep] + r+1, val) - ST[dep];
	modifySUM(BIT[dep]+l-1, pos - l + 1, 1, r-l+1);
}
int main() {
	while(scanf("%d %d", &N, &M) == 2) {
		invPair = 0;
		for(int i = 1; i <= N; i++)
			BIT[0][i] = 0;
		for(int i = 1; i <= N; i++) {
			scanf("%d", &ST[0][i]);
			MP[ST[0][i]] = i;
			invPair += i - 1 - querySUM(BIT[0], ST[0][i]);
			modifySUM(BIT[0], ST[0][i], 1, N);
		}
		buildST(1, 1, N, 1);
		
		while(M--) {
			scanf("%d", &DEL);
			printf("%lld\n", invPair);
			queryPrefix(1, 1, N, 1, 1, MP[DEL] - 1, DEL);
			querySuffix(1, 1, N, 1, MP[DEL] + 1, N, DEL);
			update(1, 1, N, 1, MP[DEL], DEL);
		}
	}
	return 0;
}
/*
5 4
1
5
3
4
2
5
*/
Read More +
解題區►解題區 - UVa

UVa 11722 - Joining with Friend

Problem

You are going from Dhaka to Chittagong by train and you came to know one of your old friends is going from city Chittagong to Sylhet. You also know that both the trains will have a stoppage at junction Akhaura at almost same time. You wanted to see your friend there. But the system of the country is not that good. The times of reaching to Akhaura for both trains are not fixed. In fact your train can reach in any time within the interval [t1, t2] with equal probability. The other one will reach in any time within the interval [s1, s2] with equal probability. Each of the trains will stop for w minutes after reaching the junction. You can only see your friend, if in some time both of the trains is present in the station. Find the probability that you can see your friend.

Input

The first line of input will denote the number of cases T (T < 500). Each of the following T line will contain 5 integers t1, t2, s1, s2, w (360 ≤ t1 < t2 < 1080, 360 ≤ s1 < s2 < 1080 and 1 ≤ w ≤ 90). All inputs t1, t2, s1, s2 and w are given in minutes and t1, t2, s1, s2 are minutes since midnight 00:00.

Output

For each test case print one line of output in the format “Case #k: p” Here k is the case number and p is the probability of seeing your friend. Up to 1e-6 error in your output will be acceptable.

Sample Input

1
2
3
2
1000 1040 1000 1040 20
720 750 730 760 16

Output for Sample Input

1
2
Case #1: 0.75000000
Case #2: 0.67111111

Solution

題目描述：

有兩位朋友，分別在 [t1, t2] 和 [s1, s2] 之間內可能會抵達，並且在那邊最多停留 w 單位時間。

問兩個人碰面的機率為何。

題目解法：

將兩個人分別至於 X Y 軸，利用幾何面積找到概率。

對於面積 [t1, t2]x[s1, s2] 只要符合 |t - s| <= w 的面積比例。

由於排容上可能不好理解，直接套用凸包交集的算法，兩個凸包交一定也是凸包。

p11722.png

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
#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;
}
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;
}
int main() {
    Pt a[64], b[64], ret[64], ch[64];
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	int t1, t2, s1, s2, w;
    	int n = 4, m = 4, q;
    	scanf("%d %d %d %d %d", &t1, &t2, &s1, &s2, &w);
    	a[0] = Pt(t1, s1), a[1] = Pt(t2, s1);
    	a[2] = Pt(t2, s2), a[3] = Pt(t1, s2);
    	b[0] = Pt(0, w), b[1] = Pt(0, -w);
    	b[2] = Pt(t2, t2-w), b[3] = Pt(t2, t2+w);
        Seg seg1, seg2;
        int retN = 0;
        for(int i = 0, j = n-1; i < n; j = i++) {
            seg1.s = a[i], seg1.e = a[j];
            for(int p = 0, q = m-1; p < m; q = p++) {
                seg2.s = b[p], seg2.e = b[q];
                if(calcIntersection(seg1, seg2, ret[retN])) {
                    retN++;
                    /*printf("%lf %lf - %lf %lf\n", s1.s.x, s1.s.y, s1.e.x, s1.e.y);
                    printf("%lf %lf - %lf %lf +++\n", s2.s.x, s2.s.y, s2.e.x, s2.e.y);*/
                }
            }
        }
        for(int i = 0; i < n; i++)
            if(inPolygon(b, m, a[i]))
                ret[retN++] = a[i];
        for(int i = 0; i < m; i++)
            if(inPolygon(a, n, b[i]))
                ret[retN++] = b[i];
        q = monotone(retN, ret, ch);
        double area = calcArea(ch, q);
        printf("Case #%d: %.8lf\n", ++cases, area / ((t2 - t1) * (s2 - s1)));
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11266 - Equations

Problem

Find the number of solutions, the equation ∑Xi = s have, if Ai≤Xi≤Bi for each i = 1…n.

For example,

        X1 + X2 + X3 = 10

        -1 ≤ X1 ≤ 3

        2 ≤ X2 ≤ 4

        6 ≤ X3 ≤ 7

The above set of equations has 6 solutions. They are: {1,4,7}, {0,3,7}, {0,4,6}, {1,2,7}, {1,3,6} and {2,2,6}.

You are given n the number of variables and the range of them. Your task is to calculate the number of solutions of that equation.

Input

First line of the Input contains T (≤50) the number of test cases. Then T test cases follow. First line of each test case contains 2 integer n (1≤n≤10) and s (-50000 ≤ s ≤ 50000). Next n lines each contain 2 integers describing the range of each variable. The ith line Ai and Bi (10000 ≤ Ai ≤ Bi ≤10000). Xi can take any integral value in the range [Ai, Bi].

Output:

For each test case output contains one integer denoting the number of solutions of the given equations. Output the value modulo 200003.

Sample Input

1
2
3
4
5
1
3 10
-1 3
2 4
6 7

Sample Output

1
6

Solution

題目描述：

對於每一個變數範圍，找到符合等式的解個數。

題目解法：

直接著手動態規劃，對於 dp[i][j] 定義為使用前 i 個變數，總合為 j 的方法數。

為了加快迴圈操作，必須修改成滑動窗口，為了省記憶體，又使用滾動數組。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int shift = 100000;
int dp[2][200005];
int main() {
	int testcase, n, s;
	int A[16], B[16];
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d", &n, &s);
		for(int i = 0; i < n; i++)
			scanf("%d %d", &A[i], &B[i]);
			
		memset(dp, 0, sizeof(dp));
		for(int i = A[0]; i <= B[0]; i++)
			dp[0][i + shift] = 1;
		int f = 1;
		for(int i = 1; i < n; i++) {
			memset(dp[f], 0, sizeof(dp[f]));
			int l = -B[i], r = -A[i], sum = 0;
			for(int j = 0 - B[i]; j <= 0 - A[i]; j++) {
				if(j < 0 || j >= 200005)
					continue;
				sum += dp[!f][j];
				sum %= 200003;
			}
			for(int j = 0; j < 200005; j++) {
				dp[f][j] = sum;
				if(l >= 0 && l < 200005)
					sum -= dp[!f][l];
				if(r + 1 >= 0 && r + 1 < 200005)
					sum += dp[!f][r+1];
//				if(sum)
//					printf("%d %d %d\n", i, j - shift, sum);
				sum %= 200003;
				l++, r++;
			}
			f = !f;
		}
		printf("%d\n", (dp[!f][s + shift] + 200003)%200003);
	}
	return 0;
}
Read More +
解題區►解題區 - 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 +