2015 Google Code Jam Round 1B

contents

  1. 1. 題解
  2. 2. A code
  3. 3. B code
  4. 4. C code

windows format to linux format

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

題解

  • A. Counter Culture
  • B. Noisy Neighbors
  • C. Hiking Deer

[A. Counter Culture]

給定一個數字 N,要求藉由兩種操作從 1 變成 N,第一種操作將當前數字 x 變成 x + 1,第二種操作為 x 變成 reverse(x),並且消除前導為零。求操作的最少次數。

由於 N 很大,搜索沒有搞頭,但關於反轉數字能理解到,當後半部恰好等於目標的前半部時,此時反轉最有利,根據貪心策略進行反轉操作,但要防止前導為 0。關於 x + 1 部分,主要是增加位數。

這時候來逆推吧!降位數 (1000 -> 999, 10000 -> 9999)、反轉貪心 (123654 -> 100321)、WTF 的情況 (19 -> 11 -> 10)。在 WTF 的情況中,反轉無效,怒降一個數字。

[B. Noisy Neighbors]

在 R x C 的網格上,每一格可以租給一個用戶,當用戶之間共享一個邊時,將會增加不滿意程度,求租給 K 名用戶,建築的不滿意程度最低為何。

考慮 K 小的時候,將網格黑白染色,必然只放置在黑色或白色網格上,此時不滿意程度皆為 0。當 K 多餘白色格子或黑色格子時,將會增加不滿意程度,每當增加一格,勢必會挑選相對的顏色 (填滿白色格子後,選黑色格子來填),那麼每一次必須挑最少相鄰邊的格子。

為什麼一定會填滿其中一種顏色?假設最優解存在其中一種顏色未填滿,且存在這一格 x 附近沒有使用的格子,那麼必然存在將一個產生不滿意的格子移動到 x 會是一個更優解。不斷地迭代下去,就是貪心的來源!

[C. Hiking Deer]

跟蹤狂 H 在一個圓從 0 出發繞一圈,H 很討厭人群,因此盡可能不與其他人碰面,H 的能力可以跟蹤在任何人身後。現在知道一群人會不斷地繞著這個圓,並且分別以各自的速度、當前位置,全部人都按著順時針方式繞行,不存在兩個人在相同地點以相同速度。現在從 time = 0 開始,請問 H 至少會發生幾次碰面。

由於是一個環狀,又要考慮繞行的區間最少人數,朝著掃描線思路邁進!保證答案 (碰面次數) 不超過總人數 N,一開始瞬間移動到最快抵達終點的人身上,只會碰到 N - 1 個人!

根據抵達終點的時間排序,維護當前需要的碰面次數 e,假設尾隨編號 i 的人,需要碰面 e 個人!經過掃描一些人後,又遇到 i,表示 i 又繞了一圈,那麼碰面次數 e = e + 1,讓尾隨後面的點時,都會遇到那該死的 i!

A code

GCJ20151B - Counter Culture
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
#include <stdio.h>
#include <string.h>
long long reverseNumber(long long x) {
static char buf[32];
sprintf(buf, "%lld", x);
long long y = 0;
for (int i = strlen(buf) - 1; i >= 0; i--)
y = y * 10 + buf[i] - '0';
return y;
}
long long f(long long n) {
if (n < 10)
return n;
long long half = 1;
while (half * half <= n)
half *= 10;
if (n % half == 0) // 1000 -> 999, 10000 -> 9999
return 1 + f(n - 1);
else {
long long v = reverseNumber(n - n%half + 1);
if (v != n - n%half + 1) // 123654 -> 100321, subtract & reverse
return n%half + f(v);
else // 19 -> 11, but 11 is palindrome, without reverse -> 10
return n%half + f(v-1);
}
}
int main() {
int testcase, cases = 0;
long long n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%lld", &n);
printf("Case #%d: %lld\n", ++cases, f(n));
}
return 0;
}

B code

GCJ20151B - Noisy Neighbors
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 <vector>
#include <algorithm>
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
int testcase, cases = 0;
int N, M, K;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d %d", &N, &M, &K);
vector<int> B, W;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int adj = 0;
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && y >= 0 && x < N && y < M)
adj++;
}
if ((i+j) %2 == 0)
B.push_back(adj), W.push_back(0);
else
B.push_back(0), W.push_back(adj);
}
}
sort(B.begin(), B.end());
sort(W.begin(), W.end());
int cost1 = 0, cost2 = 0, ret = -1;
for (int i = 0; i < K; i++) {
cost1 += B[i];
cost2 += W[i];
}
ret = min(cost1, cost2);
printf("Case #%d: %d\n", ++cases, ret);
}
return 0;
}

C code

GCJ20151B - Hiking Deer
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
#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
const int MAXN = 524288;
int N, pass[MAXN];
struct Node {
long long arrive_time, v;
int id;
Node(long long a = 0, int b = 0, long long c = 0):
arrive_time(a), id(b), v(c) {}
bool operator<(const Node &a) const {
if (arrive_time != a.arrive_time)
return arrive_time < a.arrive_time;
return v < a.v;
}
};
int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &N);
set<Node> pQ;
int id = 0;
long long D, H, M;
for (int i = 0; i < N; i++) {
scanf("%lld %lld %lld", &D, &H, &M);
for (int j = 0; j < H; j++) {
long long arrive_time = (360 - D) * (M + j);
pQ.insert(Node(arrive_time, id, M + j));
pass[id] = 0, id++;
}
}
int ret = id, encounter = id;
for (; encounter <= 2 * id; ) {
Node u = *pQ.begin(); // extract minimum
ret = min(ret, encounter);
if (pass[u.id])
encounter++;
else
encounter--;
pass[u.id] = 1;
pQ.erase(pQ.begin());
pQ.insert(Node(u.arrive_time + u.v * 360, u.id, u.v));
}
printf("Case #%d: %d\n", ++cases, ret);
}
return 0;
}