밝은 미래

관련글 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()

결국, 코드도 못 적었다.

내가 생각한 풀이 방법은

hikers의 시간/변위 그래프를 그려 보고,

그 선들을 최소로 지나면서, 왼쪽 아래에서 오른쪽 위로 향하는 곡선을 만들기

였는데, track이 원이고, 각 hiker가 몇 번 track을 돌 지 모르기 때문에 더 어려웠다.

꽤 잘 생각한 idea라고 생각했었는데,

해답을 보니, 이런 풀이 방법이 아니네... T_T

52 people successfully solved the large input for this problem

첫 문제는 쉬웠다.

보통 이건 잘 푸는 것 같다. ide 세팅시간 합쳐서 20분 정도 걸렸던 듯.

import sys
import os
#import numpy as np
import itertools

sample = "sample"
small = "A-small-attempt0"
large = "A-large"
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(N, ss):
    f = 0
    c = 0
    for i, s in enumerate(ss):
        if c < i:
            f += i - c
            c += i - c

        c += s

    return f, c

for i in range(T):
    N, S = fin.readline().split()
    ss = []
    for j in range(int(N)+1):
        ss.append(int(S[j]))
    solution = solve(int(N), ss)
    answer = "Case #%d: %s\n" % (i+1, solution[0])
    print answer
    fout.write(answer)



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

여기서 완전 말렸다.

5시간을 소비해도 못 풀었다 T_T

시간이 많이 걸렸을 때 빨리 포기하고 다른 문제를 풀었어야 했는데, 괜히 고집을 부렸다. 쉽게 풀릴 것만 같아서..

내가 틀렸다는 생각은 안하고..

왠지 testcase에 9가 n번 들어간 testcase가 많았었는데,

난 9를 4, 5로 나누려고 했었지만, 3, 3, 3으로 나누는 것이 좋을 때가 있었다! 다음 날 깨달았다.

3시간은 걸렸던 듯.

1.5시간은 quaternion class에 소비했던 것 같다.

처음에는 multiplication을 빠르게 하려고 고생했는데, 그렇게 노력할 필요가 없었다.

어차피 최소 1번은 죽 다 읽어야 하고,

각 조합에 대해서 반복 계산할 필요가 없었네..

그리고, 중요한 것은 4번 곱셈마다 값이 반복되니까 반복에 대해서 계산할 필요가 없을 때도 있다는 것.

sample = "sample"
small = "C-small-attempt3"
large = "C-large"
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())

q_order = {'i':-1, 'j':0, 'k':1}
q_next = {'i':'j', 'j':'k', 'k':'i'}

class Quaternion:

    def __init__(self, sign, v):
        self.sign = sign
        self.v = v

    def qorder(self):
        return q_order[self.v]
    def qnext(self):
        return Quaternion(self.sign, q_next[self.v])

    def __mul__(self, other):
        sign = not (self.sign ^ other.sign)

        if self.v == '1':
            return Quaternion(sign, other.v)
        if other.v == '1':
            return Quaternion(sign, self.v)
        if self.v == '0' or other.v == '0':
            return Quaternion(sign, '0')

        if self.v == other.v:
            return Quaternion( not (sign ^ False), '1')

        if self.qnext().v == other.v:
            return Quaternion(sign, other.qnext().v)
        else:
            return Quaternion( not (sign ^ False), self.qnext().v)

        print 'ERROR'

    def __neg__(self):
        return Quaternion(not (self.sign ^ False), self.v)

    def __eq__(self, other):
        # if other == 1:
        #     return self.sign == True and self.v == '1'
        # elif other == -1:
        #     return self.sign == False and self.v == '1'

        return self.sign == other.sign and self.v == other.v

    def __repr__(self):
        sign = '+' if self.sign else '-'
        return sign + self.v

def q(s):
    return Quaternion(True, s)

def mult(qs):
    r = q('1')
    for vq in qs:
        r = r * vq
    return r

def mult_table(table, vs, a, b, indices):
    key = str(a) + ',' + str(b)
    if table.has_key(key):
        return table[key]
    else:
        cs = [x for x in indices if a < x < b]
        if not cs:
            value = mult(vs[a:b])
        else:
            c = cs[len(cs)/2]
            value = mult_table(table, vs, a, c, indices) * mult_table(table, vs, c, b, indices)
            #print key, value, a, c, b
        table[key] = value
        return value

