2015-04-20

2015 Google Code Jam Round 1A

1. 題解
2. A code
3. B code
4. C code
1. 4.1. small
2. 4.2. large
  1. 4.2.1. Tricky Test Case
  2. 4.2.2. Output

\感謝諸神們替蒟蒻翻譯 GCJ 題目，巨人們/，看完第一題就過了一個小時。

windows format to linux format

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

題解

A. Mushroom Monster
B. Haircut
C. Logging

［A. Mushroom Monster］O(N)

坑爹的蘑菇蘑菇，友人 A 會偷偷增加盤子上的蘑菇，系統每十秒會記錄盤子上蘑菇數量，也就是說給定的序列是系統紀錄盤子上蘑菇的情況，而不是友人 A 放入的蘑菇。接著少兩策略的最少吃掉數量

吃蘑菇策略一，可以在任何時刻吃掉任何數量，策略二，在任何時刻都以某個速度吃蘑菇每秒 f 個，當盤子空的時候，停止餵食。貪心策略，策略一考慮友人 A 盡可能不加蘑菇，策略二考慮友人 A 盡可能讓盤子空，在最後一個時刻 (系統紀錄前) 才放入蘑菇。

［B. Haircut］O(N log N)

理髮師 i 剪一個人需要 Mi 秒，客人 j 呈現 queue 的訪問方式，當有理髮師閒置時，將客人 j 會排入理髮程序。在同一時刻，若存在多名理髮師閒置，編號小的客人優先選擇編號小的理髮師進行流程。請問當所在位置為 N 時，會被指派給哪位理髮師。

二分自己剪髮時間，利算 sum += floor(time / Mi) + 1，存在 sum >= N 時，表示理髮廳已經解決 sum 個人，並且已經理超過自己。找到最小的時間後，循序找一下適合的理髮師。presum += floor(time / Mi) + (time % Mi != 0)，找到前一個時刻 time - 1 結束瞬間完成的人數，隨後貪心找 time % Mi = 0 分配給 presum + 1 ~ N。

［C. Logging］O(2^N * N log N) -> O(N^2 log N)

松鼠在樹 i 上，請問要砍掉幾棵樹，才能讓自己的樹 i 位於森林邊緣。

最簡單的思路，使用的點集，做一次凸包，查找位於邊上的可能情況，需要凸包算法、線段上判定、bitmask，應付小測資專用。O(2^N * N log N)

接著考慮要砍點使得點 i 在凸包邊緣，那麼必然找到一條線通過點 i，其中一側具有最少的點數。因此對於每一個點 i 當作中心，對其他 N - 1 個點進行極角排序，掃描線算法找半平面 (180 度) 內最少的點數。O(N^2 log N)。

A code

GCJ20151A - Mushroom Monster

// Fucking English
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int testcase, n, cases = 0;
    long long A[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        for (int i = 0; i < n; i++)
            scanf("%lld", &A[i]);
        
        long long retA = 0, retB = 0, mx = 0;
        for (int i = 1; i < n; i++) {
            if (A[i-1] - A[i] > 0) {
                retA += A[i-1] - A[i];
                mx = max(mx, A[i-1] - A[i]);
            }
        }
        for (int i = 0; i < n - 1; i++) {
            if (A[i] > mx)
                retB += mx;
            else
                retB += A[i];
        }
        
        printf("Case #%d: %lld %lld\n", ++cases, retA, retB);
    }
    return 0;
}
/*
4
4
10 5 15 5
2
100 100
8
81 81 81 81 81 81 81 0
6
23 90 40 0 100 9
*/

B code

GCJ20151A - Haircut

#include <stdio.h>
int main() {
    int testcase, cases = 0;
    int N, B;
    long long M[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &B, &N);
        for (int i = 0; i < B; i++)
            scanf("%lld", &M[i]);
        
        long long l = 0, r = 100000LL * N, mid, time = 0;
        while (l <= r) {
            mid = (l + r)/2;
            long long cnt = 0;
            for (int i = 0; i < B; i++)
                cnt += mid / M[i] + 1;
            if (cnt >= N)
                r = mid - 1, time = mid;
            else
                l = mid + 1;
        }
        
        long long cnt = 0;
        int id = 0;
        
        for (int i = 0; i < B; i++)
            cnt += time / M[i] +(time % M[i] !=0);
        
        cnt = N - cnt;
//		printf("%lld %lld\n", cnt, time);
        for (int i = 0; i < B; i++) {
            if (time % M[i] == 0) {
                cnt--;
                if (cnt == 0)
                    id = i;
            }
        }
        printf("Case #%d: %d\n", ++cases, id + 1);
    }
    return 0;
}

C code

small

GCJ20151A - Logging

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <assert.h>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        Pt P[1024];
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &P[i].x, &P[i].y);
        
        int ret[16] = {};
        for (int i = 0; i < n; i++)
            ret[i] = n;
        for (int i = 0; i < (1<<n); i++) {
            int m = 0, cnt = 0;
            Pt a[32], ch[32];
            for (int j = 0; j < n; j++) {
                if ((i>>j)&1)
                    a[m++] = P[j];
            }
            
            int cn = monotone(m, a, ch);
            for (int p = 0; p < n; p++) {
                if ((i>>p)&1)
                for (int j = 0, k = cn-1; j < cn; k = j++) {
                    if (onSeg(ch[j], ch[k], P[p])) {
                        ret[p] = min(ret[p], n - m);
                    }
                }
            }
        }
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < n; i++)
            printf("%d\n", ret[i]);
    }
    return 0;
}

large

2015/05/15 修正極角排序誤差

Tricky Test Case

1
30
0 0
-971645 838743
748096 -988877
-652232 -993753
737167 -838743
-48 27
706721 -885828
606199 854425
659001 -993753
898961 885828
-659001 885828
748096 -973880
21 -13
-748096 606199
-732894 991850
13 -12
659001 -737167
-32 -32
737167 -748096
650983 -971645
650983 -732894
854425 -606199
-606199 885828
916399 -988877
652232 -838743
-606199 988877
-620105 -652232
-748096 -737167
24 -23
916399 854425

Output

盡可能地少用 atan2()，使用外積的方式進行極角排序。

GCJ20151A - Logging[fast]

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
    double x, y;
    int label;
    Pt(double a = 0, double b = 0, int c = 0):
    x(a), y(b), label(c) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt D[4096];
bool cmp(const Pt& p1, const Pt& p2)
{
    if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
    if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
    if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
    if (p1.y * p2.y < 0) return p1.y > p2.y;
    double c = cross2(p1, p2);
    return c > 0 || c == 0 && fabs(p1.x) < fabs(p2.x);
}
int main() {
    int N, testcase, cases = 0;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        printf("Case #%d:\n", ++cases);
        
        if (N == 1) {
            puts("0");
            continue;
        }
        
        for (int i = 0; i < N; i++) {
            vector< Pt > A;
            for (int j = 0; j < N; j++) {
                if (i == j)
                    continue;
                Pt p = D[j] - D[i];
                A.push_back(p);
            }
            sort(A.begin(), A.end(), cmp);
            int M = (int)A.size();
            int l = 0, r = 0, cnt = 1;
            int ret = 0;
            for (l = 0; l < M; l++) {
                if (l == r)
                    r = (r+1)%M, cnt++;
                while (l != r && cross2(A[l], A[r]) >= 0) {
                    r = (r+1)%M, cnt++;
                }
                ret = max(ret, cnt);
                cnt--;
            }
            printf("%d\n", N - ret);
        }
    }
    return 0;
}

Morris' Blog