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):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import deque
def resolve():
    k=int(input())
    E=[[] for _ in range(k)]
    for i in range(k):
        E[i].append(((i+1)%k,1))
        E[i].append(((10*i)%k,0))

    
    dist=[INF]*k
    dist[1]=0
    Q=deque([1])
    while(Q):
        v=Q.popleft()
        for nv,w in E[v]:
            if(dist[nv]<=dist[v]+w): continue
            dist[nv]=dist[v]+w
            if(w==0): Q.appendleft(nv)
            else: Q.append(nv)
    print(dist[0]+1)
resolve()

Solution (Python):
def bfs_01(v,mod):
    q = deque(); q.append(v)
    visited = [False] * mod
    cur = 0
    while cur == 0:
        s, x = q.popleft()
        if visited[x]:
            continue
        visited[x] = True
        if x == 0:
            cur = s
            return cur
        q.appendleft((s, (10 * x) % mod))
        q.append((s + 1, (x + 1) % mod))
def examD():
    K = I()
    ans = bfs_01((1,1),K)
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

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

que = deque()
que.append((1,1))
dist = [float("inf")]*k
while que:
    cost, cur = que.popleft()
    if dist[cur] <= cost:
        continue
    dist[cur] = cost
    
    nxt = (cur+1)%k
    que.append((cost+1,nxt))
    
    nxt = cur*10 % k
    que.appendleft((cost, nxt))
print(dist[0])

Solution (Python):
from heapq import heappush, heappop
k = int(input())

heap = [(1,1)]
dist = [float("inf")]*k
while heap:
    cost, cur = heappop(heap)
    if dist[cur] <= cost:
        continue
    dist[cur] = cost
    
    nxt = (cur+1)%k
    heappush(heap, (cost+1, nxt))
    
    nxt = cur*10 % k
    heappush(heap, (cost, nxt))

print(dist[0])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ高速化版(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    res = [INF] * N
    
    que = [1*N+src]
    
    res[src] = 1*N

    while len(que) != 0:
        cur = heappop(que)
        dist = cur // N
        cur %= N
        for nxt, cost in nodes[cur]:
            if dist + cost < res[nxt]:
                res[nxt] = dist + cost
                heappush(que, (dist+cost)*N+nxt)
    return res

K = INT()

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

res = dijkstra(K, nodes, 1)
print(res[0])

Solution (Python):
from collections import deque
 

 
K = int(input())
q = deque()
q.append((1,1)) 
visited = [False]*K
 
ans = 0
 
while ans == 0:
  s,x = q.popleft()
  if visited[x]:
    continue
  visited[x] = True
  if x == 0:
    ans = s
    break
  q.appendleft((s,(10*x)%K))
  q.append((s+1,(x+1)%K))

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


k = I()
cost = [INF] * k
cost[1] = 1
que = deque([1])
while que:
    cur = que.popleft()
    nxt = (cur * 10) % k
    if cost[cur] < cost[nxt]:
        cost[nxt] = cost[cur]
        que.appendleft(nxt)
    nxt = (cur + 1) % k
    if cost[cur] + 1 < cost[nxt]:
        cost[nxt] = cost[cur] + 1
        que.append(nxt)



print(cost[0])

Solution (Python):
from collections import deque

K = int(input())

deq = deque([(1, 1)])
history = set()

while True:
	to = deq.popleft()
	if to[0] == 0:
		print(to[1])
		break
	elif to[0] not in history:
		history.add(to[0])
		deq.appendleft((to[0] * 10 % K, to[1]))
		deq.append((to[0] + 1, to[1] + 1))

Solution (Python):
from collections import deque

K = int(input())

deq = deque([(1, 1)])
history = set()

while True:
	to = deq.popleft()
	if to[0] == 0:
		print(to[1])
		break
	elif to[0] not in history:
		history.add(to[0])
		deq.appendleft((to[0] * 10 % K, to[1]))
		deq.append((to[0] + 1, to[1] + 1))

Solution (Python):
from heapq import heappush, heappop

K = int(input())

queue = [(1, 1)]
dist = [float('inf')] * K
dist[1] = 1

while queue :
    cost, cur = heappop(queue)
    if cost + 1 < dist[(cur + 1) % K] :
        dist[(cur + 1) % K] = cost + 1
        heappush(queue, (cost + 1, (cur + 1) % K))
    if cost < dist[cur * 10 % K] :
        dist[cur * 10 % K] = cost
        heappush(queue, (cost, cur * 10 % K))
     
print(dist[0])

Solution (Python):



"""
01-BFS
辺の重みが0 or 1 のとき、dequeを使ってdijkstraを高速化できる
"""
from collections import deque
def bfs01(g,start):
    n = len(g)
    res = [float("inf")]*n 
    res[start] = 0
    pending = n-1 
    q = deque([(0,start)]) 
    while q and pending:
        dv,v = q.popleft()
        if res[v] < dv: continue
        pending -= 1
        
        for to,cost in g[v]:
            if dv + cost < res[to]:
                res[to] = dv + cost
                if cost: q.append((res[to],to))
                else: q.appendleft((res[to],to))
    return res






import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

k = int(input())

g = [[] for _ in range(k)]
for i in range(k):
    g[i].append(((i+1)%k,1))
    g[i].append((10*i%k,0))

res = bfs01(g,1)
print(res[0]+1)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

k = int(input())

g = [[] for _ in range(k)]
for i in range(k):
    g[i].append(((i+1)%k,1))
    if i: g[i].append((10*i%k,0))


"""
from collections import deque
q = deque([1])
INF = float("inf")
res = [INF]*k
res[1] = 1
while q and res[0] == INF:

    v = q.popleft()
    for c,d in g[v]:
        if res[c] <= res[v] + d: continue
        res[c] = res[v] + d
        if d: q.append(c)
        else: q.appendleft(c)



print(res[0])
"""

from heapq import *
def dijkstra(g,start):
    n = len(g)
    dist = [float("inf")]*(n) 
    pending = n-1 
    dist[start] = 0
    q = [(0,start)] 
    while q and pending:
        c,v = heappop(q)
        if dist[v] < c: continue
        pending -= 1
        for to, cost in g[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(q, (dist[to], to))
    return dist

dist = dijkstra(g,1)
print(dist[0]+1)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))





