2017 Facebook Hacker Cup 資格賽

contents

  1. 1. Facebook Hacker Cup 2017 Qualification Round
    1. 1.1. A. Progress Pie
    2. 1.2. B. Lazy Loading
    3. 1.3. C. Fighting the Zombie
    4. 1.4. Solution A
    5. 1.5. Solution B
    6. 1.6. Solution C

原本只是想推碩一學弟去寫,學弟邀著邀著,我這個老骨頭只好跟著寫

Facebook Hacker Cup 2017 Qualification Round

A. Progress Pie

給一個落在 $(0, 0)\; , (100, 100)$ 矩形內部的圓餅圖,並且從垂直十二點方向開始,順時針繞一圈 $P \%$ ,又額外給一座標,請問該點是黑色還是白色,並且保證任何一組詢問點,鄰近 $10^{-6}$ 都屬於相同顏色。

從最後一個條件來看,我們處理邊界條件的誤差是可以容忍的。由於輸入都是整數,完全在整數上操作的部分尚未想到,但我們可以透過內積外積得到詢問點是順時針轉了 $R, \; 0 \le R < 2 \pi$ ,只需要判斷 $R$ 是否小於等於 $P$ 即可。

十二點鐘的方向向量為 $\vec{v} = (0, 50)$ ,詢問點與圓心的向量為 $\vec{u} = (X-50, Y-50)$ ,計算這兩個向量的夾角 $\theta = \cos^{-1}(\frac{u \cdot v}{|u| |v|})$ ,這樣算出來的角度只會落在 $[0, \pi)$ ,接著透過外積決定順時針還是逆時針,補回來即可。

B. Lazy Loading

搬家公司的工人要搬運 $N$ 個重量不同的傢俱,主管要求每次搬運至少 50 磅,工人為了偷懶,每次只搬運一部份的傢俱,然而主管不會準確計算工人搬運的總重,只會問一次搬運的最大重量和個數,工人想藉由分配方法來增加工作天數,請問要怎麼符合需求達到最多搬運天數。

可想而知,我們只需要貪心計算即可,每次挑選最重的那一個,接著搭配當前最輕的來湊數,一超過 50 磅就當作一天的搬運方案,直到沒有物品。一開始排序好 $O(N \log N)$ ,接著只需要掃描一次 $O(N)$ 即可完成。

C. Fighting the Zombie

在 D&D 遊戲中,我們需要施放技能攻擊血量為 $H$ 的殭屍,施放採用擲骰子的方式,骰一個 $Y$ 面骰 $X$ 次得到的點數總和加上固定值 $Z$ ,請問一擊必殺的機率最高為何,由於盤面上有許多骰子可以挑選,請輸出機率最高的那個骰子的機率為何。

首先,我們必須先瞭解最基礎的六面骰,投擲 $X$ 總和的方法數怎麼計算,定義 $\text{dp}[i][j]$ 表示投擲 $i$ 次,點數總和為 $j$ 的方法數。我們得到

$$\begin{align*} dp[i][j] = \left\{\begin{matrix} 1 && i = 0\;, j = 0\\ dp[i-1][j-1] + dp[i-1][j-2] + \cdots + dp[i-1][j-6] && i \le j \\ 0 && \text{otherwise} \end{matrix}\right. \end{align*}$$

上述的遞迴考慮 $i-1$ 個骰子的總和方法數,再決定第 $i$ 個骰子擲出哪一種點數。然而,這種方法不適用此題計算機率,很容易發生 overflow,方法數的總和為 $Y^X$ ,所以一開始我們就採用機率的方式統計。

$$\begin{align*} dp[i][j] = \left\{\begin{matrix} 1 && i = 0\;, j = 0\\ (dp[i-1][j-1] + dp[i-1][j-2] + \cdots + dp[i-1][j-6])/6 && i \le j \\ 0 && \text{otherwise} \end{matrix}\right. \end{align*}$$

這樣的 DP 計算消耗時間 $O(X^2 Y^2)$ ,加上滑動窗口統計總和則可以落在 $O(X^2 Y)$

比賽當下寫的,思路不是很清楚,變數命名和邏輯判斷會有點醜,沒有好好整理。

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
32
33
34
#include <bits/stdc++.h>
using namespace std;

int main() {
const double eps = 1e-8;
const double pi = acos(-1);
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int P, X, Y;
scanf("%d %d %d", &P, &X, &Y);
int ret = 0;

if (X == 50 && Y == 50) {
ret = 1;
} else if (hypot(X-50, Y-50) > 50) {
} else if (P == 100) {
ret = 1;
} else if (P == 0) {

} else {
int vx = X-50, vy = Y-50;
int tx = 0, ty = 50;
double theta = acos((vx*tx+vy*ty)/hypot(vx, vy)/hypot(tx, ty));
if (tx*vy - ty*vx > 0)
theta = 2*pi-theta;
double t = (double) P/100.0*2*pi;
if (theta <= t)
ret = 1;
}
printf("Case #%d: %s\n", ++cases, ret ? "black" : "white");
}
return 0;
}

Solution 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
#include <bits/stdc++.h>
using namespace std;

int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int n;
vector<int> A;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
A.push_back(x);
}
sort(A.begin(), A.end());
int ret = 0;
int r = n-1, l = 0;
while (r >= l) {
int need = ((50 + A[r]-1) / A[r]);
if (l + need-1 > r)
break;
l += need-1, r--;
ret++;
}
printf("Case #%d: %d\n", ++cases, ret);
}
return 0;
}

Solution 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int H, S;
scanf("%d %d", &H, &S);
vector< pair<int, int> > A;
double ret = 0;
for (int i = 0; i < S; i++) {
char s[128];
scanf("%s", s);
int X = 0, Y = 0, Z = 0;
for (int j = 0, x = 0, sign = 1, idx = 0; s[j]; j++) {
if (isdigit(s[j]))
x = x * 10 + s[j] - '0';
if (s[j+1] == '\0' || !isdigit(s[j])) {
x = x * sign;
if (idx == 0)
X = x;
else if (idx == 1)
Y = x;
else
Z = x;
if (s[j] == '-')
sign = -1;
else
sign = 1;
x = 0, idx++;
}
}
int l = X+Z, r = X*Y+Z;
static const int OFF = 1024;
static double dp[2][OFF];
for (int i = 0; i < OFF; i++)
dp[0][i] = dp[1][i] = 0;
dp[0][0] = 1;
for (int i = 0; i < X; i++) {
int p = i&1, q = i&1^1;
for (int j = 0; j < OFF; j++)
dp[q][j] = 0;
for (int j = 0; j < OFF; j++) {
if (dp[p][j] <= 0) continue;
for (int k = 1; k <= Y; k++)
dp[q][j+k] += dp[p][j]*((double) 1.f/Y);
}
}
double sum = 0;
for (int j = 0; j <= X*Y; j++) {
if (j+Z >= H)
sum += dp[(X-1)&1^1][j];
}
ret = max(ret, sum);
}
printf("Case #%d: %.6lf\n",++cases, ret);
}
return 0;
}