2017-01-16

2017 Facebook Hacker Cup 資格賽

1. Facebook Hacker Cup 2017 Qualification Round

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

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

#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

#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

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

Morris' Blog