Problem:
 Score : 700 points    Problem Statement Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K .      Constraints  2 \leq K \leq 10^5  K is an integer.         Input Input is given from Standard Input in the following format:  K       Output Print the smallest possible sum of the digits in the decimal notation of a positive multiple of K .        Sample Input 1 6      Sample Output 1 3  12=6×2 yields the smallest sum.       Sample Input 2 41      Sample Output 2 5  11111=41×271 yields the smallest sum.       Sample Input 3 79992      Sample Output 3 36

Solution (Python):
n = int(input())

while n % 2 == 0:
    n //= 2
while n % 5 == 0:
    n //= 5
if n == 1:
    print(1)
else:
    X = [n for i in range(n)]
    
    j = 1
    s = 1
    post = []
    m = 0
    while True:
        s *= 10
        s %= n
        post.append(s)
        X[s] = min(j, X[s])
        m += 1
        if s == 1:
            break
    ans = 0
    while True:
        if ans > 0:
            break
        pre = post
        post = []
        j += 1
        for p in pre:
            pp = (p + 1) % n
            if pp == 0:
                X[0] = j
                ans = j
                break
            if X[pp] == n:
                for i in range(m):
                    post.append(pp)
                    X[pp] = j
                    pp *= 10
                    pp %= n
    print(ans)

Solution (Python):
from collections import deque
K=int(input())
Graph1=[0 for i in range(K)]
Graph0=[0 for i in range(K)]
Graph1[K-1]=0
for i in range(K-2):
  Graph1[i+1]=i+2
for i in range(1,K):
  Graph0[i]=(10*i)%K
l=1
q=deque([(1,1)])
Visited=[0]*K

while q:
  x,d=q.popleft()
  if x==0:
    ans=d
    break
  if Visited[x]==1:
    continue
  Visited[x]=1
  if Visited[Graph0[x]]==0:
    q.appendleft((Graph0[x],d))
  if Visited[Graph1[x]]==0:
    q.append((Graph1[x],d+1))
print(ans)

Solution (Python):
from collections import deque
K = int( input())
V = [0]*K
q = deque([(1,1)])
while q:
    x, r = q.popleft()
    if x == 0:
        ans = r
        break
    if V[x] == 1:
        continue
    V[x] = 1
    if V[10*x%K] == 0:
        q.appendleft((10*x%K, r))
    if V[(x+1)%K] == 0:
        q.append(((x+1)%K, r+1))
print(ans)

Solution (Python):
from heapq import heappush,heappop
class Dijk:
    def __init__(self,n):
        self.table=[[] for i in range(n)]
        self.n=n
    
    def add(self,x,y,f):
        self.table[x].append((y,f))
        
    def di(self,s):
        inf=10**20
        self.val=[inf]*self.n
        self.val[s]=0
        h=[]
        heappush(h,(0,s))
        while h:
            q,i=heappop(h)
            if self.val[i]<q:
                continue
            for x,c in self.table[i]:
                if self.val[x]>self.val[i]+c:
                    self.val[x]=self.val[i]+c
                    heappush(h,(self.val[x],x))
                    
    def dist(self,s,t):
        return self.val[t]

K=int(input())
d=Dijk(K)
for i in range(1,K):
    d.add(i,(i+1)%K,1)
    d.add(i,(10*i)%K,0)
d.di(1)
print(d.dist(1,0)+1)

Solution (Python):
from collections import deque
K = int(input())
G = [[] for i in range(K)]
for i in range(K):
    G[i].append(((i+1) % K, 1))
    G[i].append((10*i % K, 0))

visited = [0] * K
queue = deque([(1, 1)])


while queue:
    now, cost = queue.popleft()
    if now == 0:
        print(cost)
        break

    visited[now] = 1
    for n, c in G[now]:
        if visited[n]:
            continue

        if c == 0:
            queue.appendleft((n, cost))
        else:
            queue.append((n, cost+1))

Solution (Python):
from collections import deque
K=int(input())
table=[[] for i in range(K)]
for i in range(K):
    table[i].append([1,(i+1)%K])
    t = (10*i)%K
    if t!=i:
        table[i].append([0,t])
dij=deque()
visit=[False]*K
val=[10**9]*K
val[1]=0
dij.append([0,1])
while dij:
    d,x=dij.popleft()
    if val[x]<d:
        continue
    for q,y in table[x]:
        if val[y]>val[x]+q:
            val[y]=val[x]+q
            if q==1:
                dij.append([val[y],y])
            else:
                dij.appendleft([val[y],y])
print(val[0]+1)

