2016 Google Code Jam Round QR

contents

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

一年一度的 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

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
#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

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
#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

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

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
#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
*/