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:
n = int(input())

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

from queue import *


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


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

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


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


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


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


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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

K = int(input())
adjL = [[] for i in range(K)]
for i in range(K):
    adjL[i].append(((i + 1) % K, 1))  # i→(i+1) に、重み1の辺を張る
    adjL[i].append(((i * 10) % K, 0)) # i→(i*10)に、重み0の辺を張る

# ダイクストラ法
cost = [float('inf')] * K
cost[1] = 0
PQ = []
heappush(PQ, (0, 1)) # 1からスタート
while PQ:
    cNow, vNow = heappop(PQ)

    if vNow == 0: break # 0に到達したら終了
    if cNow > cost[vNow]: continue

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

# 「1→0への最短経路長」+1が求める答え
print(cost[0] + 1)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
adjL = [[] for i in range(K)]
for i in range(K):
    adjL[i].append(((i + 1) % K, 1))  # i→(i+1) に、重み1の辺を張る
    adjL[i].append(((i * 10) % K, 0)) # i→(i*10)に、重み0の辺を張る

# 【01BFS】
cost = [K] * K
cost[1] = 0
Q = deque([(1, 0)]) # 1からスタート
while Q:
    vNow, cNow = Q.popleft()

    if vNow == 0: break # 0に到達したら終了
    if cNow > cost[vNow]: continue

    for v2, wt in adjL[vNow]:
        c2 = cNow + wt
        if c2 < cost[v2]:
            cost[v2] = c2
            if wt == 1:
                # 重み1の辺ならば、キューの末尾に追加する
                Q.append((v2, c2))
            else:
                # 重み0の辺ならば、キューの先頭に追加する
                Q.appendleft((v2, c2))