k = I()
graph = [[] for _ in range(k)]
for i in range(k):
    graph[i].append([(i+1)%k, 1])
    graph[i].append([(10*i)%k, 0])


def dijkstra(x):
    d = [inf] * k
    d[x] = 1
    visited = {x}
    h = [(0, x)]

    while h:
        u = heappop(h)[1]
        visited.add(u)
        for node, cost in graph[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heappush(h, (d[u]+cost, node))
    return d


print(dijkstra(1)[0])

Solution (Python):


from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def I(): return int(sys.stdin.readline())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a = input()
    b = input()
    if a[2] == b[0] and a[1] == b[1] and a[0] == b[2]:
        print("YES")
    else:
        print("NO")
    return


def B():
    n = I()
    n = int(math.sqrt(n))
    print(n**2)
    return


def C():
    n = I()
    a = LI()
    a.sort()
    b = LI()
    b.sort()
    c = LI()
    c.sort()
    ans = 0
    for i in b:
        x = bisect_left(a, i)
        x = x * (n - bisect_right(c, i))
        ans += x
    print(ans)
    return










def D():
    k = II()
    dp = [inf] * k
    q = deque()
    q.append(1)
    dp[1] = 1
    while q:
        i = q.pop()
        if dp[(i * 10) % k] > dp[i]:
            dp[(i * 10) % k] = dp[i]
            q.appendleft((i * 10) % k)
        if dp[(i + 1) % k] > dp[i] + 1:
            dp[(i + 1) % k] = dp[i] + 1
            q.append((i + 1) % k)
    print(dp[0])
    return



if __name__ == '__main__':
    D()

Solution (Python):


from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def I(): return int(sys.stdin.readline())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a = input()
    b = input()
    if a[2] == b[0] and a[1] == b[1] and a[0] == b[2]:
        print("YES")
    else:
        print("NO")
    return


def B():
    n = I()
    n = int(math.sqrt(n))
    print(n**2)
    return


def C():
    n = I()
    a = LI()
    a.sort()
    b = LI()
    b.sort()
    c = LI()
    c.sort()
    ans = 0
    for i in b:
        x = bisect_left(a, i)
        x = x * (n - bisect_right(c, i))
        ans += x
    print(ans)
    return








def D():
    k = II()
    dp = [inf] * k
    q = deque()
    q.append(1)
    dp[1] = 1
    while q:
        i = q.pop()
        if dp[(i * 10) % k] > dp[i]:
            dp[(i * 10) % k] = dp[i]
            q.appendleft((i * 10) % k)
        if dp[(i + 1) % k] > dp[i] + 1:
            dp[(i + 1) % k] = dp[i] + 1
            q.append((i + 1) % k)
    print(dp[0])
    return



if __name__ == '__main__':
    D()

Solution (Python):
from collections import deque

K = int(input())

G = [None]*K
for i in range(K):
    G[i] = ((10*i % K, 0), ((i+1) % K, 1))
s = 1

dist = [10**9] * K
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0]+1)

