2015 google codejam Round 1B 실패 기록

공부/Computers

2015 google codejam Round 1B 실패 기록

언제나19 2015. 5. 12. 02:07

A. Counter Culture

C번을 먼저 풀어서 점수를 높이려고 하다가 시간이 부족했다.

관련글 http://luxs1t.tistory.com/238 처럼 깔끔하게 풀고 싶었는데,

괜히 쓸데 없는 생각까지 하다가 저질이 돼서 답이 안 나왔다.

언제 뒤짚을까를 얼렁뚱땅 이상한 수식으로 때려맞추려고 했다.

substract = n % (pow(10, i+1)) - 1 r = reverse(n - substract)
if r + substract + 1 < next_n + next_s and r >= 0:

그냥 정직하게 언제 뒤짚는게 좋을지를 생각해보면 좋았을텐데.

자릿수를 맞춘 다음에 최종 숫자에 도달하는 것도 착실하게 다 체크하는 것이 좋았다.

import math

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

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 reverse(n):
    result = 0
    while n:
        digit = n % 10
        n = n / 10
        result = result * 10 + digit
    return result

def solve(N):
    n = N
    times = 0

    while n:
        next_n = n-1
        next_s = 1
        for i in range(len(str(n))-1):
            substract = n % (pow(10, i+1)) - 1
            r = reverse(n - substract)
            if r + substract + 1 < next_n + next_s and r >= 0:
                #print "   ", n, next_n, r
                next_n = r
                next_s = substract + 1
        if next_s > 1:
            print n, next_n, next_s
        times += next_s
        n = next_n
        # if n > r #and (n % 10 != 0) and (n % 10 == 1):
        #     print n, r
        #     n = r
        # else:
        #     n -= 1

    return str(times)

# def bottomup(N):
#     p = 0
#     while p != n:
#         next_i = p+1
#         next_a = 1
#         for i in range(len(str(N))-1):
#             adding =

def less(N, n, times):
    if n <= 0:
        return times
    if times > N:
        return times
    r = reverse(n)
    times1 = less(N, n-1, times+1)
    times2 = less(N, r-1, times+2)
    return min(times1, times2)

def brute(N):

    return str(less(N, N-1, 1))

for i in range(T):
    N = int(fin.readline())
    print N
    solution = solve(N)
    # b_solution = brute(N)
    # if solution != b_solution:
    #     print solution, b_solution
    answer = "Case #%d: %s\n" % (i + 1, solution)
    print answer
    fout.write(answer)

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

B는 문제도 못 읽었다.

C. Hiking Deer

풀 방법을 여러 모로 생각은 해 봤는데