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: Time Limit Exceeded

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


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 spfa(s):
    dis[s] = 0
    q.put(s)
    while not q.empty():
        x = q.get()
        vis[x] = False
        for e in edge[x]:
            if dis[e.dst] > dis[x] + e.len:
                dis[e.dst] = dis[x] + e.len
                if not vis[e.dst]:
                    q.put(e.dst)
                    vis[e.dst] = True


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

Submission status: Time Limit Exceeded

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)]
        qi = 0
        v = collections.defaultdict(bool)
        v[s] = True
        while len(q):
            k, u = q[0]
            q = q[1:]
            if u == 0:
                return k
            t = u*10 % K
            while not v[t]:
                q.append((k, t))
                v[t] = True
                t = t*10 % K

            i = 1
            t = (u+i) % K
            while not v[t]:
                q.append((k+1, t))
                v[t] = True
                i = i*10 % K
                t = u+i % K

    return search(1)

print(main())

Submission status: Time Limit Exceeded

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

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 = set()
    x = sumOfDigits(n)

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

    while len(qs) > 0:
        q = qs.pop()
        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
                qs.add(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: Time Limit Exceeded

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

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

    a = {}
    qs = set()
    x = sumOfDigits(n)

    for i in range(1, min(n, 10)):
        a[i] = i
        qs.add(i)

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

            if not q3 in a or v2 < a[q3]:
                a[q3] = v2
                qs.add(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: Time Limit Exceeded

Solution code:
n = int(input())
mn = 10000
for x in range(2,1000000):
    ne = n*x
    ne = str(ne)
    su = 0
    for y in ne:
        su += int(y)
    mn = min(mn,su)
print(mn)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

V=int(input())


s=V*np.arange(1,int(10**6))
res=list(map(lambda x:sum(list(map(int,str(x)))),s))
#plt.plot(res)
ans=min(res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np

V=int(input())


s=V*np.arange(1,int(10**7))
res=list(map(lambda x:sum(list(map(int,str(x)))),s))
#plt.plot(res)
ans=min(res)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def dijkstra(edge, start, end):
    """
    Create distance(cost) table for all nodes.
    :param edge: List of tuple(to, cost)
    :param start: start node
    :param end: end node
    :return: minimum cost from start to end
    """
    h = [(0, start)]
    used = [False] * len(edge)

    while h:
        cost, node = heappop(h)
        if used[node]:
            continue
        used[node] = True

        if node == end:
            return cost

        for i, c in edge[node]:
            heappush(h, (cost + c, i))

    return -1


K = int(input())

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

k, = map(int, readline().split())

from collections import deque
INF = 1<<30
res = [INF]*k
res[1] = 1

q = deque([(1,1)])
while q:
    dv,v = q.popleft()
    if res[v] < dv: continue
    #if v==goal: break
    for to,cost in [(10*v%k,0),((v+1)%k,1)]:
        #print(to,cost)
        if dv + cost < res[to]:
            res[to] = dv + cost
            if cost: q.append((res[to],to))
            else: q.appendleft((res[to],to))
    #print(res)
    
print(res[0])

Submission status: Accepted

Solution code:
from collections import *
K=int(input())
D=[K+1]*K
D[1]=1
Q=deque([1])
def bfs():
  global Q,D,K
  v=0
  while len(Q):
    v=Q.popleft()
    if D[v*10%K]>D[v]:
      D[v*10%K]=D[v]
      Q.appendleft(v*10%K)
    if D[(v+1)%K]>D[v]+1:
      D[(v+1)%K]=D[v]+1
      Q.append((v+1)%K)

bfs()
print(D[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, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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 = 10 ** 9 + 7

k = I()
q = deque([1])
cost = [INF] * k
cost[1] = 1
while q:
    u = q.popleft()
    if cost[u * 10 % k] > cost[u]:
        cost[u * 10 % k] = cost[u]
        q.appendleft(u * 10 % k)
    if cost[(u + 1) % k] > cost[u] + 1:
        cost[(u + 1) % k] = cost[u] + 1
        q += [(u + 1) % k]


print(cost[0])

Submission status: Accepted

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 draw(d):
    for i in range(k):
        if v[i] > d:
            continue
        for v_next in g[i]:
            if v[i] == d and v_next[1] == 0 and v[v_next[0]] > d:
                v_n = v_next[0]
                while v[v_n] > d:
                    v[v_n] = d
                    v_n = v_n*10%k
            elif v[i] == d-1 and v_next[1] == 1 and v[v_next[0]] > d:
                v_n = v_next[0]
                while v[v_n] > d:
                    v[v_n] = d
                    v_n = v_n*10%k
            
for i in range(1,46):
    draw(i)
    if v[0] == i:
        print(v[0])
        exit()

Submission status: Accepted

Solution code:
import heapq

K = int(input())
D = [9999]*K
D[1] = 1
H = [(1,1)]
while len(H) != 0:
    c,h = heapq.heappop(H)
    if D[(h*10)%K] > c:
        D[(h*10)%K] = c
        H.append((c,(h*10)%K))
    if D[(h+1)%K] > c + 1:
        D[(h+1)%K] = c + 1
        H.append((c+1,(h+1)%K))

print(D[0])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
D = [9999]*K
D[1] = 1
H = deque()
H.append(1)
while len(H) != 0:
    h = H.pop()
    if D[(h*10)%K] > D[h]:
        D[(h*10)%K] = D[h]
        H.append((h*10)%K)
    if D[(h+1)%K] > D[h] + 1:
        D[(h+1)%K] = D[h] + 1
        H.appendleft((h+1)%K)

print(D[0])

Submission status: Accepted

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

K=int(input())
pro=Dijkstra(K)
for i in range(0,K):
    pro.add(i,(i+1)%K,1)
    pro.add(i,(10*i)%K,0)

ans=pro.shortest_path(1)[0]
print(ans+1)

Submission status: Accepted

Solution code:
#!python3

from collections import deque


# input
K = int(input())


def solve():
    visit = [False] * K
    # (s, num)
    dq = deque([(0, 1)])
    while dq:
        s, num = dq.popleft()
        visit[num] = True
        if num == 0:
            return s
        a = num * 10 % K
        if not visit[a]:
            dq.appendleft((s, a))
        b = (num + 1) % K
        if not visit[b]:
            dq.append((s + 1, b))
    
    assert False


def main():
    ans = solve() + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
k=int(input())
g=[[] for i in range(k)]
for i in range(k):
  g[i].append(((i+1)%k,1))
  if i:
    g[i].append((10*i%k,0))
q=deque([1])
res=[float('inf')]*k
res[1]=1
while q:
  v=q.popleft()
  if v==0:
    break
  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])

Submission status: Accepted

Solution code:
import sys
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: Accepted

Solution code:
from collections import deque

k = int(input())
seen = [False]*k
dq = deque()
dq.append((1, 1))
ans = 0
while dq:
  v, s = dq.popleft()
  if seen[v]:
    continue
  seen[v] = True
  if v == 0:
    ans = s
    break
  nv1, nv2 = (v*10)%k, (v+1)%k
  dq.appendleft((nv1, s))
  dq.append((nv2, s+1))
print(ans)

Submission status: Accepted

Solution code:
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    k = int(input())
    dist = [-1] * k
    q = deque()
    q.append([1, 1])
    while q:
        d, u = q.popleft()
        if dist[u] != -1: continue
        dist[u] = d
        if u == 0:
            print(d)
            break
        v = (u + 1) % k
        if dist[v] == -1: q.append([d + 1, v])
        v = (u * 10) % k
        if dist[v] == -1: q.appendleft([d, v])

main()

Submission status: Accepted

Solution code:
import heapq


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = float("inf")
    n = len(graph)
    distance = [INF] * n
    distance[start] = 0
    q = [(0, start)]  #q = [(startからの距離, 現在地)]
    while q:
        dist, pos = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                heapq.heappush(q, (distance[next_pos], next_pos))
    return distance
  

k = int(input())
MOD = k
INF = 10**9

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.buffer.readline
N = int(input())
e = dd(list)
for i in range(1, N):
  n1 = 10 * i
  n2 = i + 1
  e[i].append((n1 % N, 0))
  e[i].append((n2 % N, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]
d = dijkstra(N, e)
print(d.path(1, 0) + 1)

Submission status: Accepted

Solution code:
from heapq import *
from collections import deque

intinf = 10 ** 15

def bfs_01(n, graph, start):
    min_distance = [intinf] * n

    deq = deque()
    min_distance[start] = 0
    deq.append(start)

    while deq:
        src = deq.popleft()
        for dst, cost in graph[src]:
            next_d = min_distance[src] + cost
            if min_distance[dst] <= next_d:
                continue

            min_distance[dst] = next_d
            if cost == 0:
                deq.appendleft(dst)
            elif cost == 1:
                deq.append(dst)
            else:
                print('invalid cost in graph')
                raise ValueError

    return min_distance

def dijkstra(n, graph, start):
    min_distance = [intinf] * n

    # min-heap of (distance, vertex)
    heap = []

    heappush(heap, (0, start))
    min_distance[start] = 0

    while heap != []:
        d, src = heappop(heap)
        if min_distance[src] < d:
            continue
        for dst, cost in graph[src]:
            next_d = d + cost
            if next_d < min_distance[dst]:
                min_distance[dst] = next_d
                heappush(heap, (next_d, dst))

    return min_distance

def main():
    K = int(input())

    # (v, c) in graph[u] <=> u -> v with cost = c
    graph = [[] for _ in range(K)]

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

    # dist = dijkstra(K, graph, 1)
    dist = bfs_01(K, graph, 1)

    print(dist[0] + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
from collections import deque

intinf = 10 ** 15

def bfs_01(n, graph, start):
    min_distance = [intinf] * n

    deq = deque()
    min_distance[start] = 0
    deq.append(start)

    while deq:
        src = deq.popleft()
        for dst, cost in graph[src]:
            next_d = min_distance[src] + cost
            if min_distance[dst] <= next_d:
                continue

            min_distance[dst] = next_d
            if cost == 0:
                deq.appendleft(dst)
            elif cost == 1:
                deq.append(dst)
            else:
                print('invalid cost in graph')
                raise ValueError

    return min_distance

def dijkstra(n, graph, start):
    min_distance = [intinf] * n

    # min-heap of (distance, vertex)
    heap = []

    heappush(heap, (0, start))
    min_distance[start] = 0

    while heap != []:
        d, src = heappop(heap)
        if min_distance[src] < d:
            continue
        for dst, cost in graph[src]:
            next_d = d + cost
            if next_d < min_distance[dst]:
                min_distance[dst] = next_d
                heappush(heap, (next_d, dst))

    return min_distance

def main():
    K = int(input())

    # (v, c) in graph[u] <=> u -> v with cost = c
    graph = [[] for _ in range(K)]

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

    dist = dijkstra(K, graph, 1)
    # dist = bfs_01(K, graph, 1)

    print(dist[0] + 1)

if __name__ == '__main__':
    main()

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,1)])
res = [float("inf")]*k
res[1] = 1
while q:
    dd,v = q.popleft()
    if res[v] < dd: continue
    if v==0: break
    for c,d in g[v]:
        if res[c] <= res[v] + d: continue
        res[c] = res[v] + d
        if d: q.append((res[c],c))
        else: q.appendleft((res[c],c))

print(res[0])

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])
res = [float("inf")]*k
res[1] = 1
while q:
    v = q.popleft()
    if v==0: break
    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])