Solution (Python):
from collections import deque
K=int(input())
table=[[] for i in range(K)]
for i in range(K):
    table[i].append([1,(i+1)%K])
    t = (10*i)%K
    if t!=i:
        table[i].append([0,t])
dij=deque()
visit=[False]*K
val=[10**9]*K
val[1]=0
dij.append([0,1])
while dij:
    d,x=dij.popleft()
    if val[x]<d:
        continue
    for q,y in table[x]:
        if val[y]>val[x]+q:
            val[y]=val[x]+q
            if q==1:
                dij.append([val[y],y])
            else:
                dij.appendleft([val[y],y])
print(val[0]+1)

Solution (Python):
from heapq import heappush,heappop
K=int(input())
table=[[] for i in range(K)]
for i in range(K):
    table[i].append([1,(i+1)%K])
    t = (10*i)%K
    if t!=i:
        table[i].append([0,t])
dij=[]
visit=[False]*K
val=[10**9]*K
val[1]=0
heappush(dij,[0,1])
while dij:
    d,x=heappop(dij)
    if val[x]<d:
        continue
    for q,y in table[x]:
        if val[y]>val[x]+q:
            val[y]=val[x]+q
            heappush(dij,[val[y],y])
print(val[0]+1)

Solution (Python):
from heapq import heappush,heappop
K=int(input())
table=[[] for i in range(K)]
for i in range(K):
    table[i].append([1,(i+1)%K])
    t = (10*i)%K
    if t!=i:
        table[i].append([0,t])
dij=[]
visit=[False]*K
val=[10**9]*K
val[1]=0
heappush(dij,[0,1])
while dij:
    d,x=heappop(dij)
    if val[x]<d:
        continue
    for q,y in table[x]:
        if val[y]>val[x]+q:
            val[y]=val[x]+q
            heappush(dij,[val[y],y])
print(val[0]+1)

Solution (Python):



from queue import *


class Edge(object):
    def __init__(self, dst, len_):
        self.dst = dst
        self.len = len_


MAX_K = int(1e5 + 5)
INF = int(1e9)

K = 0
dis = [INF for i in range(0, MAX_K)]
vis = [False for i in range(0, MAX_K)]
edge = [[] for i in range(0, MAX_K)]
q = PriorityQueue()


def add(s, t, d):
    edge[s].append(Edge(t, d))


def build():
    for i in range(1, K):
        add(i, i * 10 % K, 0)
        add(i, (i + 1) % K, 1)


def dij(s):
    dis[s] = 0
    q.put((0, s))
    while not q.empty():
        x = q.get()[1]
        if vis[x]:
            continue
        vis[x] = True
        for e in edge[x]:
            if dis[e.dst] > dis[x] + e.len:
                dis[e.dst] = dis[x] + e.len
                q.put((dis[e.dst], e.dst))


if __name__ == "__main__":
    K = int(input())
    build()
    dij(1)
    print(dis[0] + 1)

Solution (Python):
from heapq import heappush, heappop

K = int(input())
adjL = [[] for i in range(K)]
for i in range(K):
    adjL[i].append(((i + 1) % K, 1))  
    adjL[i].append(((i * 10) % K, 0)) 


cost = [float('inf')] * K
cost[1] = 0
PQ = []
heappush(PQ, (0, 1)) 
while PQ:
    cNow, vNow = heappop(PQ)

    if vNow == 0: break 
    if cNow > cost[vNow]: continue

    for v2, wt in adjL[vNow]:
        c2 = cNow + wt
        if c2 < cost[v2]:
            cost[v2] = c2
            heappush(PQ, (c2, v2))


print(cost[0] + 1)

Solution (Python):
from collections import deque

K = int(input())
adjL = [[] for i in range(K)]
for i in range(K):
    adjL[i].append(((i + 1) % K, 1))  
    adjL[i].append(((i * 10) % K, 0)) 


cost = [K] * K
cost[1] = 0
Q = deque([(1, 0)]) 
while Q:
    vNow, cNow = Q.popleft()

    if vNow == 0: break 
    if cNow > cost[vNow]: continue

    for v2, wt in adjL[vNow]:
        c2 = cNow + wt
        if c2 < cost[v2]:
            cost[v2] = c2
            if wt == 1:
                
                Q.append((v2, c2))
            else:
                
                Q.appendleft((v2, c2))