#print q('i') * q('j'), q('j') * q('k'), q('i') * q('j') * q('k')
def solve(L, X, ijk):
    fqs = []
    for i in ijk:
        if i == 'i' or i == 'j' or i == 'k':
            fqs.append(q(i))
    qs = []
    X = X % 16
    extend = min(X, 4)
    for i in range(extend):
        qs.extend(fqs)


    print qs
    lq = q('1')
    left_plus = []
    left_minus = []
    for i_l, l in enumerate(qs):
        # print lq, l
        lq = nx = lq * l
        if nx == q('i'):
           left_plus = [i_l+1, nx, l]
        if nx == -q('i'):
            left_minus = [i_l+1, nx, l]
        if left_plus and left_minus:
            break

    right_plus = []
    right_minus = []
    rq = q('1')
    for i_r, r in enumerate(reversed(qs)):
        rq = nx = r * rq
        if nx == q('k'):
            right_plus = [i_r+1, nx, r]
        elif nx == -q('k'):
            right_minus = [i_r+1, nx, r]
        if right_plus and right_minus:
            break

    if (not left_plus) and not left_minus:
        return "NO"
    if not right_plus and not right_minus:
        return "NO"

    dqs = []
    for idqs in range(X):#range(min(X, 8)):
        dqs.extend(fqs)

    lefts = []
    rights = []

    mc = {}
    mfqs = mult(fqs)
    indices = []
    if left_plus:
        indices.append(left_plus[0])
        lefts.append(left_plus)
    if left_minus:
        indices.append(left_minus[0])
        lefts.append(left_minus)
    if right_plus:
        indices.append(len(dqs) - right_plus[0])
        rights.append(right_plus)
    if right_minus:
        indices.append(len(dqs) - right_minus[0])
        rights.append(right_minus)
    for ie in range(8):
        index = ie * len(fqs)
        indices.append(index)
        mc[str(index) + ',' + str(index + len(fqs))] = mfqs
    sorted_indices = sorted(set(indices))

    # prev = -1
    # mc = mult_table(qs, sorted_indices)
    # for ii in sorted_indices:
    #     for ij in sorted_indices[]:
    #         if
    #     if prev > 0
    #         mc[[prev, index]] = mult(qs[prev:index+1])
    #     prev = index


    print mfqs, mc, sorted_indices
    for j_l in lefts:
        for j_r in rights:
            if j_l[0] + j_r[0] < len(dqs) + 2:
                #isj = mult_table(mc, dqs, j_l[0], len(dqs)-j_r[0], sorted_indices)
                isj = mult(dqs[j_l[0] : len(dqs) - j_r[0] ])
                #print j_l[1], isj, j_r[1], j_l[1] * isj * j_r[1]
                if j_l[1] * isj * j_r[1] == -q('1'):
                    return "YES"
                # else:
                #     j_left = mult(dqs[j_l[0] : -1])
                #     j_right = mult(dqs[0 : len(dqs) - j_r[0]])
                #     j_middle = q('1')
                #     for k_d in range(min(X - 8, 4)):
                #         j_middle = j_middle * mfqs
                #         if j_l[1] * j_left * j_middle * j_right * j_r[1] == -q('1'):
                #             return "YES"

    return "NO"

for i in range(T):
    L, X = map(int, fin.readline().split())
    ijk = fin.readline()
    solution = solve(L, X, ijk)
    # if solution > candidate:
    #     print 'ERROR', i + 1, solution, candidate
    # if solution != solution1:
    #     print 'ERROR', i + 1, solution, solution1, candidate
    answer = "Case #%d: %s\n" % (i + 1, solution)
    print answer
    fout.write(answer)

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

문제 속에 hint가 있었다. 7-ominous 이상에서는 richard가 승리한다는 것.

brute force로도 풀 수 있는 문제였다.

small input에 대해서 if 몇 개로 풀 수 있었는데, 이런 문제가 나올 줄은 예상 못해서 좀 어색했네.

large input은 틀리고 말았다 T_T 지그재그 case를 틀렸나 보다.

import math

sample = "sample"
small = "D-small-attempt5"
large = "D-large"
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())

Gabriel = "GABRIEL"
Richard = "RICHARD"

def solve(X, R, C):
    if (R * C) % X != 0:
        print "%"
        return Richard
    if R < X and C < X:
        print "<"
        return Richard
    if X > 6:
        print "6"
        return Richard
    min_l = 1 + (X - 1) / 2
    if X > 2 and (R < min_l or C < min_l):
        print "sqrt"
        return Richard
    snake = 2 + (X - 2) / 3
    if X > 3 and (R <= snake or C <= snake):
        print "snake"
        if X == 4:
            return Richard
        elif X == 5 and (R < 5 and C < 5):
            return Richard
        elif X == 6 and (R < 7 and C < 7):
            return Richard

    return Gabriel

for i in range(T):
    X, R, C = map(int, fin.readline().split())
    print i+1, X, R, C

    solution = solve(X, R, C)
    # if solution > candidate:
    #     print 'ERROR', i + 1, solution, candidate
    # if solution != solution1:
    #     print 'ERROR', i + 1, solution, solution1, candidate
    answer = "Case #%d: %s\n" % (i + 1, solution)
    print answer
    fout.write(answer)

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