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



Sample input:
6


Sample output:
3

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def v(n):
        return [n*10%k, (n+1)%k]
    k = I()
    d = [float("inf")]*k
    d[1] = 1
    q = deque([1])
    while q:
        x = q.popleft()
        vx = v(x)
        dx = d[x]
        for c in range(2):
            nd = dx+c
            y = vx[c]
            if nd < d[y]:
                d[y] = nd
                if c:
                    q.append(y)
                else:
                    q.appendleft(y)
    print(d[0])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
mins = [1000 for i in range(n+1)]
used = [0 for i in range(n+1)]
deq = deque()
deq.append((1,1))
while deq:
  x,cnt = deq.popleft()
  mins[x] = min(mins[x],cnt)
  used[x] = 1
  if used[10*x%n] == 0:
    deq.appendleft((10*x%n,cnt))
  if used[(x+1)%n] == 0:
    deq.append(((x+1)%n,cnt+1))
print(mins[0])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
cost = [-1] * K
deq = deque([(1,1)])
while deq:
    x, d = deq.popleft()
    if cost[x] >= 0: continue
    cost[x] = d
    if x == 0: break
    for y, c in [(10*x%K, 0), ((x+1)%K, 1)]:
        if c: deq.append((y, d + 1))
        else: deq.appendleft((y, d))
print(cost[0])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

visited = [False] * K
Q = deque([(1, 1)])

while True:
    s, v = Q.popleft()
    if v == 0:
        print(s)
        quit()

    if visited[v]:
        continue
    visited[v] = True

    Q.appendleft((s, (10 * v) % K))
    Q.append((s + 1, (v + 1) % K))

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
t=[1]*k
q=deque()
q.append((1,1))
while q:
    p,r=q.popleft()
    if p==0:
        print(r)
        break
    if t[p]:
        t[p]=0
        q.appendleft(((p*10)%k,r))
        q.append(((p+1)%k,r+1))

Submission status: Accepted

Solution code:
from collections import deque
 
# 1から初めて、xがあるとき10x、x+1のいずれかが行えるとしてqueue
 
K = int(input())
q = deque()
q.append((1,1)) # 各桁の和、modulo K
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)

Submission status: Accepted

Solution code:
K = int(input())
G = [[] for _ in range(K)]
for i in range(K):
    G[i].append((1, (i+1)%K))
    G[i].append((0, (i*10)%K))
from collections import deque
que = deque([1])
dist = [-1]*K
dist[1] = 0
"""while que:
    v = que.pop()
    d = dist[v]
    for nv, c in G[v]:
        if dist[nv]>=0:
            continue
        if c == 0:
            que.append(nv)
            dist[nv] = d
        else:
            que.appendleft(nv)
            dist[nv] = d+1
    print(que)"""
import heapq
inf = 10**10
def dijkstra(s, n, G):#スタート, 頂点数, グラフ:[[(cost, v)], ...]
    dist = [inf]*n
    edges = []#(sからvまでのコストの候補, v)
    dist[s] = 0
    for e in G[s]:
        heapq.heappush(edges, e)
    while edges:
        cost, v = heapq.heappop(edges)
        if dist[v] != inf:
            continue
        dist[v] = cost
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv))
    return dist
dist = dijkstra(1, K, G)
print(dist[0]+1)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush 
from collections import deque
k=int(input())
inf=float("inf")
data=[[] for i in range(k)]
for i in range(1,k):
    if i%10==9:
        data[i]=[[i*10%k,0]]
    else:
        data[i]=[[i*10%k,0],[(i+1)%k,1]]

que=deque([[1,1]])
ans=[inf]*k
while que:
    c,u=que.popleft()
    ans[u]=c
    for v,d in data[u]:
        if ans[v]==inf:
            if d==0:
                que.appendleft([c,v])
            else:
                que.append([c+1,v])
    if ans[0]!=inf:
        break
print(ans[0])

Submission status: Accepted

Solution code:
K=int(input())

D=[K*10]*K
D[1]=1

import heapq

Q=[(1,1)]