print(cost[0] + 1)

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def solve(f):
    k = f.read_int()

    depth = [float('inf')] * k
    depth[1] = 1

    que = collections.deque([1])
    while len(que) > 0:
        num = que.popleft()
        n1 = (num*10)%k
        if depth[n1] > depth[num]:
            depth[n1] = depth[num]
            que.appendleft(n1)
        n2 = (num+1)%k
        if depth[n2] > depth[num]+1:
            depth[n2] = depth[num]+1
            que.append(n2)

    return depth[0]


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):
from collections import deque
K=int(input())
reached=[0 for i in range(K)]
reached[1]=1
dist=[0 for i in range(K)]
q=deque([])
q.append(1)
while(len(q)>0):
    r=q.popleft()
    v=(r+1)%K
    reached[r]=1
    if (reached[v]==0):
        q.append(v)
        dist[v]=dist[r]+1
    v=(r*10)%K
    if (reached[v]==0):
        q.appendleft(v)
        dist[v]=dist[r]
    if (reached[0]==1):
        break
print(dist[0]+1)

Solution (Python):
import heapq

K = int(input())

edge = [[] for i in range(K)]  

for i in range(1, K):
    edge[i].append(( (i+1)%K, 1) )
    edge[i].append( ((i*10)%K, 0) )


def dijkstra(fro, to, v):
    MAX = int(1e9)

    dist = [MAX]*v   
    check = [False]*v  

    dist[fro] = 0
    pq = [(0, fro)]    


    
    for i in range(v):
        
        nowNode = -1        

        while True:
            nowNode = heapq.heappop(pq)[1]  
            if not check[nowNode]:    
                check[nowNode] = True
                break

        
        for (nextNode, cost) in edge[nowNode]:
            nextDist = dist[nowNode] + cost
            if nextDist < dist[nextNode]:  
                dist[nextNode] = nextDist
                heapq.heappush(pq, (dist[nextNode], nextNode))

    return dist[to]

print(dijkstra(1, 0, K) + 1)

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def solve(f):
    n = f.read_int()
    d = [float('inf')] * n
    d[1] = 1

    que = [(1, 1)]     
    heapq.heapify(que)

    while len(que) > 0:
        dist, v0 = heapq.heappop(que)
        if d[v0] < dist: continue

        v1 = (v0*10) % n
        if d[v1] > d[v0]:
            d[v1] = d[v0]
            heapq.heappush(que, (d[v1], v1))

        v2 = (v0+1) % n
        if d[v2] > d[v0] + 1:
            d[v2] = d[v0] + 1
            heapq.heappush(que, (d[v2], v2))

    return d[0]


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):
from collections import deque

n = int(input())
q = deque()

q.append(1)
q.append(-1)  
cost = 1
costs = [-1] * n
while costs[0] == -1:
    head = q.popleft()
    if head == -1:
        cost += 1
        q.append(-1)
        continue
    elif costs[head] != -1:
        continue
    costs[head] = cost
    q.appendleft(head * 10 % n)
    q.append((head + 1) % n)
print(costs[0])

Solution (Python):
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

Solution (Python):
import heapq
k = int(input())
j = [0] * k
for i in range(k):
    j[i] = [(tuple([(i * 10) % k, 0]))]
    j[i].append(tuple([(i + 1) % k, 1]))

min_cost = [float("inf")] * k
def dijkstra(s):
    queue = [tuple([1, s])]
    while queue:
        p = heapq.heappop(queue)
        for e in j[p[1]]:
            if p[0] + e[1] >= min_cost[e[0]]:
                continue
            min_cost[e[0]] = p[0] + e[1]
            heapq.heappush(queue, tuple([min_cost[e[0]], e[0]]))
dijkstra(1)
print(min_cost[0])

Solution (Python):
import heapq

K = int(input())
adj = [dict() for i in range(K)]
for i in range(1, K):
  adj[i] = dict()
  adj[i][(i+1)%K] = 1
  adj[i][(i*10)%K] = 0

def dijkstra(adj):
  q = []
  d = dict()
  p = dict()
  n = len(adj)

  for i in range(n):
    d[i] = float('inf')

  start_id = 1
  d[start_id] = 0
  heapq.heappush(q, (0, start_id))
  S = set()

  while len(S) != n:
    dist, node_id = heapq.heappop(q)
    S.add(node_id)
    for u, c in adj[node_id].items():
      if c + d[node_id] < d[u]:
        d[u] = c + d[node_id]
        heapq.heappush(q, (d[u], u))

  return d

d = dijkstra(adj)
print(d[0]+1)

Solution (Python):

import heapq

'''
方針：mod Kで考える。すべての数字は、１を足すor10倍するの操作を繰り返せば作ることができる。
1を足す場合は、fは1増える。10倍しても、fは増加しない。
'''

