2015 Google Code Jam Round 1C

contents

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

windows format to linux format

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

題解

• A. Brattleship
• B. Typewriter Monkey
• C. Less Money, More Problems

［A. Brattleship］

哥哥和弟弟玩遊戲，在一個 R * C 的網格中，弟弟會放置一個 1 * W 水平放置的戰艦，接著哥哥蒙上眼睛，問弟弟說 (x, y) 是否為戰艦的一部分，而弟弟很狡猾，可以在猜測過程中偷偷改答案，想辦法去搬移戰艦，使得哥哥猜測數量最多。請問哥哥至少要多少次才能猜到。

R * C 跟 1 * C 其實是一樣的，哥哥仍然必須猜完所有的行，因此至少花費 (R - 1) * floor(C/W) + LastLine 的花費，LastLine 怎麼求得呢？其一方法是貪心，其二方法是 dp 博弈最小化，由於 C <= 20，使用 2^C 進行博弈 dp 是不錯的選擇 (懶人系列，咱走這裡)。

［B. Typewriter Monkey］

給定猴子 K 個鍵盤按鈕，鍵盤按鈕對應的字母可能會重複，每個按鈕敲擊的機率均勻分布，接著希望猴子敲擊 S 次，統計出現目標長度 L 的字串 (在長度 S 字串中可能會重疊)，當猴子打出一個目標字串就給一條香蕉。人員要準備最慘情況的香蕉個數，請問猴子完成一次後，獎勵猴子後，手上剩餘的香蕉個數的期望值為何？

首先要找出最慘情況的香蕉個數，也就是去找到最大重疊長度 x，暴力搜索即可 (有機會咱們再來談談 KMP)，基本香蕉數量為 1 + (S - L) / (L - x)。接著找到猴子拼出目標字串的期望值，考慮目標字串的起始位置 i 的機率 expect = p(S) * 1^(S - L)，p(S) = \product(uniform(target[i])), i in [1, S - L + 1]
，最後答案顯而易見 = max_banana - expect * (S - L + 1)。

［C. Less Money, More Problems］

給定 D 種不同的面值，每一種面值最多使用 C 次，請問要湊出 [1, V] 之間所有價錢的交易方式，至少要增加幾個新面值。

貪心思路，假設能湊出 [1, S]，則對於新面值 x 而言，可以增加範圍 [1, S + x * C]。將 x 由小排到大，若 S < x - 1 則新增一個面值 S+1 下去，擴張到範圍 [1, S + (S+1) * C] … 如此類推，想辦法湊出 [1, V]。

A code

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;

int dp[1<<20], R, C, W;
int isEnd(int u) {
    int place = (1<<W)-1;
    int v = 0;
    for (int i = 0; i < C - W; i++) {
        if (((u>>i)&place) == 0) 
            return 0; 
        v = min(v, __builtin_popcount(((u>>i)&place)));
    }
    return W - v;
}
int dfs(int u) {
    if (isEnd(u))
        return isEnd(u);
    if (dp[u] != -1)
        return dp[u];
    int &ret = dp[u];
    ret = 0x3f3f3f3f;
    for (int i = 0; i < C; i++) {
        if ((u>>i)&1)
            continue;
        ret = min(ret, dfs(u|(1<<i)) + 1);
    }
    return ret;
}
int solve() {
    memset(dp, -1, sizeof(dp));
    int v = dfs(0);
    return v + (R-1) * (C/W);
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &R, &C, &W);
        printf("Case #%d: %d\n", ++cases, solve());
    }
    return 0;
}
/*
999
1 5 1
1 10 3
 
3
1 4 2
1 7 7
2 5 1
*/

B code

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;

int K, L, S;
char keyboard[128], target[128];
double solve() {
    if (L > S)
        return 0;
    int a[128] = {};
    for (int i = 0; i < K; i++)
        a[keyboard[i]]++;
    for (int i = 0; i < L; i++)
        if (a[target[i]] == 0)
            return 0;
            
    double mx_banana = S / L, expect = 1;
    for (int i = 1; i < L; i++) {
        int ok = 1;
        for (int j = 0; target[i+j] && j < L; j++)
            ok &= target[j] == target[i+j];
        if (ok) {
            mx_banana = 1 + (S - L) / (i); 
            break;
        }
    }
    for (int i = 0; i < L; i++)
        expect = (expect * a[target[i]]) / K;
    return mx_banana - expect * (S - L + 1);
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &K, &L, &S);
        scanf("%s %s", keyboard, target);
        
        double ret = solve();
        printf("Case #%d: %lf\n", ++cases, ret);
    } 
    return 0;
}

C code

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main() {
    int testcase, cases = 0;
    long long C, K, V, x[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %lld %lld", &C, &K, &V);
        
        long long sum = 0, ret = 0;
        for (int i = 0; i < K; i++) {
            scanf("%lld", &x[i]);
        }
        for (int i = 0; i < K; i++) {
            while (sum < V && sum < x[i] - 1) {
                ret++;
                long long ncoin = sum + 1;
                sum += ncoin * C;
            }
            sum += x[i] * C;
        }
        while (sum < V) {
            ret++;
            long long ncoin = sum + 1;
            sum += ncoin * C;
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}
/*

*/