# 「1→0への最短経路長」+1が求める答え
print(cost[0] + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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

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

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

    return depth[0]


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

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

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

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

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

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

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:
import heapq

K = int(input())

edge = [[] for i in range(K)]  # (node, cost) list list

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

# fro から to への最短距離(v は頂点数)
def dijkstra(fro, to, v):
    MAX = int(1e9)

    dist = [MAX]*v   # fro からの距離を格納する
    check = [False]*v  # すでにその頂点からを調べたかのフラグ

    dist[fro] = 0
    pq = [(0, fro)]    # (-cost, node)


    # 頂点は v 個あるので、v 周する
    for i in range(v):
        # 調べ済みでない頂点のうち、最も近い頂点を now に入れる
        nowNode = -1        # このターンにフォーカスするノード

        while True:
            nowNode = heapq.heappop(pq)[1]  # 最小コストから貪欲に取っていく
            if not check[nowNode]:    # まだチェックされていないノードだったら決定
                check[nowNode] = True
                break

        # その頂点からたどり着ける頂点の情報を更新する
        for (nextNode, cost) in edge[nowNode]:
            nextDist = dist[nowNode] + cost
            if nextDist < dist[nextNode]:  # 既存の通路より近いなら更新
                dist[nextNode] = nextDist
                heapq.heappush(pq, (dist[nextNode], nextNode))

    return dist[to]

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

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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

    que = [(1, 1)]     # (min_dist, vertex)
    heapq.heapify(que)

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

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

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

    return d[0]


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

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

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

Submission status: Accepted

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

print dist[0] + 1

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq

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

def dijkstra(adj):
  q = []# p q
  d = dict()# min cost from start
  p = dict()# parent node
  n = len(adj)# num of node

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

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

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

  return d

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

Submission status: Accepted

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

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

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

# print(adj)
# １から０への最短経路を見つける
# ダイクストラ法
def dijkstra(adj):
    '''
    :param adj: adj[i][j] distance between i and j
    adj = list(dict()) #隣接リスト形式
    :return: d[u]
    '''
    q = []  # プライオリティキュー
    d = dict()  # 始点からvまでの最短コスト
    p = dict()  # 親ノードを保存
    n = len(adj)  # ノードの数

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

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



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

Submission status: Accepted

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

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

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


def main():
    K = I()

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

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

    return search(1)

print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return tuple(map(int, input().split()))

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

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

Submission status: Accepted

Solution code:
import collections


dq=collections.deque()
n=input()
dis=[100000]*100005
# print(dis[100])
dis[1]=1
dq.append(1)

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

print (dis[0])

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

import heapq

def sumOfDigits(n):
    a = 0

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

    return a


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

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

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

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

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

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

    return x


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

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

q0 = [1]
q1 = []

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

x = 1

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

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

print(L[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque


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


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque


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


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

Submission status: Accepted

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

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

Submission status: Judge Not Available

Solution code:
from collections import deque
K = int(input())
d={1:1}
q = deque()
q.append([1,1])

while q:
    a,c = q.popleft()
    a_ = (a*10)%K
    if(a_ not in d or c < d[a_]):
        d[a_]=c
        q.appendleft([a_,c])
    b_ = (a+1)%K
    if(b_ not in d or c < d[b_]):
        d[b_] = c+1
        q.append([b_,c+1])

print(d[0])

Submission status: Runtime Error

Solution code:
k = int(input())
g = [[] for _ in range(k)]
for i in range(1,k):
    g[i].append([i*10%k,0])
    if i%10 != 9:
        g[i].append([(i+1)%k,1])
v = [100000]*k
v[1] = 1

def bfs(w,d):
    w_nexts = g[w]
    for w_next in w_nexts:
        if v[w_next[0]] <= d + w_next[1] or d + w_next[1] > 45:
            continue
        v[w_next[0]] = d + w_next[1]
        bfs(w_next[0],d + w_next[1])

bfs(1,1)
print(v[0])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<int>;
const int maxn = 46, mlg = 18, rt = 1<<10, mod = 1e9 + 7;
int dp[50][100003];
void mq(int &a, int b) {
	a = min(a, b);
}
int ok[100003], vis[100003];
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	memset(dp, 0x4f, sizeof dp);
	dp[0][0] = 0;
	int ans = 1<<30;
	for(int i = 0; i < 47; i++) {
		
		memset(ok, 0x4f, sizeof ok);
		memset(vis, 0, sizeof vis);
		for(int z = 0; z < n; z++) {
			if(vis[z]) continue;
			int g = z, mn = dp[i][g];
			vi t;
			while(!vis[g]) {
				vis[g] = 1;
				mq(mn, dp[i][g]);
				t.pb(g);
				g = g*10%n;
			}
			for(auto x : t) dp[i][x] = mn;
		}
		
		for(int r = 0; r < n; r++) {
			for(int d = i==0; d < 10; d++) {
				mq(dp[i+1][(r*10 + d)%n], dp[i][r] + d);
			}
		}
		if(i)
			ans = min(ans, dp[i][0]);
	}
	cout << ans;
}

Submission status: Runtime Error

Solution code:
def mizu(x):
    temp=0
    while x>0:
        temp+=x%10
        x//=10
    return temp 

def main():
    K=int(input())
    ans=10**9
    for i in range(1,10**8):
        ans=min(ans,mizu(i*k))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
ls = []
for i in range(1,200001):
  x = list(str(int(input())*i))
  y = 0
  for i in x:
    y += int(i)
  ls.append(y)
print(min(ls))

Submission status: Runtime Error

Solution code:
from collections import deque
readline = sys.stdin.readline

K = int(readline())

inf = 10**9+7
dist = [inf]*(K+1)
dist[K] = 0
Q = deque([K])
used = [False]*(K+1)
while Q:
    vn = Q.pop()
    if used[vn]:
        continue
    used[vn] = True
    vf = (vn*10)%K
    if vn%K and not used[vf]:
        dist[vf] = min(dist[vf], dist[vn])
        Q.append(vf)
    vf = (vn+1)%K
    if not used[(vn+1)%K]:
        dist[vf] = min(dist[vf], 1+dist[vn])
        Q.appendleft(vf)
print(dist[0])

Submission status: Runtime Error

Solution code:
K = input()
while K%2==0:
    K /= 2
while K%5==0:
    K /= 5

T = [[0]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        T[i][i*j%10] = j

memo = [-1]*100000
def f(x):
    if x==0:
        return 0
    if memo[x]>=0:
        return x
    if memo[x]==-2:
        return 999999
    memo[x] = -2
    ans = sum(map(int, str(x)))
    for i in range(10):
        for j in range(10):
            if (j*K+x)%10==i:
                ans = min(ans, i+f((j*K+x)/10))
    memo[x] = ans
    return ans
print f(K)

Submission status: Runtime Error

Solution code:
import random
random.seed(1024)

K = int(input())
ans = 0

K_copy = K
while K_copy > 0:
    ans += K_copy % 10
    K_copy //= 10

maxi = int('1' * ans)
maxi //= K

for _ in range(10 ** 4):
    j = random.randint(1, maxi)
    M = K * j
    m = 0
    while M > 0:
        m += M % 10
        M //= 10
    ans = min(ans, m)

print(ans)