Submission status: Accepted

Solution code:
import heapq as hq

k =int(input())
inf = float("inf")
dist = [inf for _ in range(k)]
dist[1]=1
start =1
q =[(1,1)]

while q:
    keta,nowmod = hq.heappop(q)
    if dist[(nowmod*10)%k]>keta:
        dist[(nowmod*10)%k]=keta
        hq.heappush(q,(keta,(nowmod*10)%k))
    if dist[(nowmod+1)%k]>keta+1:
        dist[(nowmod+1)%k]=keta+1
        hq.heappush(q,(keta+1,(nowmod+1)%k))

print(dist[0])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
G = [-1 for k in range(K)]

Q = deque()
Q.append([1,1])
while len(Q) > 0:
    p = Q.popleft()
    x, d = p[0], p[1]
    if G[x] == -1:
        G[x] = d
        Q.append([(x+1)%K,d+1])
        Q.appendleft([(x*10)%K,d])

print(G[0])

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  k=int(input())
  e=[[]for _ in range(k)]
  for i in range(k):
    e[i].extend([(i*10%k,0),(-~i%k,1)])
  q=deque([1])
  p,l,r=q.pop,q.appendleft,q.append
  f=[10**18]*k
  f[1]=1
  while q:
    v=p()
    for w,d in e[v]:
      c=f[v]+d
      if f[w]>c:
        (r,l)[d](w)
        f[w]=c
  print(f[0])
