解題區/解題區 - 其他題目

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;
}