# # Google Kick Start 2020 Round F 题解

## # Problem A - ATM Queue (opens new window)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n, x;
vector<pair<int, int>> v;
for (int i = 0; i < n; ++i) {
int a;
v.emplace_back((a - 1) / x + 1, i);
}
sort(v.begin(), v.end());
for (auto vi : v)
printf("%d ", vi.second + 1);
printf("\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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

## # Problem B - Metal Harvest (opens new window)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
using ll = int64_t;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n, k;
vector<pair<ll, ll>> v;
for (int i = 0; i < n; ++i) {
ll s, e;
v.emplace_back(s, e);
}
sort(v.begin(), v.end());
ll ans = 0, r = 0;
for (auto vi : v) {
if (vi.second > r) {
ll l = max(r, vi.first);
ll len = vi.second - l;
ll num = (len - 1) / k + 1;
r = l + num * k;
ans += num;
}
}
printf("%d\n", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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

## # Problem C - Painters' Duel (opens new window)

• $A$可以移动。从所有可选的房间中，我们需要找到一个可以最小化下一步得分的房间（因为在下一步中$A$$B$的身份会互换）。
• $A$无法移动，而$B$可以移动。直接交换$A$$B$，进入下一步操作。
• $A$$B$都无法移动。这是边界条件，返回$0$

#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
typedef long long ll;
const ll mask = (1 << 10) - 1;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

ll encode(ll state, ll a, ll b) { return state | (a << 50) | (b << 40); }

class Solution {
unordered_map<ll, int> memo;
void connect(int u, int v) {
}
int dfs(ll state, ll a, ll b) {
ll code = encode(state, a, b);
if (memo.count(code))
return memo[code];
bool a_can_move = false, b_can_move = false;
int lo = 100;
for (int u : adj[a]) {
if (state & (1ll << u))
continue;
a_can_move = true;
int result = dfs(state | (1ll << u), b, u);
lo = min(lo, result);
}
if (a_can_move) {
memo[code] = 1 - lo;
return memo[code];
}
for (int u : adj[b]) {
if (state & (1ll << u))
continue;
b_can_move = true;
break;
}
if (!b_can_move) {
memo[code] = 0;
return 0;
}
memo[code] = -dfs(state, b, a);
return memo[code];
}

public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int s, ra, pa, rb, pb, c;
int n = s * s;
auto encode = [&](int i, int j) { return (i - 1) * (i - 1) + j; };
vector<bool> ban(n + 1);
for (int i = 0; i < c; ++i) {
int ri, pi;
ban[encode(ri, pi)] = true;
}
for (int i = 1; i <= s; ++i)
for (int j = 1; j <= i * 2 - 1; ++j) {
int u = encode(i, j);
if (j < i * 2 - 1) {
int v1 = encode(i, j + 1);
if (!ban[v1])
connect(u, v1);
}
if (j % 2 == 1 && i < s) {
int v2 = encode(i + 1, j + 1);
if (!ban[v2])
connect(u, v2);
}
}
ll start = 0;
for (int i = 1; i <= n; ++i)
if (ban[i])
start |= (1ll << i);
ll a = encode(ra, pa), b = encode(rb, pb);
start |= (1ll << a);
start |= (1ll << b);
printf("%d\n", dfs(start, a, b));
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

## # Problem D - Yeetzhee (opens new window)

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
int n, m, k;
vector<int> a(k);
vector<int> cnt(n + 1);
for (int i = 0; i < k; ++i)
int hi = a.back();
vector<int> target(hi + 1);
target[0] = m - k;
for (int i = 1; i <= hi; ++i)
target[i] = target[i - 1] + cnt[i];
map<vector<int>, double> p, e;
vector<int> raw(hi + 1, m);
p[raw] = 1, e[raw] = 0;
for (int i = 1; i <= n; ++i) {
map<vector<int>, double> np, ne;
for (const auto &pr : p) {
const vector<int> &state = pr.first;
double pi = pr.second;
double ei = e[state];
int good = 0;
vector<pair<int, int>> choices;
for (int j = 0; j < hi; ++j) {
if (state[j] == target[j])
continue;
int rem = state[j] - (j == 0 ? 0 : state[j - 1]);
if (!rem)
continue;
good += rem;
choices.emplace_back(j, rem);
}
for (auto choice : choices) {
int j = choice.first, c = choice.second;
vector<int> nxt(state);
nxt[j]--;
double pnxt = pi * c / good;
np[nxt] += pnxt;
updates.emplace_back(nxt, make_pair(pnxt, ei + (double)m / good));
}
}
for (const auto &update : updates) {
const vector<int> &nxt = update.first;
double pnxt = update.second.first, enxt = update.second.second;
ne[nxt] += pnxt / np[nxt] * enxt;
}
p = move(np);
e = move(ne);
}
double ans = 0;
for (auto pr : e)
ans += pr.second * p[pr.first];
printf("%.8f\n", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88