main()

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
D = [-1]*K
Q = deque()
Q.append([1,0])
while D[0] == -1:
    k,v = Q.popleft()
    D[k] = v
    j = (k*10)%K
    if D[j] == -1:
        Q.appendleft([j,v])
    l = (k+1)%K
    if D[l] == -1:
        Q.append([l,v+1])

print(D[0]+1)

Submission status: Accepted

Solution code:
k = int(input())
from collections import deque
dic = {1:1}
queue = deque()
queue.appendleft([1,1])
while queue:
    v,cost = queue.popleft()
    v_ = (v+1)%k
    if not v_ in dic or cost+1<dic[v_]:
        dic[v_] = cost+1
        queue.appendleft([v_,cost+1])
    v_ = v*10%k
    if not v_ in dic or cost<dic[v_]:
        dic[v_] = cost
        queue.append([v_,cost])

print(dic[0])

Submission status: Accepted

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: Accepted

Solution code:
k = int(input())
from collections import deque
dic = {1:1}
queue = deque([[1,1]])
while queue:
    v,cost = queue.popleft()
    v_ = (v+1)%k
    if not v_ in dic or cost+1<dic[v_]:
        dic[v_] = cost+1
        queue.appendleft([v_,cost+1])
    v_ = v*10%k
    if not v_ in dic or cost<dic[v_]:
        dic[v_] = cost
        queue.append([v_,cost])