Solution (Python):
import collections

K = int(input())

q = collections.deque([(1, 0)])
v = {1}

while len(q) > 0:
    c, p = q.popleft()
    v.add(c)
    if c == 0:
        break

    n1, n10 = (c + 1) % K, (c * 10) % K
    if not n1 in v:
        q.append((n1, p + 1))
    if not n10 in v:
        q.appendleft((n10, p))

print(p + 1)

Solution (Python):

import sys
import heapq
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(K: int):
    g = Graph(K)
    for i in range(1, K):
        
        g.add_edge([i, (i+1) % K, 1])
        
        g.add_edge([i, (10*i) % K, 0])
    dist, prev = shortestPath(g, 1)
    print(dist[0]+1)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from math import *
from heapq import *

def dijkstra(s, edges, INF = 10 ** 20):
    dist = [INF for _ in range(len(edges))]
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u, cost in edges[v]:
            if dv + cost < dist[u]:
                dist[u] = dv + cost
                heappush(h, (dist[u], u))
    return dist

K = int(input())
es = [[] for i in range(K)]
for i in range(1, K):
    k = i*10
    for j in range(10):
        es[i].append([(k+j)%K, j])
print(dijkstra(1, es)[0]+1)

Solution (Python):
from collections import deque

def solve(k):
    que = deque()
    que.append((1, 1))
    dp = {1: 1}
    while que:
        x, c = que.pop()
        y = (x + 1) % k
        if (not y in dp) or (dp[y] > c + 1):
            dp[y] = c + 1
            que.appendleft((y, c+1))
        z = (10 * x) % k
        if (not z in dp) or (dp[z] > c):
            dp[z] = c
            que.append((z, c))
    return dp[0]

k = int(input())
print(solve(k))

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
K = int(input())
g = [[] for _ in range(K)]
for n in range(1,K+1):
    g[n%K] += [(1,(n+1)%K),(0,10*n%K)]

print(dijkstra(g,K,1)[0]+1)

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

G = [((10*i % K, 0), ((i+1) % K, 1)) for i in range(K)]
s = 1

dist = [10**9] * K
S = [s]
T = []
dist[s] = 0

d = 0
while S:
    while S:
        v = S.pop()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0]+1)

Solution (Python):
from collections import deque

K = int(input())

G = [((10*i % K, 0), ((i+1) % K, 1)) for i in range(K)]
s = 1

dist = [10**9] * K
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0]+1)

Solution (Python):
from collections import deque

K = int(input())

G = [((10*i % K, 0), ((i+1) % K, 1)) for i in range(K)]
s = 1

dist = [10**9] * K
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0]+1)

Solution (Python):
from collections import deque

K = int(input())

G = [((10*i % K, 0), ((i+1) % K, 1)) for i in range(K)]
s = 1

dist = [10**9] * K
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0]+1)

Solution (Python):
from collections import deque

K = int(input())

G = [None]*K
for i in range(K):
    G[i] = ((10*i % K, 0), ((i+1) % K, 1))
s = 1

dist = [10**9] * K
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d+c < dist[w]:
                dist[w] = d+c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0]+1)

Solution (Python):
from collections import deque

K = int(input())

G = [None]*K
for i in range(K):
    G[i] = ((10*i % K, 0), ((i+1) % K, 1))
s = 1

dist = [10**9] * K
que = deque([s])
dist[s] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w, c in G[v]:
        if d+c < dist[w]:
            dist[w] = d+c
            if c:
                que.append(w)
            else:
                que.appendleft(w)