while Q:
    c,x=heapq.heappop(Q)

    if D[x*10%K]>c:
        D[x*10%K]=c
        heapq.heappush(Q,(c,x*10%K))

    if D[(x+1)%K]>c+1:
        D[(x+1)%K]=c+1
        heapq.heappush(Q,(c+1,(x+1)%K))

print(D[0])

Submission status: Accepted

Solution code:
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))

    # 0-1 BFS
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    # +1
    nxt = (cur+1)%k
    que.append((cost+1,nxt))
    # *10
    nxt = cur*10 % k
    que.appendleft((cost, nxt))
print(dist[0])

Submission status: Accepted

Solution code:
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
    # +1
    nxt = (cur+1)%k
    heappush(heap, (cost+1, nxt))
    # *10
    nxt = cur*10 % k
    heappush(heap, (cost, nxt))

print(dist[0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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
    # スタート位置(今回は開始コストが0じゃないので1*Nを含める)
    que = [1*N+src]
    # 今回の開始位置1のコストは1
    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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

"""
01-BFS
辺の重みが0 or 1 のとき、dequeを使ってdijkstraを高速化できる
"""
from collections import deque
def bfs01(g,start):
    n = len(g)
    res = [float("inf")]*n #startからの最短距離
    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
        #if v==goal: break
        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

######################################################################
#ARC084 small multiple
#
######################################################################

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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

#print(g)
"""
from collections import deque
q = deque([1])
INF = float("inf")
res = [INF]*k
res[1] = 1
while q and res[0] == INF:
#    print(q)
    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)
#print(used)
print(res[0])
"""

from heapq import *
def dijkstra(g,start):
    n = len(g)
    dist = [float("inf")]*(n) #startからの最短距離
    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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC77 D

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

#頂点iにmod(k)でiと等しい正の整数の集合を割り当て、頂点iから10i+j(0≦j≦9,mod(k))にコストjの有向辺を張ったグラフを考える
#頂点v(1≦v≦9)への到達コストの初期値をvとし、ダイクストラ法で頂点0(kの倍数)への到達コストを求める
#頂点iから+1して移動できる頂点:=桁和+1(コスト1),頂点iから*10して移動できる頂点:=桁和そのまま(コスト0) の2通りに遷移できる

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])
#print(graph)

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

Submission status: Accepted

Solution code:

#!/usr/bin/env python3
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')

#A
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

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

#C
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

# D
# 解説AC
# 俺は正数問題を解いていたと思ったらいつのまにかグラフ問題を解いていた
# 何を言ってるかわからねーと思うが自分もわからねぇ(ｒｙ)
# 変態
# 全部の数字は足す1もしくは×10で考えられて前者なら全体の和が1増えて後者なら
# 変わらないということに気づいたらいけるんだと思う（いけるとは言ってない）
# 倍数の下で何かをするというよりはそのKのmod下にて最小な桁和がいくつになるのか
# という考えに至るとほぼ勝ち
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


#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:

#!/usr/bin/env python3
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')

#A
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

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

#C
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

# D
# 解説AC
# 俺は正数問題を解いていたと思ったらいつのまにかグラフ問題を解いていた
# 何を言ってるかわからねーと思うが自分もわからねぇ(ｒｙ)
# 変態
# 全部の数字は足す1もしくは×10で考えられて前者なら全体の和が1増えて後者なら
# 変わらないということに気づいたらいけるんだと思う（いけるとは言ってない）
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


#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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):
        # 1を加える
        g.add_edge([i, (i+1) % K, 1])
        # 10倍する
        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))  # type: int
    solve(K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):#Gはi->jの辺をG[i]=[(j,cost),...]で保存
  INF=10**19
  n=len(G)
  d=[INF]*n#n=node数
  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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
#from fractions import gcd
#from functools import* #reduce
#from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
#from operator import mul
#from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
#from math import factorial
#from copy import deepcopy
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):  #10倍をつなぐ
        d[i].append([(i*10)%k,0])
    #print(d)
    
    
    print(DIJKSTRA(1,d,k)[0]+1)

    
    
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
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
    #1から始めて、Kの倍数を見つける 01BFS
    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()

Submission status: Accepted

Solution code:
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)
# https://img.atcoder.jp/arc084/editorial.pdf

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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

Submission status: Accepted

Solution code:
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))