Facebook Hacker Cup 2017 Qualification Round

Facebook Hacker Cup 2017 Qualification Round

(페이스북 해커컵 2017 예선 라운드)

결과먼저 얘기하자면, B번이 나갔다.

아직 왜 나갔는지는 모르겠다. 나중에 다시 코딩해봐야지...

A. Progress Pie (25 points)

https://www.facebook.com/hackercup/problem/326053454264498/

입력을 double로 받았는데, x,y가 정수라고 얘기하지 않아서 나는 소수값도 들어오는 줄 알았다.

revision()이라 해서 오차부분 미리 자르고 시작하는 함수도 만들었는데, 쓰잘데기 없는 짓이었다. ㅋㅋ

아래 코드에서 주의해야 할 예외는 0%만큼 진행했을 때에는 반드시 white를 출력해야 했던것 뿐이었다.

경계는 문제에서 딱히 언급이 있었는지 모르겠다. 난 코드 내고나서 이 부분 실수했다고 생각했는데,

나중에 인풋 데이터를 들여다보니 그런 데이터는 없었다. ㅋㅋ

#include <cstdio>
#include <cmath>
using namespace std;
const double pi = 2.0*acos(0.0);
const double pi2 = 2.0*pi;
double revision(double x) { return double(int(x*1e6))/1e6; }
double chg(double x, double t) { return (x<0.0)? pi2-t:t; }
int main() {
    //freopen("./a_input.txt", "r", stdin);
    //freopen("./a_output.txt", "w", stdout);
    int tc; scanf("%d", &tc);
    for(int z=1; z<=tc; z++) {
        double x,y,r=50.0,p;
        scanf("%lf%lf%lf",&p,&x,&y);
        bool white=false;
        x=revision(x-r); y=revision(y-r);
        double d=x*x+y*y;
        if(d>r*r||p==0.0) white=true;
        else {
            if(d==0.0) white=false;
            else {
                double t = acos(y/sqrt(d));
                white = !(chg(x,t)/pi2*100.0 <= p);
            }
        }
        printf("Case #%d: %s\n", z, (white)?"white":"black");
    }
    return 0;
}
 

B. Lazy Loading (30 points)

https://www.facebook.com/hackercup/problem/169401886867367/

일단 틀려서... ㅠ

너무 거지같이 짰다.

그냥 위에서 하나 밑에서 하나 빼는 식으로 하면 됐는데,

쓸데 없이 뭉탱이로 빼다가 WA가 난듯 하다.

바로 아래에 펼치면 보이는 코드는 WA받은 코드. 나중에 다시 짜봐야지...

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v, need;
int main() {
    //freopen("./b_input.txt", "r", stdin);
    //freopen("./b_output.txt", "w", stdout);
    int tc; scanf("%d",&tc);
    for(int i=1; i<=50; i++) {
        if(need.begin() == need.end()) need.emplace_back(50);
        else if(need.back() != int((50+i-1)/i)) need.emplace_back((50+i-1)/i);
    }
    for(int z=1; z<=tc; z++) {
        int n; scanf("%d", &n);
        v.clear(); v.resize(n);
        for(int i=0; i<n; i++) scanf("%d", &v[i]);
        sort(v.begin(), v.end());
 
        int ans=0;
        for(int i=0; i<need.size()&&!v.empty(); i++) {
            auto it = lower_bound(v.begin(), v.end(), need[i]);
            int exist = v.end()-it;
            int pp=(need[need.size()-1-i]-1);
            if(it!=v.end()) v.erase(it, v.end());
            if(pp==0) ans+=exist;
            else {
                int rm = min(int(v.size()/pp),exist);
                v.erase(v.begin(), v.begin()+rm*pp);
                ans += rm + (exist-rm)/(pp+1);
            }
        }
        printf("Case #%d: %d\n",z,ans);
    }
    return 0;
}

C. Fighting the Zombie (45 points)

https://www.facebook.com/hackercup/problem/326053454264498/

문제는 쉬운데, 좀 고생했다.

왜냐면, 내가 푼 방식이 long long범위를 초과하도록 짰기 때문이다.

일단 방식은 맞다고 생각해서 c++로 짜놓고 페북 테케 몇개 넣어서 테스트 해봤더니 다 맞았다.

그래서 이 코드를 자바나 파이썬으로 옮기거나 c++에선 big integer를 구현해서 다시 코딩해야 했는데 ㅠㅠ

제일 못하는 파이썬을 선택했다.

우앜... 코딩하는데 얼마 안걸렸는데 ㅋㅋ python으로 옮기는데만 4시간이 넘게 걸렸다. ㅡ,.ㅠ

정말 더럽게 짰다.

입력 받는것도 몰라서 한참 찾았다. ㅠㅠㅠㅠ

