밝은 미래

A는 2012년 당시보다 매우 쉽게 정석대로 풀었다.

수식만 세우고, 필요한 계산만 하면 쉽게 풀렸다.

1시간도 안 걸렸던 것 같다.

B는 문제를 제대로 이해 못해서 한참 헤맸다.

sample input은 쉽게 통과했는데, 로직에 틀린 부분이 있어서 small input 푸는 것에 시간을 많이 보냈다.

틀린 부분을 못 찾고, 3시간 이상 걸려서 답 안 보고 푸는 것은 포기했다.

B-small-practice.out 을 github에서 찾아내고, 틀린 test case를 diff로 찾았다.

손으로 푼 결과랑 비교할 수 있게 로그를 남겼다.

답 등을 graph로 남겨서 변화를 알기 쉽게 만드는 것도 도움이 되겠다.

C는 무리다..

L, R 무시하고, 수식으로 풀 수 있을 것 같았는데, 머리가 잘 안 돌아간다.

해답을 보니, 수식만으로 푼 것 같지도 않다. 나중에 시간이 날 때, 해답을 읽어보고 다시 풀어봐야 하겠다.

L, R이 주어진 만큼, 이용을 해서 풀어야 하겠다.

#https://code.google.com/codejam/contest/1645485/dashboard

import sys
import os

sample = "sample"
small = "A-small-practice"
large = "A-large-practice"
current = large

fin = open(current + ".in", "r")
fout = open(current + ".out", 'w')
f1out = open(current + "1.out", 'w')
f2out = open(current + "2.out", 'w')

T = int(fin.readline())

def solve(typed, N, ps):
    acc_ps = []
    acc_p = 1
    for p in ps:
        acc_p *= p
        acc_ps.append(acc_p)

    ss = []
    for b in range(typed):
        strokes = acc_ps[typed - b - 1] * (N - typed + 2 * b + 1) + (1 - acc_ps[typed - b - 1]) * (N - typed + 2 * b + 1 + N + 1)
        ss.append(strokes)

    ss.append(2 + N)

    return min(ss)

for i in range(T):
    typed, N = map(int, fin.readline().split())
    ps = map(float, fin.readline().split())

    solution = solve(typed, N, ps)
    answer = "Case #%d: %s" % (i+1, str(solution))
    fout.write(answer + '\n')

fin.close()
fout.close()
f1out.close()
f2out.close()

# https://code.google.com/codejam/contest/1645485/dashboard#s=p1

import sys
import os
import numpy as np

sample = "sample"
small = "B-small-practice"
large = "B-large-practice"
current = large

fin = open(current + ".in", "r")
fout = open(current + ".out", 'w')
f1out = open(current + "1.out", 'w')
f2out = open(current + "2.out", 'w')

T = int(fin.readline())


completed = []
star1s = []
sorted_star2_indices = []

def next_rush1(score):
    global star1s
    global sorted_star2_indices
    global completed

    if not sorted_star2_indices:
        return -1

    for level in reversed(sorted_star2_indices):
        if (not completed[level]) and star1s[level] <= score:
            return level

    return -1

def next_challenge():
    global star1s
    global sorted_star2_indices
    global completed

    if not sorted_star2_indices:
        return -1

    return sorted_star2_indices[0]

def rush1(level, stars, score):
    global star1s
    global sorted_star2_indices
    global completed

    if level >= 0:
        completed[level] = True
        next = next_challenge()
        # print 'rush1+1', level, score, completed, sorted_star2_indices, next
        n_moves, more_scores = rush(next, stars, score + 1)
        return 1 + n_moves, 1 + more_scores

    return 0, -1

def rush(level, stars, score):
    global star1s
    global sorted_star2_indices
    global completed

    if stars[level][1] <= score:
        sorted_star2_indices.remove(level)
        if completed[level]:
            # print 'rush2+1', level, score, completed, sorted_star2_indices, stars[level][1]
            return 1, 1
        else:
            # print 'rush2+2', level, score, completed, sorted_star2_indices, stars[level][1]
            return 1, 2

    return rush1(next_rush1(score), stars, score)

def greater(a, b):
    global star1s

    if a[1] > b[1]:
        return 1
    elif b[1] > a[1]:
        return -1

    return star1s[b[0]] - star1s[a[0]]

def solve(n_stars, stars):
    global star1s
    global sorted_star2_indices
    global completed

    n_moves = 0
    total_score = 0
    star1s = np.array(stars).T[0]
    star2s = np.array(stars).T[1]

    #sorted_star2_indices = [v[0] for v in sorted(enumerate(star2s), key=lambda x:x[1])]
    sorted_star2_indices = [v[0] for v in sorted(enumerate(star2s), cmp=greater)]
    sorted_star2_values = [v[1] for v in sorted(enumerate(star2s), cmp=greater)]

    # print ""
    # print star1s
    # print star2s
    # print sorted_star2_indices
    # print sorted_star2_values

    while sorted_star2_indices:
        level = next_challenge()
        move, more_scores = rush(level, stars, total_score)
        if move <= 0:
            return 0, -1
        n_moves += move
        total_score += more_scores
    return n_moves, total_score

for i in range(T):
    N = int(fin.readline())
    stars = []
    completed = []
    for j in range(N):
        stars.append(map(int, fin.readline().split()))
        completed.append(False)

    solution, score = solve(N, stars)
    solutionText = str(solution) if (solution > 0) else "Too Bad"
    answer = "Case #%d: %s" % (i+1, solutionText)
    fout.write(answer + '\n')

fin.close()
fout.close()
f1out.close()
f2out.close()