print(dic[0])

Submission status: Accepted

Solution code:
k = int(input())
from collections import deque
dic = {1:1}
queue = deque([[1,1]])
while queue:
    v,cost = queue.popleft()
    if not (v+1)%k in dic or cost+1<dic[(v+1)%k]:
        dic[(v+1)%k] = cost+1
        queue.appendleft([(v+1)%k,cost+1])
    if not v*10%k in dic or cost<dic[v*10%k]:
        dic[v*10%k] = cost
        queue.append([v*10%k,cost])

print(dic[0])

Submission status: Accepted

Solution code:
from collections import deque
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
 
# 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:
# -*- coding: utf-8 -*-

import sys
from collections import deque

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
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

K=INT()

que=deque()
que.append((1, 1))
costs=[-1]*K

while len(que):
    cur,cost=que.popleft()
    if costs[cur]==-1:
        costs[cur]=cost
        que.appendleft((cur*10%K, cost))
        que.append(((cur+1)%K, cost+1))
print(costs[0])

Submission status: Accepted

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

cost = [None] * K
Q = deque()
Q.append((1, 1))
while Q:
    currentCost, currentNode = Q.popleft()
    if cost[currentNode] == None:
        cost[currentNode] = currentCost
        Q.append((currentCost + 1, (currentNode + 1) % K))
        Q.appendleft((currentCost, (currentNode * 10) % K))
print(cost[0])

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 collections import deque


def main():
    K = int(input())
    q = deque([(1, 1)])
    visited = [False] * K
    while len(q):
        n, s = q.popleft()
        if visited[n]:
            continue
        visited[n] = True
        if n == 0:
            print(s)
            return
        q.appendleft((n*10 % K, s))
        q.append(((n+1) % K, s+1))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input())
    q = deque([[1, 1]])
    d = {1: 1}
    while q:
        n, c = q.popleft()
        a = (n * 10) % N
        if a not in d or d[a] > c:
            d[a] = c
            q.appendleft([a, c])

        b = (n + 1) % N
        if b not in d or d[b] > c+1:
            d[b] = c + 1
            q.append([b, c+1])

    print(d[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
dis = [float("inf") for _ in range(k)]

def bfs(start, goal):
	que = deque([[start, 1]])
	while que:
		label = que.pop()
		l, c = label[0], label[1]
		if l == goal:
			return c
		if dis[l] > c:
			dis[l] = c
			que.append([(l*10)%k, c])
			que.appendleft([(l+1)%k, c+1])

print(bfs(1, 0))

Submission status: Accepted

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

def main():
    K = int(input())

    d = [100] * K
    d[1] = 1
    Q = []
    for i in range(45 + 1):
        Q.append([])
    Q[1].append(1)
    for i in range(1, 45 + 1):
        q = Q[i]
        while 0 < len(q):
            v = q.pop(0)
            nv = (v * 10) % K
            if i < d[nv]:
                d[nv] = i
                q.append(nv)
            nnv = (v + 1) % K
            if i + 1 < d[nnv]:
                d[nnv] = i + 1
                Q[i + 1].append(nnv)



    print(d[0])


if __name__ == '__main__':
    main()