print(dist[0]+1)

Solution (Python):
import heapq
K=int(input())
G=[[((i+1)%K,1)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((a,0))
def dijkstra(G,s):
  INF=10**19
  n=len(G)
  d=[INF]*n
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heapq.heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heapq.heappush(que,(d[node],node))
  return d

d=dijkstra(G,1)
print(d[0]+1)

Solution (Python):
import heapq
K=int(input())
G=[[((i+1)%K,1)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((a,0))
def dijkstra(G,s):
  INF=10**19
  n=len(G)
  d=[INF]*n
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heapq.heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heapq.heappush(que,(d[node],node))
  return d

d=dijkstra(G,1)
print(d[0]+1)

Solution (Python):
import heapq
K = int(input())
visited=[0]*100001
visited[1]=1
queue=[(1,1)]

while queue and queue[0][1] != 0:
    cost, value = heapq.heappop(queue)
    cand1 = value*10 % K
    cand2 = (value+1) % K
    if not visited[cand1]:
        visited[cand1] = 1
        heapq.heappush(queue,(cost, cand1))
    if not visited[cand2]:
        visited[cand1] = 1
        heapq.heappush(queue,(cost+1, cand2))

print(queue[0][0])

Solution (Python):
import heapq

def generate_graph(K):
    return [{(i + 1) % K: 1, (i * 10) % K: 0} for i in xrange(K)]

def dijkstra(start, goal, graph):
    answer = [float("inf")] * len(graph)
    answer[start] = 0
    remains = sorted([[v, i] for i, v in enumerate(answer)])

    while remains:
        _, i = heapq.heappop(remains)
        for j, cost in graph[i].items():
            if answer[j] > answer[i] + cost:
                answer[j] = answer[i] + cost
                heapq.heappush(remains, [answer[j], j])

    return answer[goal] + 1

K = int(input())
graph = generate_graph(K)
print dijkstra(1, 0, graph)

Solution (Python):


from collections import* 





from heapq import* 


import sys
input=sys.stdin.readline  
sys.setrecursionlimit(10**6)

def DIJKSTRA(point,d,n):
    cost      = {node:float("inf") for node in range(n)}
    Q         = []  
    cost[point]=0  
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    k=int(input())
    d=defaultdict(list)
    for i in range(k-1): 
        d[i].append([i+1,1])
    d[k-1].append([0,1])
    for i in range(k):  
        d[i].append([(i*10)%k,0])
    
    
    
    print(DIJKSTRA(1,d,k)[0]+1)

    
    
    
    
if __name__ == '__main__':
    main()

Solution (Python):











import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    from collections import deque
    K = I()
    edge = [[]for _ in range(K)]
    for i in range(K):
        edge[i].append((i * 10) % K)
        edge[i].append((i + 1)%K)
        
    zero_one_deque = deque([(1, 1)])
    node = [inf] * K
    
    node[1] = 1
    searched = set()
    while zero_one_deque:
        from_ , digit_sum = zero_one_deque.popleft()
        if from_ in searched:
            continue
        else:
            searched.add(from_)
            node[from_] = digit_sum
            
        for i, to in enumerate(edge[from_]):
            if i == 0:
                zero_one_deque.appendleft((to,node[from_]))
            else:   
                zero_one_deque.append((to, node[from_] + 1))
    print(node[0])
                    

if __name__ == '__main__':
    main()

Solution (Python):
import collections
K = int(input())
Q = collections.deque([(1, 1)])
searched = set()
while True:
    n, d = Q.popleft()
    r = n % K
    if not r in searched:
        if r == 0:
            break
        else:
            searched.add(r)
            Q.append((n + 1, d + 1))
            Q.appendleft((n * 10 % K, d))
print(d)

Solution (Python):



def loop(i):
    j = (10 * i) % K
    if dp[i] < dp[j-1] + 1 and dp[i] < dp[j]:
        dp[j] = dp[i]
        return j, True
    if dp[j-1] + 1 < dp[i] and dp[j-1] + 1 < dp[j]:
        dp[j] = dp[j-1] + 1
        return j, True
    return j, False


K = int(input())

dp = [K + 1 for _ in range(K)]

dp[1] = 1
for i in range(1, K):
    if i == 1:
        pass
    else:
        dp[i] = min(dp[i-1] + 1, dp[i])
    l = i
    while True:
        l, updated = loop(l)
        if not updated:
            break

dp[0] = min(dp[K - 1] + 1, dp[0])
print(dp[0])

Solution (Python):
k = int(input())
from collections import deque
d = deque( )
d.append((1,1))
discovered = set()
while True:
  node, cost = d.popleft()
  discovered |= {node}
  if node == 0: 
  	print(cost)
  	quit()
  if (node*10)%k not in discovered:
    d.appendleft( ((node*10)%k  ,cost))
  if (node+1)%k not in discovered:
    d.append((node+1,cost+1))

Solution (Python):
import heapq


def small_multiple(k):
    
    dist = [float("inf")] * k
    q = []
    
    heapq.heappush(q, (1, 1))

    while q:
        n, c = heapq.heappop(q)
        if dist[n] <= c:
            continue
        dist[n] = c

        if dist[(n + 1) % k] > c + 1:
            heapq.heappush(q, ((n + 1) % k, c + 1))
        if dist[(n * 10) % k] > c:
            heapq.heappush(q, ((n * 10) % k, c))

    print(dist[0])


def main():
    k = int(input())
    small_multiple(k)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

K = int(input())






distances = [INF for _ in range(K)]


distances[1] = 1
remains = deque()
remains.append((1, 1))
while True:
    d, mod_k = remains.popleft()
    if mod_k == 0:
        break
    if d + 1 < distances[(mod_k + 1) % K]:
        distances[(mod_k + 1) % K] = d + 1
        remains.append((d + 1, (mod_k + 1) % K))
    if d < distances[mod_k * 10 % K]:
        distances[mod_k * 10 % K] = d
        remains.appendleft((d, mod_k * 10 % K))
print(distances[0])

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

K = int(input())






distances = [INF for _ in range(K)]


remains = deque()
remains.append((1, 1))
while distances[0] == INF:
    d, mod_k = remains.popleft()
    distances[mod_k] = d
    if distances[(mod_k + 1) % K] == INF:
        remains.append((d + 1, (mod_k + 1) % K))
    if distances[mod_k * 10 % K] == INF:
        remains.appendleft((d, mod_k * 10 % K))
print(distances[0])

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

import heapq
INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        return self.dist

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

DIJ = Dijkstra(edge)
DIJ.calc
print(DIJ.calc(1)[0] + 1)

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N = int(input())
for i in range(N):
    g.add_edge(i, (i+1)%N, 1)
    g.add_edge(i, (10 * i) % N, 0)

d = Dijkstra(g, 1)
print(d.dist[0]+1)

Solution (Python):


import itertools
from scipy.sparse import coo_matrix, lil_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford, floyd_warshall



N = int(input())

rows = []
cols = []
weights = []

"""
for _ in range(M):
    
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)
"""

for i in range(N):
    rows.append(i)
    cols.append((i+1)%N)
    weights.append(1)

for i in range(N):
    if i - ((10 * i) % N) == -1:
        weights[i] = 0
    elif i == N-1 and i - ((10 * i) % N) == 1:
        weights[i] = 0
    else:
        rows.append(i)
        cols.append((10 * i) % N)
        weights.append(0)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()


d1 = dijkstra(graph, indices=1, directed=True, unweighted=False)

print(int(d1[0]+1.5))

Solution (Python):
from collections import deque
K = int(input())
E = [[(i*10)%K,(i+1)%K] for i in range(K)] 
INF = K*10
V = [INF] * (K)
V[1] = 1
q = deque([1])
i = 1
while q:
    i = q.popleft()
    if V[E[i][0]] > V[i]:
        q.appendleft(E[i][0])
        V[E[i][0]] = V[i]
    if V[E[i][1]] > V[i]+1:
        q.append(E[i][1])
        V[E[i][1]] = V[i]+1
print(V[0])

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


dist = [float('inf')] * K
dist[1] = 1
que = deque()
que.append(1)

while que:
    n = que.pop()
    for v, c in G[n]:
        if dist[v] > dist[n] + c:
            dist[v] = dist[n] + c
            if c == 0:
                que.append(v)
            else:
                que.appendleft(v)

print(dist[0])