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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = deque()
    q.append((1, 0))

    vis = {}
    while q:
        u, cc = q.popleft()
        if u == 0:
            return cc + 1
        vis[u] = True
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.appendleft((v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, deque
from bisect import bisect
from random import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60
def bfs(K):
  result = [INF] * K
  result[1] = 1
  que = deque([(1, 1)])
  while len(que) > 0:
    (d, u) = que.popleft()
    if result[u] < d:
      continue
    v0 = (10 * u) % K
    if d < result[v0]:
      result[v0] = d
      que.appendleft((d, v0))
    v1 = (u + 1) % K
    if d + 1 < result[v1]:
      result[v1] = d+1
      que.append((d+1, v1))
  return result

def solve(k):
  return bfs(k)[0]

K = read()
print(solve(K))

Submission status: Accepted

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

INF = 10**9+7
A = [INF] * (K)

q = deque()
q.append(1)
A[1] = 1
while q:
    x = q.popleft()
    if A[(x*10)%K] > A[x]:
        A[(x*10)%K] = A[x]
        q.appendleft((x*10)%K)
    if A[(x+1)%K] > A[x]+1:
        A[(x+1)%K] = A[x]+1
        q.append((x+1)%K)

print(A[0])

Submission status: Accepted

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

d=[1000000 for x in range(K+1)]
d[1]=1

def bfs(K):
  q=deque()
  q.append(1)
  while q:
    nx=q.popleft()
    if d[(nx*10)%K]>d[nx]:
      d[(nx*10)%K]=d[nx]
      q.appendleft((nx*10)%K)
    if d[(nx+1)%K]>d[nx]+1:
      d[(nx+1)%K]=d[nx]+1
      q.append((nx+1)%K)
  return d[0]

print(bfs(K))

Submission status: Accepted

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

d=[1000000 for x in range(K+1)]
d[1]=0

def bfs(K):
  q=deque()
  q.append(1)
  while q:
    nx=q.popleft()
    if d[(nx*10)%K]>d[nx]:
      d[(nx*10)%K]=d[nx]
      q.appendleft((nx*10)%K)
    if d[(nx+1)%K]>d[nx]+1:
      d[(nx+1)%K]=d[nx]+1
      q.append((nx+1)%K)
  return d[0]+1

print(bfs(K))

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
q = deque()
q.append(1)
d = [float("inf")] * k
d[1] = 1
while q:
    n = q.popleft()
    l, r = (n * 10) % k, (n + 1) % k
    if d[l] > d[n]:
        d[l] = d[n]
        q.appendleft(l)
    if d[r] > d[n] + 1:
        d[r] = d[n] + 1
        q.append(r)
print(d[0])

Submission status: Accepted

Solution code:
from collections import deque

def BFS01(d,K):
    d[1] = 1
    q = deque([1])
    while q:
        n = q.popleft()
        l, r = map(lambda x: (x) % K, [n * 10, n + 1])
        if d[l] > d[n]:
            d[l] = d[n]
            q.appendleft(l)

        if d[r] > d[n] + 1:
            d[r] = d[n] + 1
            q.append(r)
    return d[0]

K = int(input())
d = [float('inf')] * K

print(BFS01(d,K))

Submission status: Accepted

Solution code:
def solve(K):
    checked = [False] * K
    def calc(x):
        while not checked[x]:
            checked[x] = True
            yield x
            x = (x * 10) % K
    i = 0
    xs = [0]
    while 1:
        i += 1
        ys = []
        for x in xs:
            for z in calc((x + 1) % K):
                if z == 0:
                    return i
                ys.append(z)
        xs = ys

K = int(input())
print(solve(K))

Submission status: Accepted

Solution code:
from collections import deque

def solve(K):
    checked = [99999999999] * (K + 1)
    queue = deque()
    queue.append((1, 1))
    checked[1] = 1
    while queue:
        x, n = queue.popleft()
        if x == 0:
            return n
        _ = (x * 10) % K 
        if n < checked[_]:
            queue.appendleft((_, n))
            checked[_] = n
        _ = (x + 1) % K 
        if n + 1 < checked[_]:
            queue.append((_, n + 1))
            checked[_] = n + 1
    return None

K = int(input())
print(solve(K))

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
dist = {1: 1}

deq = deque([1])
while deq:
    v = deq.popleft()
    # x10: +0
    w = (10 * v) % K
    if dist[v] < dist.get(w, 10**9):
        dist[w] = dist[v]
        deq.appendleft(w)
    # +1: +1
    w = (v + 1) % K
    if dist[v] + 1 < dist.get(w, 10**9):
        dist[w] = dist[v] + 1
        deq.append(w)
print(dist[0])

Submission status: Accepted

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

q = deque()
q.append((1, 1, 1))
used = set()
while True:
    x, y, k = q.popleft()
    if k % K == 0:
        print(x)
        break
    if (x, 0, k*10%K) in used:
        continue
    else:
        used.add((x, 0, k*10%K))
    q.appendleft((x, 0, k*10%K))
    if (y + 1) % 10 == 0:
        q.appendleft((x, 0, k+1))
    else:
        q.append((x+1, y+1, k+1))

Submission status: Accepted

Solution code:
import math
from collections import defaultdict,deque
import numpy as np
import heapq
INF=10**12+1
a=input()
a=int(a)
graph = defaultdict(list)
for i in range(a):
    graph[i].append((1,(i+1)%a))
    graph[i].append((0,(i*10)%a))
costs=[INF]*a
costs[1]=1
que = [] #後ろの方が優先度高いqueue
que.append((0,1))
while len(que)!=0:
    temp=heapq.heappop(que)
    now=temp[1]
    v_now=graph[now]
    for c,n in v_now: #v nowから出てる総てのノードについて操作する c→ノードのコスト n→行き先
        if costs[n]>c+costs[now]: #改善したのでそのvは走査の余地あり
            costs[n]=c+costs[now]
            heapq.heappush(que,(c,n))
            
print(costs[0])

Submission status: Accepted

Solution code:
from collections import deque


def foo(k):
    q = deque([(1, 0)])
    nodes = {} #i:k+1 for i in range(k)}
    while q:
        x, cost = q.popleft()
        if x in nodes:
            continue
        nodes[x] = cost
        zero = (x * 10) % k
        one = (x + 1) % k
        q.appendleft((zero, cost ))
        q.append((one, cost + 1))
    return nodes[0]



if __name__ == "__main__":
    k = int(input())
    print(foo(k)+1)

Submission status: Accepted

Solution code:

import collections

k = int(input())

lst = [k + 1] * k

q = collections.deque([1])
lst[1] = 1

while q:
    a = q.pop()
    if lst[a * 10 % k] > lst[a]:
        lst[a * 10 % k] = lst[a]
        q.append(a * 10 % k)
    if lst[(a + 1) % k] >= lst[a] + 1:
        lst[(a + 1) % k] = lst[a] + 1
        q.appendleft((a + 1) % k)

print(lst[0])

Submission status: Accepted

Solution code:
import collections
k=int(input())
lst = [k+1]*k
q = collections.deque([1])
lst[1] = 1
while q:
    a = q.pop()
    if lst[a*10%k] > lst[a]:
        lst[a*10%k] = lst[a]
        q.append(a*10%k)
    if lst[(a+1)%k]>= lst[a]+1:
        lst[(a+1)%k] = lst[a]+1
        q.appendleft((a+1)%k)
print(lst[0])

Submission status: Accepted

Solution code:
def d_smallmultiple(K):
    import collections
    q = collections.deque()
    q.append(1)
    
    dp = [float('Inf') for _ in range(K)]
    dp[1] = 0
    
    while q:
        u = q.popleft()
        if dp[(u*10)%K] > dp[u]:
           dp[(u*10)%K] = dp[u]
           q.appendleft((u*10)%K)
        if dp[(u+1)%K] > dp[u] + 1:
            dp[(u+1)%K] = dp[u] + 1
            q.append((u+1)%K)
            
    return dp[0]+1

K = int(input())
print(d_smallmultiple(K))

Submission status: Accepted

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

L = {i: 10**6 for i in range(K)}
L[1] = 1
biq = deque()
biq.append(1)

while len(biq) > 0:
    i = biq.popleft()
    if i == 0:
        break
    j = (i * 10) % K
    if L[j] > L[i]:
        L[j] = L[i]
        biq.appendleft(j)
    k = 0 if i == K - 1 else i + 1
    if L[k] > L[i]:
        L[k] = L[i] + 1
        biq.append(k)

print(L[0])

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
E = [[((i + 1) % K, 1)] for i in range(K)]
for i in range(1, K):
	E[i].append((i * 10 % K, 0))
Q = deque([(1, 1)])
reached = set()
while 1:
	tmp_node, tmp_cost = Q.popleft()
	if tmp_node == 0:
		ans = tmp_cost
		break
	if tmp_node in reached:
		continue
	reached.add(tmp_node)
	for nxt, dist in E[tmp_node]:
		if dist == 0:
			Q.appendleft((nxt, tmp_cost))
		else:
			Q.append((nxt, tmp_cost + 1))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
v, que, k = set(), deque([(1, 1)]), input()
while que:
    n, c = que.popleft()
    if n in (0, k):
        print c
        break
    if n not in v:
        que.append((n + 1, c + 1))
        que.appendleft((n * 10 % k, c))
        v.add(n)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
d = [-1] * K
Q = [0] * (K + 1)
p = 0 # Qの先頭（次に取り出す場所）
q = 0 # Qの末尾（次に入れる場所）
d[1] = 1
Q[q] = 1
q += 1

while q - p > 0:
    # 距離0の探索
    sp = p
    ep = q
    while ep - sp > 0:
        for i in range(sp, ep):
            x = Q[i]
            y = 10 * x % K
            if d[y] < 0:
                d[y] = d[x]
                Q[q] = y
                q += 1
        sp, ep = ep, q
    # 距離1の探索
    for i in range(p, q):
        x = Q[i]
        p += 1
        y = (x + 1) % K
        if d[y] < 0:
            d[y] = d[x] + 1
            Q[q] = y
            q += 1

print(d[0])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

INF = float('inf')
K = int(input())

def zero_one_bfs_shortest_path(s, K):
    G = defaultdict(list)
    for v in range(K):
        G[v].append((0, (v * 10) % K))
        G[v].append((1, (v + 1) % K))
    d = [INF] * K
    d[s] = 0
    dq = deque()
    dq.appendleft(s)
    while len(dq) != 0:
        u = dq.popleft()
        for w, v in G[u]:
            if d[v] > d[u] + w:
                d[v] = d[u] + w
                if w == 0: dq.appendleft(v)
                else: dq.append(v)
    return d

print(zero_one_bfs_shortest_path(1, K)[0] + 1)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    """K の正の倍数の 10 進法での各桁の和としてありうる最小の値を求めてください。

    2 ≤ K ≤ 10^5

    min: 1が1つと他が0 -> 10^n, e.g.: 5*2, 25*4
    10倍しても元のKと和は変わらない
    1-9倍とは限らない?: 入力例 2　11111=41×271, 4+1=5では？
    """
    K = int(input())

    ans = sum_digits(K)
    for i in range(2, 10):
        ans = min(ans, sum_digits(K * i))

    print(ans)


def sum_digits(n):
    return sum(map(int, list(str(n))))


def main2():
    import sys

    debug = sys.argv[-1] == "debug"
    K = int(input())

    q = deque([1])
    inf = float("inf")
    dp = [inf for _ in range(K)]
    dp[1] = 0

    # 01BFS
    # cost 0 の辺の遷移は deque の先頭に要素を追加
    # cost 1 の辺の遷移は deque の末尾に要素を追加
    while q:
        idx = q.popleft()
        x = dp[idx]
        m1 = (idx * 10) % K
        m2 = (idx + 1) % K
        if dp[m1] > x:
            dp[m1] = x
            q.appendleft(m1)
        if dp[m2] > x + 1:
            dp[m2] = x + 1
            q.append(m2)

        if debug:
            print((m1, m2), dp, q, file=sys.stderr)
            print("-" * 10, file=sys.stderr)

    print(dp[0] + 1)


if __name__ == '__main__':
    main2()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import heapq
K=input()

#隣接リストa
a=[[] for i in range(K)]
for i in range(K):
	a[i].append(((i+1)%K,1))
	a[i].append((i*10%K,0))

#print "# a"
#print a

#開始位置
Start=1

#初期化
d=[-1 for i in range(K)]
d[Start]=0


#優先度付きキューに[距離,頂点の番号]を格納する
#スタート地点の頂点1には距離0を入れる
q=[]
heapq.heappush(q, [0,Start])
#print "# q"
#print q

while len(q)!=0:
	#距離が最小の頂点を取り出し
	l,u=heapq.heappop(q)
	for val in a[u]:
		v=val[0]
		l_u_v=val[1]
		#print v, l_u_v
		if (d[v]>d[u]+l_u_v) or d[v]==-1:
			d[v]=d[u]+l_u_v
			heapq.heappush(q, [d[v],v])
	#print "# q,d"
	#print q
	#print "# d"
	#print d	

print d[0]+1

Submission status: Accepted

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

from collections import deque

K = int(input())

d = [float('inf')] * K
d[1] = 1
q = deque([1])
while q:
    n = q.popleft()
    l, r = map(lambda x: (x) % K, [n * 10, n + 1])

    if d[l] > d[n]:
        d[l] = d[n]
        q.appendleft(l)

    if d[r] > d[n] + 1:
        d[r] = d[n] + 1
        q.append(r)

print(d[0])

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from heapq import heappush, heappop
INF = float("inf")


def main():
    K = int(input())
    graph = defaultdict(list)
    for i in range(K):
        graph[i].append((1, (i + 1) % K))
        graph[i].append((0, (i * 10) % K))

    cost = [INF] * K
    cost[1] = 1
    que = deque()
    que.appendleft(1)
    while len(que) != 0:
        now = que.popleft()

        for c, node in graph[now]:
            new_cost = cost[now] + c
            if new_cost < cost[node]:
                cost[node] = new_cost
                if c == 0:
                    que.appendleft(node)
                else:
                    que.append(node)

    print(cost[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections


def ans(n):
    dist = [10 ** 5] * n
    dist[1] = 1
    d = collections.deque()
    d.append(1)
    while not d.count == 0:
        u = d.popleft()
        if u == 0:
            return dist[u]
        if dist[u] < dist[(u * 10) % n]:
            dist[(u * 10) % n] = dist[u]
            d.appendleft((u * 10) % n)
        if dist[u] < dist[(u + 1) % n]:
            dist[(u + 1) % n] = dist[u] + 1
            d.append((u + 1) % n)

n = int(input())
print(ans(n))

Submission status: Accepted

Solution code:
def D_SmallMultiple(K):
    import collections
    q = collections.deque()
    q.append(1)  # 頂点1からスタート

    # dp[i]は1からi(0以上K未満)へ行くために必要なコスト(必要なのはdp[0])
    dp = [float('Inf') for _ in range(K)]
    dp[1] = 0

    while q:
        u = q.popleft()
        # 位置uから行ける場所を検索
        if dp[(u * 10) % K] > dp[u]:
            # コスト0(*10すること)で行ける場所
            dp[(u * 10) % K] = dp[u]
            q.appendleft((u * 10) % K)
        if dp[(u + 1) % K] > dp[u] + 1:
            # コスト1(+1すること)で行ける場所
            dp[(u + 1) % K] = dp[u] + 1
            q.append((u + 1) % K)
    return dp[0] + 1

K = int(input())
print(D_SmallMultiple(K))

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())

K = I()

Graph = [0]*K
for i in range(K):
    if (i+1) % K != (10*i) % K:
        Graph[i] = [(1,(i+1) % K),(0,(10*i) % K)]  # 1を加える,10倍する
    else:
        Graph[i] = [(0,(10*i) % K)]

# dijkstra

from heapq import heappush,heappop

d = [100]*K
d[1] = 1
q = []
heappush(q,(1,1))
v = [False]*K
while q:
    a,n = heappop(q)
    if v[n]:
        continue
    v[a] = True
    for da,dn in Graph[n]:
        if v[dn]:
            continue
        if a+da < d[dn]:
            d[dn] = a+da
            heappush(q,(a+da,dn))

print(d[0])

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


k = int(input())

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

dist = dijkstra(graph, k, 1)
ans = dist[0] + 1
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    while heap:
        dist2v, v_from = heappop(heap)
        if dist[v_from] < dist2v:
            continue
        for cost, v_to in graph[v_from]:
            dist_cand = dist2v + cost
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist


k = int(input())

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

dist = dijkstra(graph, k, 1)
ans = dist[0]
print(ans)

Submission status: Runtime Error

Solution code:
K=int(input())

if K%10==0:
    print(1)
else:
    mod=set([])
    i=0
    while pow(10,i,K) not in mod:
        mod.add(pow(10,i,K))
        i+=1

    mod=list(mod)
    mod.sort(reverse=True)

    ans=0
    for i in range(0,len(mod)):
        ans+=K//mod[i]
        K%=mod[i]

    print(ans)

Submission status: Runtime Error

Solution code:
import heapq
def main():
    if k==2:print(1)
    elif k==3:print(3)
    elif k==8:print(1)
    elif k==9:print(9)
    else:
        brdict = {}
        for i in range(1,k):
            if i==k-1:brdict[i] = [(0,1)]
            else:
                brdict[i] = [((i*10)%k,0)]
                if (i*10)%k!=i+1:brdict[i] += [(i+1,1)]
        start=1
        cost=[i for i in range(k)]
        cost[0]=k
        fixed=[False]*k
        fixed[start]=True
        akouho = [(1,start)]
        heapq.heapify(akouho)
        while not all(fixed):
            (fnode,fcost) = heapq.heappop(akouho)
            if fnode==0:break
            fixed[fnode]=True
            for br in brdict[fnode]:
                if not fixed[br[0]]:
                    if cost[br[0]] > fcost + br[1]:
                        cost[br[0]] = fcost + br[1]
                        heapq.heappush(akouho,(br[0],cost[br[0]]))
        print(cost[0])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq
def main():
    k=int(input())
    brdict = {}
    for i in range(1,k):
        if i==k-1:brdict[i] = [(0,1)]
        else:
            brdict[i] = [((i*10)%k,0)]
            if (i*10)%k!=i+1:brdict[i] += [(i+1,1)]
    start=1
    cost=[i for i in range(k)]
    cost[0]=k
    fixed=[False]*k
    fixed[start]=True
    akouho = [(1,start)]
    heapq.heapify(akouho)
    while not all(fixed):
        (fnode,fcost) = heapq.heappop(akouho)
        if fnode==0:break
        fixed[fnode]=True
        for br in brdict[fnode]:
            if not fixed[br[0]]:
                if cost[br[0]] > fcost + br[1]:
                    cost[br[0]] = fcost + br[1]
                    heapq.heappush(akouho,(br[0],cost[br[0]]))
    print(cost[0])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import Deque, List
except ImportError:
    pass


def solve(K: int):
    pars = list(range(K))

    def union(a: int, b: int):
        pars[a] = b

    def getpar(a: int):
        if pars[a] == a:
            return a
        pars[a] = getpar(pars[a])
        return pars[a]

    for i in range(K):
        union(getpar(i), getpar(i * 10 % K))

    gs = [getpar(i) for i in range(K)]
    G = [[] for i in range(K)]  # type: List[List[int]]
    for i in range(K):
        G[gs[i]].append(gs[(i + 1) % K])
    d = {gs[1]: 1}
    q = deque()  # type: Deque[int]
    q.append(gs[1])
    while q:
        s = q.popleft()
        for t in G[s]:
            if t in d:
                continue
            d[t] = d[s] + 1
            if t == gs[0]:
                print(d[t])
                return
            q.append(t)
    assert False


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: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import Deque, List
except ImportError:
    pass


def solve(K: int):
    pars = list(range(K))

    def union(a: int, b: int):
        pars[a] = b

    def getpar(a: int):
        if pars[a] == a:
            return a
        pars[a] = getpar(pars[a])
        return pars[a]

    for i in range(K):
        union(getpar(i), getpar(i * 10 % K))

    gs = [getpar(i) for i in range(K)]
    G = [[] for i in range(K)]  # type: List[List[int]]
    for i in range(K):
        G[gs[i]].append(gs[(i + 1) % K])
    d = {gs[1]: 1}
    q = deque()  # type: Deque[int]
    q.append(gs[1])
    while q:
        s = q.popleft()
        for t in G[s]:
            if t in d:
                continue
            d[t] = d[s] + 1
            if t == 0:
                print(d[t])
                return
            q.append(t)
    assert False


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: Runtime Error

Solution code:
def bi_power(n):
    rtn=0
    while n%2==0:
        n//=2
        rtn+=1
    return rtn

n=int(input())
print(n//=bi_power(n))

Submission status: Runtime Error

Solution code:
= input()
c = 0
for i in n:
  c += int(i)
for i in range(1,10**7):
  d = 0
  l = str(int(n)*(i+1))
  for j in l:
    d += int(j)
  c = min(c, d)
print(c)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())

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

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

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

print(p + 1)

Submission status: Runtime Error

Solution code:
K=int(input())
G=[[(1,(i+1)%K)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((0,a))
stack=list(G[1])
heapq.heapify(stack)
reached=[0]*K
reached[1]=1
while(stack):
    c,g=heapq.heappop(stack)
    if g==0:
        print(c+1)
        quit()
    reached[g]=1
    for i in G[g]:
        if reached[i[1]]:
            continue
        heapq.heappush(stack,(c+i[0],i[1]))

Submission status: Runtime Error

Solution code:
from math import log
K=int(input())
N=K
def func(N):
    res=0
    while(N!=0):
        res+=N%10
        N//=10
    return res
ans=func(K)
if ans==1:
    print(ans)
    quit()
n=ceil(log(K,10))
MOD=10**(n)
K=K*(ceil((10**n)/K))
ans=min(ans,func(K))
used=[0]*N
K%=MOD
K*=10
while(True):
    K%=N
    if K==0:
        print(1)
        quit()
    ans=min(ans,func(K)+1)
    if used[K]:
        print(ans)
        quit()
    used[K]=1
    K*=10

Submission status: Runtime Error

Solution code:
k = int(input())
from collections import deque
d = deque([1])
discovered = {1:1}
while true:
  q = d.popleft()
  if q == 0: 
  	print(discovered[q])
  	quit()
  if (q*10)%k not in discovered:
    if (q*10)%k == 0:
      
    d.appendleft((q*10)%k)
    discovered[(q*10)%k] = discovered[q]
  if q+1 not in discoverd:
    d.append(q+1)
    discovered[q+1] = discovered[q]+1

Submission status: Runtime Error

Solution code:
import heapq


def small_multiple(k):
    # kの倍数で各桁の総数が最も小さくなるような、各桁の総数
    dist = [float("inf")] * k
    q = []
    # kで割った余りが1になるような最小の数は1
    heapq.heappush(q, (1, 1))
 
    while q:
        n, c = heapq.heappop(q)
        if dist[n] <= c:
            continue
        print(n, c)
        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()

Submission status: Runtime Error

Solution code:
import heapq


def small_multiple(k):
    # kの倍数で各桁の総数が最も小さくなるような、各桁の総数
    dist = [float("inf")] * k
    q = []
    # kで割った余りが1になるような最小の数は1
    heapq.heappush(q, (1, 1))

    while q:
        n, c = heapq.heappop(q)
        if dist[n] <= c:
            continue
        print(n, c)
        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()

Submission status: Runtime Error

Solution code:
k = int(input())

def sum_keta(num):
  ans = 0
  for i in str(num):
    ans = ans + int(i)
  return ans

min_sum_keta = float("inf")
limit = k*10**len(str(k)+1)
add = k
while k < limit:
  min_sum_keta = min(min_sum_keta,sum_keta(k))
  k += add
print(min_sum_keta)

Submission status: Runtime Error

Solution code:
k = int(input())
ans= 10*10
for i in range(2,10*5):
  o = list(str(i*k))
	sumorder = sum(o)
    if sumorder < ans:
      ans = sumorder
print(ans)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def digit_sum(num:int, base:int) -> int:
    if num < base:
        return num
    else:
        return digit_sum(int(num/base), base) + (num % base)

from collections import deque

k = ni()
que = deque([1])

kmod = [0]*k

while kmod[0] == 0:
    cur = que.popleft()
    if kmod[cur%k] == 0:
        kmod[cur%k] = digit_sum(cur,10)
    
    if kmod[(10*cur)%k] == 0:
        que.appendleft(10*cur)
    
    if kmod[(cur+1)%k] == 0:
        que.append(cur+1)
            
        
print(kmod[0])

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def digit_sum(num:int, base:int) -> int:
    if num < base:
        return num
    else:
        return digit_sum(int(num/base), base) + (num % base)

from collections import deque

k = ni()
que = deque([1])

kmod = [0]*k

while kmod[0] == 0:
    cur = que.popleft()
    if kmod[cur%k] == 0:
        kmod[cur%k] = digit_sum(cur,10)
        que.appendleft(10*cur)
        que.append(cur+1)
            
        
print(kmod[0])

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def digit_sum(num:int, base:int) -> int:
    if num < base:
        return num
    else:
        return digit_sum(int(num/base), base) + (num % base)

from collections import deque

k = ni()
que = deque([1])

kmod = [0]*k

while kmod[0] == 0:
    cur = que.popleft()
    if kmod[cur%k] == 0:
        kmod[cur%k] = digit_sum(cur,10)
        
        if kmod[(10*cur)%k] == 0:
            que.appendleft(10*cur)
        if kmod[(cur+1)%k] == 0:
            que.append(cur+1)
            
        
print(kmod[0])

Submission status: Runtime Error

Solution code:
import time
begin=time.monotonic()
def sum(i):
    s=str(i)
    ret=0
    for c in s:
        ret+=int(c)
    return ret

n=int(input())
res=sum(n)
i=2
while True:
    x=n*i
    res=min(res,sum(x))
    i+=1
    if time.monotonic()-begin>1.9:
        break
print(res)

Submission status: Runtime Error

Solution code:
ktw=lambda x:sum(int(i) for i in str(x))
a=int(input())
while True:
  if a % 2 !=0:
    a/=2
  else:
    break
m=ktw(a)
for i in range(2,10**5):
  a*=i
  m=min(m,ktw(m))
print(m)

Submission status: Runtime Error

Solution code:
import bisect, functools
N = int(input())
A = sorted(int(x) for x in input().split())
B = sorted(int(x) for x in input().split())
C = sorted(int(x) for x in input().split())

@functools.lru_cache(maxsize=None)
def a(n):
    return bisect.bisect_left(A, n)

@functools.lru_cache(maxsize=None)
def b_i(i):
    if i >= 1:
        return b_i(i - 1) + a(B[i - 1])
    return 0

@functools.lru_cache(maxsize=None)
def b(n):
    return b_i(min(len(B), bisect.bisect_left(B, n)))

def c():
    return sum(b(x) for x in C)

print(c())

Submission status: Runtime Error

Solution code:
import heapq as hq

INF = 10_0000_0007
K = int(input())

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

h = []
hq.heappush(h, (1, 1))

while h:
    v, c = hq.heappop(h)
    if dist[v] <= c:
        continue
    dist[v] = c
    
    if dist[(v+1)%K] > c+1:
        hq.heappush(h, ((v+1)%K, c+1))
    if dist[(v*10)%K] > c:
        hq.heappush(h, ((v*10)%K, c))

print(dist[0])