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)
RECENT COMMENT