2015 Google Code Jam Round 1A

contents

  1. 1. 題解
  2. 2. A code
  3. 3. B code
  4. 4. C code
    1. 4.1. small
    2. 4.2. large
      1. 4.2.1. Tricky Test Case
      2. 4.2.2. Output

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

windows format to linux format

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

題解

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

[A. Mushroom Monster]O(N)

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

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

[B. Haircut]O(N log N)

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

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

[C. Logging]O(2^N * N log N) -> O(N^2 log N)

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

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

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

A code

GCJ20151A - Mushroom Monster
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Fucking English
#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
int testcase, n, cases = 0;
long long A[1024];
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);

for (int i = 0; i < n; i++)
scanf("%lld", &A[i]);

long long retA = 0, retB = 0, mx = 0;
for (int i = 1; i < n; i++) {
if (A[i-1] - A[i] > 0) {
retA += A[i-1] - A[i];
mx = max(mx, A[i-1] - A[i]);
}
}
for (int i = 0; i < n - 1; i++) {
if (A[i] > mx)
retB += mx;
else
retB += A[i];
}

printf("Case #%d: %lld %lld\n", ++cases, retA, retB);
}
return 0;
}
/*
4
4
10 5 15 5
2
100 100
8
81 81 81 81 81 81 81 0
6
23 90 40 0 100 9
*/

B code

GCJ20151A - Haircut
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>

int main() {
int testcase, cases = 0;
int N, B;
long long M[1024];
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &B, &N);
for (int i = 0; i < B; i++)
scanf("%lld", &M[i]);

long long l = 0, r = 100000LL * N, mid, time = 0;
while (l <= r) {
mid = (l + r)/2;
long long cnt = 0;
for (int i = 0; i < B; i++)
cnt += mid / M[i] + 1;
if (cnt >= N)
r = mid - 1, time = mid;
else
l = mid + 1;
}

long long cnt = 0;
int id = 0;

for (int i = 0; i < B; i++)
cnt += time / M[i] +(time % M[i] !=0);

cnt = N - cnt;
// printf("%lld %lld\n", cnt, time);
for (int i = 0; i < B; i++) {
if (time % M[i] == 0) {
cnt--;
if (cnt == 0)
id = i;
}
}
printf("Case #%d: %d\n", ++cases, id + 1);
}
return 0;
}

C code

small

GCJ20151A - Logging
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <assert.h>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
double x, y;
Pt(double a = 0, double b = 0):
x(a), y(b) {}
Pt operator-(const Pt &a) const {
return Pt(x - a.x, y - a.y);
}
Pt operator+(const Pt &a) const {
return Pt(x + a.x, y + a.y);
}
Pt operator*(const double a) const {
return Pt(x * a, y * a);
}
bool operator==(const Pt &a) const {
return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
}
bool operator<(const Pt &a) const {
if (fabs(x - a.x) > eps)
return x < a.x;
if (fabs(y - a.y) > eps)
return y < a.y;
return false;
}
double length() {
return hypot(x, y);
}
void read() {
scanf("%lf %lf", &x, &y);
}
};
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
Pt s, e;
double angle;
int label;
Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
// angle = atan2(e.y - s.y, e.x - s.x);
}
bool operator<(const Seg &other) const {
if (fabs(angle - other.angle) > eps)
return angle > other.angle;
if (cross(other.s, other.e, s) > -eps)
return true;
return false;
}
bool operator!=(const Seg &other) const {
return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
}
};
Pt getIntersect(Seg a, Seg b) {
Pt u = a.s - b.s;
double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
double x, y;
x = a.x * cos(radian) - a.y * sin(radian);
y = a.x * sin(radian) + a.y * cos(radian);
return Pt(x, y);
}
const double pi = acos(-1);
int cmpZero(double v) {
if (fabs(v) > eps) return v > 0 ? 1 : -1;
return 0;
}
int monotone(int n, Pt p[], Pt ch[]) {
sort(p, p+n);
int i, m = 0, t;
for(i = 0; i < n; i++) {
while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
for(i = n-1, t = m+1; i >= 0; i--) {
while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
return m-1;
}
int main() {
int testcase, cases = 0;
int n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
Pt P[1024];
for (int i = 0; i < n; i++)
scanf("%lf %lf", &P[i].x, &P[i].y);

int ret[16] = {};
for (int i = 0; i < n; i++)
ret[i] = n;
for (int i = 0; i < (1<<n); i++) {
int m = 0, cnt = 0;
Pt a[32], ch[32];
for (int j = 0; j < n; j++) {
if ((i>>j)&1)
a[m++] = P[j];
}

int cn = monotone(m, a, ch);
for (int p = 0; p < n; p++) {
if ((i>>p)&1)
for (int j = 0, k = cn-1; j < cn; k = j++) {
if (onSeg(ch[j], ch[k], P[p])) {
ret[p] = min(ret[p], n - m);
}
}
}
}
printf("Case #%d:\n", ++cases);
for (int i = 0; i < n; i++)
printf("%d\n", ret[i]);
}
return 0;
}

large

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

Tricky Test Case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
1
30
0 0
-971645 838743
748096 -988877
-652232 -993753
737167 -838743
-48 27
706721 -885828
606199 854425
659001 -993753
898961 885828
-659001 885828
748096 -973880
21 -13
-748096 606199
-732894 991850
13 -12
659001 -737167
-32 -32
737167 -748096
650983 -971645
650983 -732894
854425 -606199
-606199 885828
916399 -988877
652232 -838743
-606199 988877
-620105 -652232
-748096 -737167
24 -23
916399 854425

Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Case #1:
9
0
1
0
3
7
4
2
0
0
2
2
8
1
0
9
7
7
4
3
8
1
2
0
7
0
2
0
9
0

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

GCJ20151A - Logging[fast]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
double x, y;
int label;
Pt(double a = 0, double b = 0, int c = 0):
x(a), y(b), label(c) {}
Pt operator-(const Pt &a) const {
return Pt(x - a.x, y - a.y);
}
Pt operator+(const Pt &a) const {
return Pt(x + a.x, y + a.y);
}
Pt operator*(const double a) const {
return Pt(x * a, y * a);
}
bool operator<(const Pt &a) const {
if (fabs(x - a.x) > eps)
return x < a.x;
if (fabs(y - a.y) > eps)
return y < a.y;
return false;
}
};
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt D[4096];

bool cmp(const Pt& p1, const Pt& p2)
{
if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
if (p1.y * p2.y < 0) return p1.y > p2.y;
double c = cross2(p1, p2);
return c > 0 || c == 0 && fabs(p1.x) < fabs(p2.x);
}
int main() {
int N, testcase, cases = 0;
double x, y;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%lf %lf", &x, &y);
D[i] = Pt(x, y);
}
printf("Case #%d:\n", ++cases);

if (N == 1) {
puts("0");
continue;
}

for (int i = 0; i < N; i++) {
vector< Pt > A;
for (int j = 0; j < N; j++) {
if (i == j)
continue;
Pt p = D[j] - D[i];
A.push_back(p);
}
sort(A.begin(), A.end(), cmp);
int M = (int)A.size();
int l = 0, r = 0, cnt = 1;
int ret = 0;
for (l = 0; l < M; l++) {
if (l == r)
r = (r+1)%M, cnt++;
while (l != r && cross2(A[l], A[r]) >= 0) {
r = (r+1)%M, cnt++;
}
ret = max(ret, cnt);
cnt--;
}
printf("%d\n", N - ret);
}
}
return 0;
}