K = int(input())
adj = [dict() for i in range(K)]
for i in range(1,K):
    adj[i] = dict()
    adj[i][(i+1)%K] = 1
    adj[i][(i*10)%K] = 0




def dijkstra(adj):
    '''
    :param adj: adj[i][j] distance between i and j
    adj = list(dict()) 
    :return: d[u]
    '''
    q = []  
    d = dict()  
    p = dict()  
    n = len(adj)  

    for i in range(n):
        d[i] = float('inf')
    
    start_id = 1
    d[start_id] = 0
    heapq.heappush(q, (0,start_id)) 
    S = set()

    while len(S) != n:
        
        dist, node_id = heapq.heappop(q)
        S.add(node_id)
        for u, c in adj[node_id].items(): 
            
            if c + d[node_id] < d[u]:
                d[u] = c + d[node_id]
                heapq.heappush(q, (d[u], u))
    return d



d = dijkstra(adj)
print(d[0]+1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    K = I()

    
    def search(s):
        d = collections.defaultdict(lambda: inf)
        q = [(1,s)]
        d[s] = 1
        qi = 0
        v = [False] * (K+1)
        v[s] = True
        while len(q):
            k, u = heapq.heappop(q)
            if u == 0:
                return k
            t = u*10 % K
            v[u] = True
            while not v[t]:
                if t == 0:
                    return k
                if d[t] > k:
                    heapq.heappush(q, (k, t))
                    d[t] = k
                v[t] = True
                t = t*10 % K

            i = 1
            t = (u+i) % K
            while not v[t] and t != u:
                if d[t] > k+1:
                    heapq.heappush(q, (k+1, t))
                    d[t] = k+1
                    i = i*10 % K
                    t = (u+i) % K
                else:
                    break

    return search(1)

print(main())

Solution (Python):

from collections import deque
def inpl(): return tuple(map(int, input().split()))

K = int(input())
visited = [False for _ in range(K)] 
dq = deque([(1, 1)]) 

while True:
    c, m = dq.popleft()
    visited[m] = True
    if m == 0:
        print(c)
        break
    else:
        if not visited[(m*10)%K]:
            dq.appendleft((c, (m*10)%K))
        if not visited[(m+1)%K]:
            dq.append((c+1, (m+1)%K))

Solution (Python):
import collections


dq=collections.deque()
n=input()
dis=[100000]*100005

dis[1]=1
dq.append(1)

while len(dq):
    a=dq[0]
    dq.popleft()
    if a==0:
        break
    b=(a*10)%n
    c=(a+1)%n
    if dis[b]> dis[a]:
        dis[b]=dis[a]
        dq.appendleft(b)
    if dis[c]>dis[a]+1:
        dis[c]=dis[a]+1
        dq.append(c)

print (dis[0])

Solution (Python):
import sys
from collections import deque
K = int(input())

visited = [0 for i in range(K)]
q = deque([(1,1)])
while q:
    now,cost = q.popleft()
    if now == 0:
        print(cost)
        sys.exit()
    visited[now] = 1
    v0 = (now*10) % K
    v1 = (now+1) % K
    if not visited[v0]: q.appendleft((v0, cost))
    if not visited[v1]: q.append((v1, cost+1))

Solution (Python):
import sys
from collections import deque
K = int(input())

es = []
for i in range(K):
    v0 = (i*10) % K
    v1 = (i+1) % K
    es.append((v0, v1))

visited = [0 for i in range(K)]
q = deque([(1,1)])
while q:
    now,cost = q.popleft()
    if now == 0:
        print(cost)
        sys.exit()
    visited[now] = 1
    v0,v1 = es[now]
    if not visited[v0]: q.appendleft((v0, cost))
    if not visited[v1]: q.append((v1, cost+1))

Solution (Python):


import heapq

def sumOfDigits(n):
    a = 0

    while n > 0:
        a += n%10
        n //= 10

    return a


def f(n):
    while n%2 == 0:
        n //= 2

    while n%5 == 0:
        n //= 5

    vs = [None]*n
    qs = []
    x = sumOfDigits(n)

    for i in range(1, min(n, 10)):
        vs[i] = i
        heapq.heappush(qs, (i, i))

    while len(qs) > 0:
        _, q = heapq.heappop(qs)
        q2 = q*10
        v = vs[q]
        
        for i in range(0, min(x-v, 10)):
            q3 = (q2 + i)%n
            v2 = v + i
            v3 = vs[q3]

            if v3 == None or v2 < v3:
                vs[q3] = v2
                heapq.heappush(qs, (v2, q3))
                    
            if q3 == 0 and v2 < x:
                x = v2

    return x


def test():
    assert f(6) == 3
    assert f(41) == 5
    assert f(79992) == 36


def main():
    n = int(input())
    print(f(n))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

K = int(input())

while K%2 == 0:
  K //= 2
while K%5 == 0:
  K //= 5

if K == 1:
  print(1)
  exit()

q0 = [1]
q1 = []

T = [2]*K
T[1] = 0

x = 1

while True:
  while q0:
    v = q0.pop()
    a = (v+1)%K
    if T[a] > 1:
      q1.append(a)
      T[a] = 1
    b = (v*10)%K
    if T[b] > 0:
      q0.append(b)
      T[b] = 0
  if T[0] <= 1:
    print(x+T[0])
    exit()
  q0 = q1
  q1 = []
  x += 1

Solution (Python):
from collections import deque
K = int(input())
INF = 10 ** 6
dist = [INF] * K

deq = deque()
deq.append((1, 0))
while True:
    v, d = deq.popleft()
    if dist[v] != INF:
        continue
    if v == 0:
        print(d + 1)
        break
    dist[v] = d
    if dist[(v + 1) % K] == INF:
        deq.append(((v + 1) % K, d + 1))
    if dist[v * 10 % K] == INF:
        deq.appendleft((v * 10 % K, d))

Solution (Python):
from collections import deque

K = int(input())

Q = deque((1,))
inf = float('inf')
L = [inf]*K
L[1] = 1

while Q[0] != 0:
  n = Q.popleft()
  a = (n+1)%K
  if L[a] > L[n]+1:
    L[a] = L[n]+1
    Q.append(a)
  b = (n*10)%K
  if L[b] > L[n]:
    L[b] = L[n]
    Q.appendleft(b)

print(L[0])

Solution (Python):
from collections import deque
k = int(input().strip())
a = [k+1] * k
q = deque()
q.append((1, 1))
while q:
    i, m = q.popleft()
    while 1:
        if a[i] <= m:
            break
        if i == 0:
            print(m)
            raise SystemExit
        a[i] = m
        q.append(((i+1)%k, m+1))
        i = i * 10 % k

Solution (Python):
from collections import deque


def solve(k):
    que = deque([(1, 1)])
    checked = set()
    while True:
        cost, num = que.popleft()
        if num == 0 or num == k:
            return cost
        if num in checked:
            continue
        checked.add(num)
        que.appendleft((cost, num * 10 % k))
        que.append((cost + 1, num + 1))


print(solve(int(input())))

Solution (Python):
from collections import deque
k=int(input())
dist=[1000000000 for i in range(k)]
dist[1]=0
dq=deque()
dq.append(1)
while len(dq)>0:
    it=dq.pop()
    if dist[(it+1)%k]>dist[it]+1:
        dist[(it+1)%k]=dist[it]+1
        dq.appendleft((it+1)%k)
    if dist[(it*10)%k]>dist[it]:
        dist[(it*10)%k]=dist[it]
        dq.append((it*10)%k)
print(dist[0]+1)

Solution (Python):
from collections import *
k=int(input())
q=deque([(1,1)])
v=[0]*(k+1)
while True:
    i,c=q.popleft()
    if i==0:
        break
    if v[i]:
        continue
    v[i]=True
    q.append(((i+1)%k,c+1))
    q.appendleft(((i*10)%k,c))
print(c)

Solution (Python):
from collections import deque


def calc(k):
    if k == 1:
        return 1
    d = {1: 1}
    q = deque([[1, 1]])
    while q:
        n, c = q.popleft()
        a = (n * 10) % k
        if a not in d or c < d[a]:
            d[a] = c
            q.appendleft([a, c])
        b = (n + 1) % k
        if b not in d or c + 1 < d[b]:
            d[b] = c + 1
            q.append([b, c + 1])
    return d[0]


print(calc(int(input())))

Solution (Python):
import heapq
def Dijkstra(adj, source):
    n = len(adj)-1; dist = [float('inf')]*(n+1)
    PQ = []
    for u, d in adj[0]:
        if dist[u] > d: dist[u] = d; heapq.heappush(PQ, (d, u))
    while PQ:
        d, u = heapq.heappop(PQ)
        if dist[u] != d: continue
        for v, c in adj[u]:
            if dist[v] > d+c: dist[v] = d+c; heapq.heappush(PQ, (d+c, v))
    return dist

range = xrange
k = int(raw_input())
adj = [[] for i in range(k+1)]
for i in range(k+1):
    for j in range(10):
        if i==0 and j==0: continue
        adj[i].append(((i*10+j)%k, j))
print(Dijkstra(adj, 0)[0])