Facebook Hacker Cup Round 1 solutions

A.py

from sys import stdin

for case in range(1, int(stdin.readline()) + 1):
    L, N = stdin.readline().split()
    N = int(N)
    b = len(L)
    n = 1
    while b**n < N:
        N -= b**n
        n += 1
    answer = ''.join(L[(N - 1)//(b**i)%b] for i in reversed(range(n)))
    print('Case #{}: {}'.format(case, answer))

B.py

from sys import stdin

for case in range(1, int(stdin.readline()) + 1):
    N, K, C = map(int, stdin.readline().split())
    answer = C + max(0, N - K//((C + N - 1)//N))
    print('Case #{}: {}'.format(case, answer))

C.cpp

#include <iostream>
#include <vector>
using namespace std;

#define FOR(i, a, b)    for(int i = int(a); i < int(b); ++i)
#define REP(i, n)       FOR(i, 0, n)
#define FORD(i, a, b)   for(int i = int(b) - 1; i >= int(a); --i)
#define REPD(i, n)      FORD(i, 0, n)

int main()
{
    int cases = 0;
    cin >> cases;

    for (int caseNo = 1; caseNo <= cases; ++caseNo)
    {
        // Read input.
        int H = 0, W = 0;
        cin >> H >> W;
        vector<string> grid(H);
        REP(r, H) cin >> grid[r];

        vector<vector<int> > reach(H, vector<int>(W));
        vector<vector<int> > length(H, vector<int>(W));

        // For each cell, determine if it is reachable from the entrance by
        // moving right and down only.
        REP(r, H) REP(c, W) if (grid[r][c] == '.') {
            reach[r][c] = (r == 0 && c == 0) || (r > 0 && reach[r - 1][c])
                                             || (c > 0 && reach[r][c - 1]);
        }

        // For each cell, find the maximum queue length that can be achieved by
        // moving only right and down from there:
        REPD(r, H) REPD(c, W) if (grid[r][c] == '.') {
            length[r][c] = max( (r + 1 < H) ? length[r + 1][c] : 0,
                                (c + 1 < W) ? length[r][c + 1] : 0 ) + 1;
        }

        int answer = length[0][0];

        // Try to improve using an extra segment moving left or down form (r,c):
        REP(r, H) REP(c, W) {

            if (r > 0 && reach[r - 1][c])
            {
                // Entered from top; try walking n steps left:
                for (int n = 0; n <= c && grid[r][c - n] == '.'; ++n)
                    answer = max(answer, r + c + n + 1 + (r + 1 < H ? length[r + 1][c - n] : 0));
            }
            if (c > 0 && reach[r][c - 1])
            {
                // Entered from left; try walking n steps up:
                for (int n = 0; n <= r && grid[r - n][c] == '.'; ++n)
                    answer = max(answer, r + c + n + 1 + (c + 1 < W ? length[r - n][c + 1] : 0));
            }
        }

        cout << "Case #" << caseNo << ": " << answer << endl;
    }
}

D.cpp

#include <algorithm>
#include <cstring>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

#define FOR(i, a, b)    for(int i = int(a); i < int(b); ++i)
#define REP(i, n)       FOR(i, 0, n)
#define IT(c)           __typeof((c).begin())
#define FORIT(i, c)     for(IT(c) i = (c).begin(); i != (c).end(); ++i)

// Since A[i]<=50 and N<=20 we only need about 35 primes, because the 15th prime
// is already greater than 50.
static int primes[40] = {
      2,     3,     5,     7,    11,    13,    17,    19,    23,    29,
     31,    37,    41,    43,    47,    53,    59,    61,    67,    71,
     73,    79,    83,    89,    97,   101,   103,   107,   109,   113,
    127,   131,   137,   139,   149,   151,   157,   163,   167,   173 };

// X is the cut-off for "small primes"; i.e. primes less than A[i]<=50.
const int X = 15;

// List of numbers below 200 which can be build out of small primes (less than
// primes[X]) and corresponding bitmasks:
static bool is_small[200];
static unsigned factors[200];

// Cache for results of calc (must be initialized to -1 for each testcase!)
static int memo[20][1<<X][20];

// Calculates total amount of money spent for ages in A starting from index pos,
// with indices of low primes used marked in bitmask used_low, and the next
// unused high prime having index next_high.
static int calc(const vector<int> &A, int pos, unsigned used_low, int next_high)
{
    // Check if we reached the end of the list:
    if (pos == (int)A.size()) return 0;

    // Check for cached value:
    int &m = memo[pos][used_low][next_high - X];
    if (m >= 0) return m;

    // We can always take the next `high` prime and move on to next position:
    int res = primes[next_high] + calc(A, pos + 1, used_low, next_high + 1);

    // Otherwise, we give use a value i which is smaller than the next prime:
    for (int i = A[pos]; i < primes[next_high]; ++i)
    {
        if (is_small[i] && ((used_low & factors[i]) == 0))
            res = min(res, i + calc(A, pos + 1, used_low | factors[i], next_high));
    }
    return m = res;
}

int main()
{
    // Prepare list of numbers made out of small primes:
    is_small[1] = true;
    factors[1] = 0;
    REP(n, X) {
        for (int i = 0; i < 200; ++i)
        {
            if (is_small[i])
            {
                int j = i*primes[n];
                if (j < 200)
                {
                    is_small[j] = true;
                    factors[j] = factors[i] | 1u<<n;
                }
            }
        }
    }

    int cases = 0;
    cin >> cases;
    for (int caseNo = 1; caseNo <= cases; ++caseNo)
    {
        // Read input
        int N = 0, K = 0;
        cin >> N >> K;
        vector<int> A(N);
        REP(i, N) cin >> A[i];

        // Normalize ages to multiples-of-K:
        vector<int> B(N);
        REP(i, N) B[i] = (A[i] + K - 1)/K;

        int answer;
        sort(B.begin(), B.end());
        if (B[N - 1] <= 1)
        {
            // We can give the first person 0 as long as everyone else gets 1.
            FOR(n, 1, N) if (B[n] == 0) ++B[n];
            answer = accumulate(&B[0], &B[N], 0);
        }
        else
        {
            // Otherwise, we must bump everyone to 1:
            REP(n, N) if (B[n] == 0) ++B[n];

            // Now calculate the maximum amount to spend (in K multiples):
            memset(memo, -1, sizeof(memo));
            answer = calc(B, 0, 0u, X);
        }
        answer = K*answer - accumulate(&A[0], &A[N], 0);
        cout << "Case #" << caseNo << ": " << answer << endl;
    }
}