Submission #2203852

---

Source Code Expand

from collections import deque
from sys import maxint
dist = [maxint]*100005
K = int(raw_input())
Q = deque()
dist[1] = 0
Q.append(1)
while Q :
    cur = Q.popleft()
    n1 = (cur + 1)%K
    n2 = (cur * 10)%K
    if dist[cur] + 1 < dist[n1] :
        dist[n1] = dist[cur] + 1
        Q.append(n1)
    if dist[cur] < dist[n2]:
        dist[n2] = dist[cur]
        Q.appendleft(n2)

print dist[0] + 1

Submission Info

Judge Result