2016 Google Code Jam Round QR

1. A. Counting Sheep
2. B. Revenge of the Pancakes
3. C. Coin Jam
4. D. Fractiles
5. Solution

一年一度的 GCJ 資格賽又開打了，這次的題目類型挺開放的，也就是有很多不同的解法可以通過。也許是因為都用了奇怪的方法解決。全寫完 Rank 400 名以內。

打完比賽完全沒心情寫水泥數學的作業證明。不！其實是不會寫。

A. Counting Sheep

睡覺前數羊，從一個基數 $N$ 開始，數 $N$, $2N$, $3N$, …, $?N$，直到 10 個位數都出現過，請問最後一個數的數 $?N$ 為何。

除了 $N = 0$ 的特殊情況外，直接模擬即可。最重要的是它不只有看個位數字，把每一位全看的狀況下，要湊滿 0-9 所有 digits 都出現過就不是難事。

B. Revenge of the Pancakes

現在 $N$ 個煎餅位於堆上，並且有分成兩個正反面狀態，每一次可以把煎餅從堆頂開始連續得拿出，並反轉序列放回堆中，同時把煎餅正反反轉，請問從一個開始序列轉移到全部皆為正面的操作次數最少為何？

一開始的策略是亂貪心一番，甚至題目看錯都能亂過小測資。必要任務一定是先把堆底那片煎餅翻成正的，這時一定堆頂為反，進行一次反轉讓堆底便成正的，為了讓堆頂為反，貪心策略盡可能讓堆頂一連續全部變成反。不斷地模擬此步驟即可。

C. Coin Jam

產生一個數字 $X$，$X$ 長度恰為 $N$，必須首尾皆為 1，只能由 0/1 構成。請產生數字 $X$，滿足在二進制、三進制 … 到十進制下皆為合成數。

這題莫名其妙指定 $N = 16, \; 32$，特殊的 $N$ 使得找到 $J$ 個 $X$ 並不難，更由於 $J$ 不大，各種解法都可以完成。從以往得概念，假設有一個數字 $A = 123123$，那麼保證不進位的情況下，找得到一組 $A = 123 \times 1001$，因此指定 $A = 1????1$，湊滿 $X = AA \cdots A$，不管在哪個進制下，勢必被 $A$ 整除。

D. Fractiles

詭異的數學碎形考古，給一個長度為 $K$ 的起始字串 $X$，$X$ 只由 $G$ 和 $L$ 構成。碎形迭代 $C$ 次，產生長度為 $K^C$ 的字串。現在雇用 $S$ 個學生，每個學生只能檢查一個位子，只要確定那一個位子有 $G$，那麼原始字串保證有 $G$。在限定學生數量下，請問要怎麼安排學生們的檢查工作。

由於長度為 $K$ 的起始字串有 $2^K$ 種，實際上只要剃除 $LL \cdots L$ 的字串。為了要在最少檢查位置下處理，必然要一個位置能否有 $G$，就能檢查原始字串的數個位置是否有 $G$。

窮舉只有 1 個 $G$ 個字串 $GLL...L$、$LGL...L$、… 等 $K$ 個，追蹤迭代 $C$ 次後，$K^C$ 長度下，每一個字串 $G$ 的出現位置。當 $C = 2$，可以讓位置 1, 2 的 $G$ 可以同時被檢查，同理位置 3, 4 的 $G$ 可以同時被檢查。當 $C = 3$ 時，位置 1, 2, 3 的 $G$ 可以同時被檢查。根據觀察，至少要 $\textit{ceil}(K/C)$ 個學生就能滿足需求。

第 $i$ 個學生要檢查的位置為 $1 + \sum_{0 \le j < C} (C(i-1)+(C-1-j))K^j$。

Solution

A

#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n;
        scanf("%lld", &n);
        if (n == 0) {
            printf("Case #%d: INSOMNIA\n", ++cases);
            continue;
        }
        int has[128] = {}, ten = 10;
        long long on = n;
        while (1) {
            static char buf[32];
            sprintf(buf, "%lld", n);
            for (int i = 0; buf[i]; i++) {
                if (has[buf[i]] == 0) {
                    ten--, has[buf[i]] = 1;
                }
            }
            if (ten == 0)
                break;
            n += on;
        }
        printf("Case #%d: %lld\n", ++cases, n);
    }
    return 0;
}

B

#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int n = strlen(s), ret = 0;
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == '+')	continue;
            int has = 0, j = 0;
            for (j = 0; j <= i; j++) {
                if (s[j] == '-')	break;
                has = 1;
            }
            if (has) {
                reverse(s, s+j);
                for (int k = 0; k < j; k++) {
                    if (s[k] == '-')
                        s[k] = '+';
                    else
                        s[k] = '-';
                }
            }
            ret += has;
            if (s[i] == '+')	continue;
            reverse(s, s+i+1);
            for (int k = 0; k < i+1; k++) {
                if (s[k] == '-')
                    s[k] = '+';
                else
                    s[k] = '-';
            }
            ret++;
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

C

#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, J;
        scanf("%d %d", &N, &J);
        printf("Case #%d:\n", ++cases);
        set<long long> R;
        for (int i = 2; i < N && J; i++) {
            if (N%i)	continue;
            for (int j = 0; j < (1<<(i-2)) && J; j++) {
                int mask = (j<<1)|1|(1<<(i-1));
                long long v = 0;
                for (int k = 0; k < N/i; k++)
                    v = (v<<i) | mask;
                if (R.count(v))	continue;
                R.insert(v);
                for (int k = N-1; k >= 0; k--)
                    printf("%d", (v>>k)&1);
                for (int B = 2; B <= 10; B++) {
                    long long div = 0, nn = 0;
                    for (int k = i-1; k >= 0; k--)
                        div = div * B + ((mask>>k)&1);
                    for (int k = N-1; k >= 0; k--)
                        nn = nn * B + ((v>>k)&1);
//					assert(nn % div == 0 && nn != div);
                    printf(" %lld", div);
                }
                puts("");
                J--;
            }
        }
        assert(J == 0);
    }
    return 0;
}
/*
1
16 3
*/

D

#include <bits/stdc++.h>
using namespace std;
long long mpow(long long x, long long y) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = ret * x;
        y >>= 1, x = x*x;
    }
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long K, C, S;
        scanf("%lld %lld %lld", &K, &C, &S);
        printf("Case #%d:", ++cases);
        
        int pos = 0;
        vector<unsigned long long> A;
//		puts("");
        for (int i = 0; i < ceil(1.f*K/C); i++) {
            int item = min(C, K - pos);
            unsigned long long x = 0;
            for (int j = C-1, k = 0; j >= 0 && k < item; j--, k++) {
//				printf("%d K^%d + ", pos + k, j);
                x += (pos + k) * mpow(K, j);
            }
            A.push_back(x);
//			puts("");
            pos += C;
            if (pos > K)	pos = K;
        }
        if (A.size() > S)
            puts(" IMPOSSIBLE");
        else {
            for (int i = 0; i < A.size(); i++)
                printf(" %llu", A[i]+1);
            puts("");
        }
    }
    return 0;
}
/*
5
4 4 5
*/

Morris' Blog