Hacker Cup 2017 solutions

fighting_the_zombie.cpp

#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <iomanip>
using namespace std;

int DD[6] = {4, 6, 8, 10, 12, 20};
double D[6][25][500];

void init() {
    for(int dk=0; dk<6; dk++) {
        int die = DD[dk];

        D[dk][0][0] = 1;
        for(int i=1; i<=20; i++) {
            for(int j=0; j<=400; j++) {
                for(int k=1; k<=die; k++) {
                    if (j+k <= 400)
                        D[dk][i][j+k] += D[dk][i-1][j] / die;
                }            
            }
        }
        for(int i=1; i<=20; i++)
            for(int j=399; j>=0; j--)
                D[dk][i][j] += D[dk][i][j+1];
    }
}

double parseDice(string s, int H) {
    stringstream sin(s);
    int x, y, z; char c;
    sin >> x >> c >> y >> c >> z;
    
    if (c == '-')
        z = -z;
    else if (c != '+')
        z = 0;
    
    if (y == 4) y = 0;
    else if (y == 6) y = 1;
    else if (y == 8) y = 2;
    else if (y == 10) y = 3;
    else if (y == 12) y = 4;
    else if (y == 20) y = 5;
    
    if (H-z<0) return 1;
    if (H-z>400) return 0;
    return D[y][x][H-z];  
}

int main() {
    init();
    int tests, test=0; cin >> tests;
    
    int H, S;
    while(cin >> H >> S) {
        double answer = 0;
        for(int i=0; i<S; i++) {
            string s; cin >> s;
            
            answer = max(answer, parseDice(s, H));
        }
        
        cout << "Case #" << ++test << ": ";
        cout << fixed << setprecision(6) << answer << endl;

    }
}

lazy_loading.cpp

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int T[1000];

int main() {
    int tests, test=0; cin >> tests;
    
    int N;
    while(cin >> N) {
        for(int i=0; i<N; i++)
            cin >> T[i];
        sort(T, T+N, greater<int>());
      
        int SN = N;
        int answer = 0;

        for(int i=0; i<N && SN; i++) {
            SN--;
            
            int top = T[i];
            int missing = ceil(50.0/top) - 1;
            if (SN >= missing) {
                SN -= missing;
                answer++;
            }
        }
        
        cout << "Case #" << ++test << ": ";
        cout << answer << endl;
    }
}

progress_pie.cpp

#include <iostream>
#include <cmath>
#define PI 3.14159265
using namespace std;

struct Point {
    int x, y;

    Point() {}
    Point(int x, int y) : x(x), y(y) {}

    double dist(Point A) {
        return sqrt(pow(A.x-x,2.0)+pow(A.y-y,2.0));
    }

    double angle(Point B, Point C) {
        double a = x - B.x;
        double b = y - B.y;
        double c = C.x - B.x;
        double d = C.y - B.y;
        double answer = atan2(a, b) - atan2(c, d);
        if (answer < 0) answer += 2*PI;
        return answer;
    }
};

int main() {
    int tests, test; cin >> tests;
    
    int P; Point A;
    while(cin >> P >> A.x >> A.y) {
        double AP = A.angle(Point(50, 50), Point(50, 100))/(2*PI)*100;
        cout << "Case #" << test++ << ": ";
        cout <<  (AP<=P and A.dist(Point(50, 50)) <= 50 ? "black" : "white") << endl;
    }
}