일단 c++코드가 깔끔하니 c++코드부터 올려보겠다.

다시 말하지만 long long범위가 초과되므로 일부 데이터는 WA를 받을 것이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll d[21][21][20001], po[21][21];
ll f(int x, int y, int p) {
    if(p<0) return f(x,y,0);
    ll &ret = d[x][y][p];
    if(ret>=0LL) return ret;
    else ret=0LL;
    if(x==0) return ret=(p==0);
 
    for(int i=1; i<=y; i++) ret+=f(x-1,y,p-i);
    return ret;
}
ll spow(int y, int x) {
    ll &ret = po[y][x];
    if(ret) return ret;
    if(x==0) return ret=1LL;
 
    ret = spow(y,x>>1);
    if(x&1) return ret=ret*ret*y;
    else return ret*=ret;
}
double div(double ans, int x, double y) {
    for(int i=0; i<x; i++) ans/=y;
    return ans;
}
int main() {
    memset(d,-1,sizeof(d));
    memset(po,0,sizeof(po));
    int tc; scanf("%d", &tc);
    for(int t=1; t<=tc; t++) {
        int h,s,x,y,z;
        scanf("%d%d",&h,&s);
        double ans=0.0;
        for(int i=0; i<s; i++) {
            char ch;
            scanf("%dd%d%c",&x,&y,&ch);
            if(ch==' '||ch=='\n'||ch=='\r') z=0;
            else {
                scanf("%d",&z);
                if(ch=='-') z*=-1;
            }
            ans = max(ans, double(f(x,y,h-z))/spow(y,x));
        }
        printf("Case #%d: %.6lf\n",t,ans);
    }
}

spow(y,x)는 y^x을 구해주는 코드다. 혹시나 해서 이것마저 dp로 처리했다.

f(x,y,p)에서 p는 좀비 체력(h)-주사위에서 마지막에 더해줘야 하는 값(z)이다.

그러니까 h=10인데 z=6이면 나중에 주사위 다 굴리고 나서 주사위에 6더해줄거를 미리 좀비체력에서 뺌으로써 좀비체력이 원래부터 4인것처럼 얘기하는 것이다.

아무튼 d[x][y][p]는 새로운 좀비데이터가 들어온다고 해서 절대 변하지 않는다.

주사위 눈깔이 1~y까지 있고 주사위를 x번까지 굴릴 수 있을 때 좀비체력이 p인 애를 죽이는 방법의 수는 언제나 같기 때문이다.

이걸 파이썬 코드로 다음과 같이 옮겼다.

혹시 파이썬 고수분들 중에 깔끔하게 옮길 수 있으신분은 옮겨주시면 매우 감사하겠습니다.

제가 치킨 사드릴게요. (대신 나랑 먹어야함. ^^)

(아래 코드가 확실하게 AC를 받은 코드)

from ctypes import *
import re
import sys
 
def freopen(f, option, stream):
    import os
    oldf = open(f,option)
    oldfd = oldf.fileno()
    newfd = stream.fileno()
    os.close(newfd)
    os.dup2(oldfd, newfd)
 
freopen("./input.txt", "r", sys.stdin)
freopen("./output.txt", "w", sys.stdout)
d = [[[-1]*20001 for i in range(21)] for j in range(21)]
po = [[0]*21 for i in range(21)]
 
def f(x,y,p):
    if p<0: return f(x,y,0)
    if d[x][y][p]>=0: return d[x][y][p]
    else: d[x][y][p]=0
 
    if x==0:
        if p==0: d[x][y][p]=1
        else: d[x][y][p]=0
        return d[x][y][p]
 
    for i in range(1,y+1):
        d[x][y][p] += f(x-1,y,p-i)
 
    return d[x][y][p]
 
def spow(y,x):
    if po[y][x]>0: return po[y][x]
    if x==0:
        po[y][x]=1
        return po[y][x]
 
    po[y][x] = spow(y,x>>1)
    po[y][x] *= po[y][x]
    if x%2==0: return po[y][x]
    else:
        po[y][x] *= y
        return po[y][x]
 
tc = int(input())
for t in range(tc):
    h,s = input().split()
    h=int(h)
    s=int(s)
    ans = 0.0
 
    x,y,z=(0,0,0)
    pat1 = re.compile("(\d+)[d](\d+)([+|-]\d+)")
    pat2 = re.compile("(\d+)[d](\d+)")
    for word in input().split(" "):
        z=0
        if pat1.match(word):
            x,y,z=pat1.match(word).groups()
        else:
            x,y=pat2.match(word).groups()
        x=int(x)
        y=int(y)
        z=int(z)
        ans = max(ans, float(f(x,y,h-z))/float(spow(y,x)))
 
    print("Case #%d: %.6lf"%(t+1, ans))