2015 GCJ Round 1B Counting culture.

알고스팟/알고리즘 2015.05.04 16:26


1. Counting Culture.


small input은 DP로 풀 수 있다. 다음의 점화식을 이용한다.



스몰인풋은 n이 10^6승 미만 이므로, 10^6승까지 미리 pre-compute을 해놓고 각 테스트 케이스에 대하여 캐쉬값을 반환하면 된다.


large input은 10^14승이라. 32비트 정수배열을 잡는다해도 400테라바이트다. Greedy한 접근을 요함을 알 수 있다.


그리디 접근의 핵심은 다음과 같다. 주어진 n이 d자리수 일 때, 생각해보면 뒤집기 연산을 통해서 d-1자리수에서 d자리수로 커질 수 없기 때문에, 항상 1자리 -> 10자리 -> 100자리 -> 1000자리 -> 10000자리 -> ... -> d자리까지 최적으로 도달해야 한다. 이건 생각해보면 현재 d-1자리의 10...0라 가정할 때 99....9로 최대한 빨리 도달한 다음 +1을 해주면 된다.


근데 어떻게 해야 10...0에서 99....9로 최적으로 도달할까? 예를들어보자,


100000에서 999999으로 최적으로 도달하고 싶다. 그럼 일단 제일 먼저 100000에서 100009로 증가한 뒤 뒤집어서 900001로 간 뒤 999999까지 도달하는 방법이 있다. 왜? 100002일 때 뒤집지 않는가? 이건 손으로 계산해보면 2에서 9까지는 7번만 추가하면 되지만, 200001에서 900001이상으로 가려면 최소 7번 이상이 필요하기 때문이다. 

다음과 같이 걸린다. 

200001 -> 200009 -> 900002. 여기서 이미 8+1 = 9번이 걸림을 알 수 있다.


이걸 좀 더 확장해 생각해보면, 100009에서 뒤집는게 10000x (1<= x <=8)보다 최적이고,

100099에서 뒤집는게 1000xy (1<= x<= 9, 1<= y <=8)에서 뒤집는것 보다 낫다. 이걸 

100009, 100099, ..., 109999, 199999까지 다 해본 뒤 그 중에 가장 최적의 답을 구하는 주는 답을 택한다. 



예를 들면, 

1000에서 9999까지 제일 빨리 가려면, 1000 -> 1099 -> 9901 -> 9999로, 99+1+98 = 198번이 걸린다.


그럼 이제 d자리수인 n의 답을 구하려면, 

1 -> 10 -> 100 -> ... d 디짓까지 도달하는 횟수를 다 더한 뒤, 10....0 (d-1개) 에서 n까지 걸리는 도달 횟수를 더해서 반환하면 된다.





def minsteps(start,goal):
    if start == goal: return 0

    best = int(goal) - int(start)
    C = len(start)
    for cif in range(C):
        suffix = goal[::-1]
        intermediate = start[:C-cif] + suffix[C-cif:]
        
        if intermediate[::-1] > goal: continue
        candSum = int(intermediate) - int(start) + 1
        candSum += int(goal) - int(intermediate[::-1])
        if candSum < best:
            best = candSum
      
    return best

def solve(goal):
    start = '1'
    answer = 1
    #quickly get upto 'd' digits = len(goal).
    while len(start) < len(goal):
        #sum up the steps needed to get from '100..0' to '999...9'
        answer += minsteps(start, '9'*len(start)) + 1 
        #go to one more digit
        start += '0'
        
    answer += minsteps(start,goal)
    return answer

cache = [-1]*1000001
def solve_DP(n):
    
    for i in xrange(11, n+1):
        if i % 10 != 0 and rev(i) < i:
            cache[i] = 1 + min(cache[rev(i)], cache[i-1])
        else:
            cache[i] = 1 + cache[i-1]
#   print n, cache[n]
    return cache[n] 

f = open("A-large-attempt0.in", 'r')
f2 = open("outputCountingLarge.txt", 'w')   
t = int(f.readline())
for i in xrange(t):
    s = "Case #" + str(i+1) + ": "
    
    n = f.readline().rstrip()
    if n != '1':
        ans = solve(n)
        tryMe = str(int(n) - 1)
        ans = min(ans, 1+solve(tryMe))
    else:
        ans = solve(n)
    if i == t-1:
        f2.write(s+str(ans))
    else:
        f2.write(s+str(ans)+'\n')

f.close()
f2.close()


설정

트랙백

댓글