홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다.
홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 LED로 된 다섯 자리 십진수 N이, 그 옆에 T, G라는 알파벳과 함께 또 다른 정수 두 개가 쓰여 있었고, 벽 앞에는 버튼 A, B 두 개가 있었다.
버튼을 이리저리 눌러보던 똑똑한 홍익이는 어떻게 해야 방을 탈출할 수 있을지 금방 눈치챘다.
버튼과 수에 대해 홍익이가 알아낸 것은 다음과 같다.
또한 홍익이는 최대 T회 버튼을 누를 수 있고, 그 횟수 안에 LED로 표현된 N을 G와 같게 만들어야 탈출할 수 있다는 사실을 알아냈다.
똑똑한 홍익이는 이와중에 자존심이 발동해 버튼 누르는 횟수를 최소로 하여 방을 탈출하기로 했다.
홍익이의 방 탈출을 기원하며, 탈출에 필요한 최소의 버튼 횟수를 구하자.
# 16397
import sys
input = lambda: sys.stdin.readline().strip()
from collections import deque
# 1. A : n+1
# 2. B : n*2 이후 가장 높은 자릿수의 숫자가 1 줄어든다
# 3. 버튼을 누른 N의 결과값이 99,999 보다 큰 경우 실패
N, T, G = map(int, input().split())
time = [-1] * 100000
def bfs():
global N, T, G, time
queue = deque()
queue.append(N)
time[N] = 0
while queue:
n = queue.popleft()
if time[n] + 1 > T:
continue
if n + 1 <= 99999:
if time[n+1] == -1 or time[n] + 1 < time[n+1]:
time[n+1] = time[n] + 1
queue.append(n+1)
if n * 2 <= 99999:
num = n * 2
if num >= 10000:
num -= 10000
elif num >= 1000:
num -= 1000
elif num >= 100:
num -= 100
elif num >= 10:
num -= 10
elif num > 0:
num -= 1
if time[num] == -1 or time[n] + 1 < time[num]:
time[num] = time[n] + 1
queue.append(num)
return time[G]
exit_time = bfs()
if 0 <= exit_time <= T:
print(exit_time)
else:
print("ANG")