Skip to content

Instantly share code, notes, and snippets.

@maksverver
Created November 25, 2013 01:13
Show Gist options
  • Save maksverver/7634768 to your computer and use it in GitHub Desktop.
Save maksverver/7634768 to your computer and use it in GitHub Desktop.
Facebook Hacker Cup 2014 Qualification Round solutions
#!/usr/bin/env python3
for case in range(int(input())):
N = int(input())
grid = [ input() for _ in range(N) ]
black = [ (r,c) for r in range(N) for c in range(N) if grid[r][c] == '#' ]
(r1,c1),(r2,c2) = black[0], black[-1]
size = r2 - r1 + 1
rect = [ (r1+i,c1+j) for i in range(size) for j in range(size) ]
print('Case #{}: {}'.format(case + 1, "YES" if rect == black else "NO"))
#!/usr/bin/env python3
for case in range(int(input())):
N,M,P = map(int, input().split())
players = []
for p in range(N):
name, skill, height = input().split()
players.append((int(skill), int(height), name))
players.sort(reverse=True)
playing = [ [ (0,i) for i in range(team, 2*P, 2) ] for team in range(2) ]
sitting = [ [ (0,i) for i in range(2*P + team, N, 2) ] for team in range(2) ]
for minute in range(M):
playing = [ [ (t+1,i) for (t,i) in team ] for team in playing ]
for field,bench in zip(playing, sitting):
if bench:
leaves = max(field)
enters = min(bench)
field.remove(leaves)
field.append(enters)
bench.remove(enters)
bench.append(leaves)
names = [ players[i][2] for team in playing for (_,i) in team ]
print('Case #{}:'.format(case + 1), *sorted(names))
#include <assert.h>
#include <stdio.h>
#include <string.h>
#define MAX_K 100
static int K;
static double Ps, Pr, Pi, Pu, Pw, Pd, Pl;
static double memo[2][MAX_K][3][MAX_K][MAX_K];
static double get_p(int a, int b, int c)
{
return (a ? a - 1 : Pi) + b*Pu - c*Pd;
}
static double get_value(int games, int wins, int a, int b, int c)
{
double p = get_p(a, b, c);
if (wins >= K) return 1.0;
if (games - wins >= K) return 0.0;
if (p <= 0.0) a = 1, b = c = 0;
if (p >= 1.0) a = 2, b = c = 0;
return memo[games%2][wins][a][b][c];
}
static void update_value(int games, int wins, int a, int b, int c)
{
double p_sun = get_p(a, b, c),
p_win = p_sun*Ps + (1 - p_sun)*Pr;
if (p_sun < 0.0 || p_sun > 1.0) return;
p_win = p_sun*Ps + (1 - p_sun)*Pr;
memo[games%2][wins][a][b][c] =
( p_win)*( ( Pw)*get_value(games + 1, wins + 1, a, b + 1, c) +
(1 - Pw)*get_value(games + 1, wins + 1, a, b, c) ) +
(1 - p_win)*( ( Pl)*get_value(games + 1, wins, a, b, c + 1 ) +
(1 - Pl)*get_value(games + 1, wins, a, b, c) );
}
int main()
{
int cases, caseNo, games, wins, a, b, c;
if (scanf("%d", &cases) == 1)
{
for (caseNo = 1; caseNo <= cases; ++caseNo)
{
if (scanf("%d %lf %lf %lf %lf %lf %lf %lf",
&K, &Ps, &Pr, &Pi, &Pu, &Pw, &Pd, &Pl) == 8)
{
assert(K > 0 && K <= MAX_K);
for (games = 2*K - 2; games >= 0; --games)
{
for ( wins = (games < K ? 0 : games + 1 - K);
wins < (games < K ? games + 1 : K); ++wins )
{
assert(wins >= 0 && wins < K);
assert(games - wins >= 0 && games - wins < K);
for (a = 0; a < 3; ++a)
{
for (b = 0; b <= wins; ++b)
{
for (c = 0; c <= games - wins; ++c)
{
update_value(games, wins, a, b, c);
}
}
}
}
}
printf("Case #%d: %.6lf\n", caseNo, get_value(0, 0, 0, 0, 0));
}
}
}
return 0;
}
#!/usr/bin/env python3
def calc(wins, losses, a, b, c, d):
if wins == K: return 1
if losses == K: return 0
p = a*Pi + b*Pu - c*Pd + d
if p <= 0: a,b,c,d,p = 0,0,0,0,0
if p >= 1: a,b,c,d,p = 0,0,0,1,1
try:
result = memo[wins,losses,a,b,c,d]
except KeyError:
p_win = p*Ps + (1 - p)*Pr
result = memo[wins,losses,a,b,c,d] = (
( p_win)*( ( Pw)*calc(wins + 1, losses, a, b + 1, c, d) +
(1 - Pw)*calc(wins + 1, losses, a, b, c, d) ) +
(1 - p_win)*( ( Pl)*calc(wins, losses + 1, a, b, c + 1, d) +
(1 - Pl)*calc(wins, losses + 1, a, b, c, d) ) )
return result
for case in range(int(input())):
memo = {}
params = input().split()
K = int(params[0])
Ps, Pr, Pi, Pu, Pw, Pd, Pl = map(float, params[1:])
print('Case #{}: {:.6f}'.format(case + 1, calc(0, 0, 1, 0, 0, 0)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment