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:
import sys
from collections import deque

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

K = int(input())

# ある数に 1 を足すと各桁の和は 1 増える
# ある数に 10 を掛けると各桁の和は 0 増える
# mod K の世界で同じことやっても同じなので
# このグラフ上で 1 から 0 への最短距離が答え。

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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

K = int(input())

# ある数に 1 を足すと各桁の和は 1 増える
# ある数に 10 を掛けると各桁の和は 0 増える
# mod K の世界で同じことやっても同じなので
# このグラフ上で 1 から 0 への最短距離が答え。

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

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

Submission status: Accepted

Solution code:
k = int(input())

import heapq
INF = 10**9

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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


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

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

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

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

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


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

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

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

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


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

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

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import itertools
from scipy.sparse import coo_matrix, lil_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford, floyd_warshall
#sys.setrecursionlimit(10000)

#H, W = [int(i) for i in input().split()]
N = int(input())

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

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

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

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

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
#graph = coo_matrix((weights, (cols, rows)), shape=(10, 10)).tocsr()
#print(graph)
d1 = dijkstra(graph, indices=1, directed=True, unweighted=False)

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

Submission status: Accepted

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

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


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

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

print(dist[0])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
d = deque()
mat = []
for i in range(k):
    mat.append([])
#mark = [False]*k
dis = [10**18]*k
dis[1] = 0
for i in range(k):
    mat[i].append(((i+1)%k,True))

    if (10*i)%k != i:
        mat[i].append(((10*i)%k,False))

#bfs 1->0
d.append(1)
res = 0
while d:
    left = d.popleft()
    for neighbour,edge in mat[left]:
        distance = edge + dis[left]
        if dis[neighbour] > distance: 
            dis[neighbour] = distance 
            
            if edge == 0:
                d.appendleft(neighbour)
            else:
                d.append(neighbour)
print(dis[0]+1)

Submission status: Accepted

Solution code:
from collections import deque


def solve(K):
    s = 1
    q = deque()
    q.append(s)
    dists = {}
    dists[s] = 1
    while len(q) > 0:
        n = q.pop()
        if n == 0:
            break
        m = (n*10)%K
        if m not in dists:
            dists[m] = dists[n]
            q.append(m)
        elif dists[m] > dists[n]:
            dists[m] = dists[n]
            q.append(m)
        if n % 10 != 9:
            m = (n+1)%K
            if m not in dists:
                dists[m] = dists[n] + 1
                q.appendleft(m)
            elif dists[m] > dists[n] + 1:
                dists[m] = dists[n] + 1
                q.appendleft(m)
    return dists[0]


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue


def bfs01(s: int, t: int, V: int, graph: list)->int:
    '''01-bfs
    :param s: source
    :param t: sink
    :param V: number of vertex
    :param graph: graph
    :return: minimum distance from `s` to `t`
    '''
    INF = float('inf')

    # deque と s から各頂点への距離を初期化する。
    q = queue.deque([])  # deque
    qc = 0               # 毎度 len(q) を回すと時間かかりそうなので変数で管理
    l = [INF] * V        # s から各頂点への距離

    # s に関する初期化
    q.append(s)
    qc += 1
    l[s] = 0

    # deque に頂点が存在する限り次を繰り返す。
    # 1. deque の先頭から頂点を取り出す。
    # 2. 取り出した頂点に隣接する全ての頂点に対して以下を行う。
    # 2-a. 距離が更新されるなら更新する。加えて辺の長さが 0 なら
    #      先頭に、1 なら末尾に追加する。
    while qc > 0:
        u = q.popleft()
        qc -= 1
        for v, c in graph[u]:
            if l[u] + c < l[v]:
                l[v] = l[u] + c
                qc += 1
                if c == 0:
                    q.appendleft(v)
                else:
                    q.append(v)

    return l[t]


def small_multiple(K: int)->int:
    graph = []
    for k in range(K):
        # k -> k+1 に 1 の辺を、k -> 10*k に 0 の辺を張る。
        # ただし、どちらも mod K をとって k と等しくない場合のみ
        graph.append([])
        v1 = k+1 if k+1 < K else 0
        v10 = (k*10) % K

        graph[k].append((v1, 1))
        if v10 != k:
            graph[k].append((v10, 0))

    return bfs01(1, 0, K, graph) + 1


if __name__ == "__main__":
    K = int(input())
    ans = small_multiple(K)
    print(ans)

Submission status: Accepted

Solution code:
import queue


def bfs01(s: int, t: int, V: int, graph: list)->int:
    INF = float('inf')

    q = queue.deque([])
    qc = 0
    l = [INF] * V

    q.append(s)
    qc += 1
    l[s] = 0

    while qc > 0:
        u = q.popleft()
        qc -= 1
        for v, c in graph[u]:
            if l[u] + c < l[v]:
                l[v] = l[u] + c
                qc += 1
                if c == 0:
                    q.appendleft(v)
                else:
                    q.append(v)

    return l[t]


def small_multiple(K: int)->int:
    graph = []
    for k in range(K):
        graph.append([])
        v1 = k+1 if k+1 < K else 0
        v10 = (k*10) % K

        graph[k].append((v1, 1))
        if v10 != k:
            graph[k].append((v10, 0))

    return bfs01(1, 0, K, graph) + 1


if __name__ == "__main__":
    K = int(input())
    ans = small_multiple(K)
    print(ans)

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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    s = S()
    t = S()
    if s+t == t[::-1]+s[::-1]:
        print("YES")
    else:
        print("NO")

#B
def B():
    n = I()
    for i in range(int(n**0.5)+2)[::-1]:
        if i*i <= n:
            print(i*i)
            quit()
#C
def C():
    n = I()
    a = LI()
    b = LI()
    c = LI()
    q = [0 for i in range(n)]
    ans = 0
    a.sort()
    b.sort()
    c.sort()
    for i in range(n):
        j = bisect.bisect_left(a,b[i])
        q[i] = j
    for i in range(n-1):
        q[i+1] += q[i]
    q.insert(0,0)
    for i in range(n):
        j = bisect.bisect_left(b,c[i])
        ans += q[j]
    print(ans)
#D
def D():
    def dijkstra():
        d = [float("inf") for i in range(k)]
        q = [[0,1]]
        d[1] = 0
        while q:
            dx,x = heappop(q)
            for y,dy in v[x]:
                if d[y] > dx+dy:
                    d[y] = dx+dy
                    heappush(q,[d[y],y])
        print(d[0]+1)
    k = I()
    if k == 1:
        print(1)
        quit()
    v = [[] for i in range(k)]
    for i in range(1,k):
        v[i].append([(i+1)%k,1])
        v[i].append([i*10%k,0])
    dijkstra()
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

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

if(K == 1):print("1")
else : 
    visited = [-1 for i in range(K)]
    queue = deque([])
    st = 1

    while True:
        visited[st] = 1
        queue.append(st)
        st = (10*st) % K
        if (st == 1) : break

    while queue:
        a = queue.popleft()
        if (visited[0] != -1) :break
        if (visited[(a+1) % K] == -1):
            st = (a+1) % K
            while True:
                visited[st] = visited[a] + 1
                queue.append(st)
                st = (10*st) % K
                if (st == ((a+1) % K)) : break
            if (visited[0] != -1) :break


    print(visited[0])

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
dist=[float('inf') for _ in range(k)]
dist[1]=1
q=deque()
q.append(1)
while len(q)>0:
    r=q.popleft()
    s=(r+1)%k
    if dist[r]+1<dist[s]:
        dist[s]=dist[r]+1
        q.append(s)
    t=(r*10)%k
    if dist[r]<dist[t]:
        dist[t]=dist[r]
        q.appendleft(t)
print(dist[0])

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())
dist=[10**15 for i in range(K)]
dist[1]=1
q=deque([1])
while(len(q)>0):
    r=q.popleft()
    s=(r+1)%K
    if dist[r]+1<dist[s]:
        dist[s]=dist[r]+1
        q.append(s)
    t=(r*10)%K
    if dist[r]<dist[t]:
        dist[t]=dist[r]
        q.appendleft(t)
print(dist[0])

Submission status: Accepted

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

import collections

n = int(input())

cursor = 1
deque = collections.deque([(cursor, 0)])
visited = {cursor}

min_path = 10e10
while len(deque) > 0:
    cursor, min_path = deque.popleft()
    visited.add(cursor)
    if cursor == 0:
        break

    pone, mten = (cursor + 1) % n, (cursor * 10) % n
    if not pone in visited:
        deque.append((pone, min_path + 1))
    if not mten in visited:
        deque.appendleft((mten, min_path))

print(min_path + 1)

Submission status: Accepted

Solution code:
import heapq
K=int(input())
dist=[10**15 for i in range(K)]
dist[1]=1
q=[]
heapq.heappush(q,(0,1))
while (len(q)!=0):
    prc,src=heapq.heappop(q)
    if dist[src]<prc:
        continue
    if dist[(src+1)%K]>dist[src]+1:
        dist[(src+1)%K]=dist[src]+1
        heapq.heappush(q,(dist[(src+1)%K],(src+1)%K))
    if dist[(10*src)%K]>dist[src]:
        dist[(10*src)%K]=dist[src]
        heapq.heappush(q,(dist[(src*10)%K],(src*10)%K))
print(dist[0])

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
k = int(input())

dist = []
for i in range(k):
    if i != k - 1:
        dist.append([i, i + 1, 1])
    else:
        dist.append([i, 0, 1])

for i in range(k):
    dist.append([i, (10 * i) % k, 0])

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

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

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

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

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


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

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

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

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

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    #g.add_edge(dst, src, weight)
spdi = {}

d = Dijkstra(g, 1)
sp = format(d.shortest_distance(0))
print(int(sp) + 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(((10 * i) % K, 0))
    G[i].append(((i + 1) % K, 1))

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

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

print(dist[0])

Submission status: Accepted

Solution code:
from collections import deque
q=deque();K=int(input());q+=[(1,1)];m={}
while len(q):
 n,s=q.pop()
 if not n in m:m[n]=s;q+=[(n*10%K,s)];q.appendleft(((n+1)%K,s+1))
print(m[0])

Submission status: Accepted

Solution code:
from collections import deque
q=deque();K=int(input());a=q.append;a((1,1));m={}
while len(q):
 n,s=q.popleft()
 if not n in m:m[n]=s;q.appendleft((n*10%K,s));a(((n+1)%K,s+1))
print(m[0])

Submission status: Accepted

Solution code:
from collections import deque
q=deque()
K=int(input())
a=q.append
a((1,1))
m={}
while len(q):
 n,s=q.popleft()
 if n in m:continue
 m[n]=s
 q.appendleft((n*10%K,s))
 a(((n+1)%K,s+1))
print(m[0])

Submission status: Accepted

Solution code:
from collections import deque
q = deque()
K = int(input())
q.append((1, 1))
m = {}
while len(q):
 n, s = q.popleft()
 if n in m:continue
 m[n] = s
 q.appendleft((n * 10 % K, s))
 q.append(((n + 1) % K, s + 1))
print(m[0])

Submission status: Accepted

Solution code:
from collections import deque

que = deque()

K = int(input())

que.append((1, 1))
visited = {}

while len(que) != 0:
    num, step = que.popleft()
    if num in visited:
        continue
    visited[num] = step
    que.appendleft((num * 10 % K, step))
    que.append(((num + 1) % K, step + 1))

print(visited[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
K = int(input())
G = [[] for i in range(K)]

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

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

while que:
    node, cost = que.pop()
    dist[node] = min(cost, dist[node])
    for e, e_cost in G[node]:
        if dist[e] != float('inf'):
            continue

        if e_cost == 0:
            que.append([e, cost + 0])

        if e_cost == 1:
            que.appendleft([e, cost + 1])

print(dist[0])

Submission status: Accepted

Solution code:
import heapq
from collections import deque
K = int(input())
G = [[] for i in range(K)]

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


def dijkstra(x):
    d = [float('inf')] * K
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


print(dijkstra(1)[0] + 1)

Submission status: Accepted

Solution code:
k = int(input())

INF = 10 ** 6

d = [INF for _ in range(k)]

d[1] = 1
temp = [[1,1]]
while 1:
    next = []
    for p, c in temp:
        if c + 1 < d[(p + 1) % k]:
            d[(p + 1) % k] = c + 1
            next.append([(p + 1) % k, c + 1])
        if c < d[(p * 10) % k]:
            d[(p * 10) % k] = c
            next.append([(p * 10) % k, c])
    if len(next) == 0:
        break
    else:
        temp = [] + next

print(d[0])

Submission status: Accepted

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

from collections import deque

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

kmod = [0]*k

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

Submission status: Accepted

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

from collections import deque

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

kmod = [0]*k

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

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

visited = [False]*(k+1)
dist = [0]*(k+1)
dist[1] = 1
que = deque([(1, 1)])

while len(que) > 0:
    cost, node = que.popleft()
    if visited[node]:
        continue
    
    visited[node] = True
    dist[node] = cost

    if not visited[10*node%k]:
        que.appendleft((cost, 10*node%k))
    if not visited[(node+1)%k]:
        que.append((cost+1, (node+1)%k))

print(dist[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 heapq import heappop, heappush
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    K = int(input())
    dp = [INF] * K
    dp[1] = 1

    heap = []
    heappush(heap, (1, 1))

    while len(heap) != 0:
        k, p = heappop(heap)
        if dp[(p + 1) % K] > dp[p] + 1:
            dp[(p + 1) % K] = dp[p] + 1
            heappush(heap, (dp[p] + 1, (p + 1) % K))
        if dp[(p * 10) % K] > dp[p]:
            dp[(p * 10) % K] = dp[p]
            heappush(heap, (dp[p], (p * 10) % K))

        if dp[0] != INF:
            break

    print(dp[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


class Graph(object):

    def __init__(self, K):
        self.K = K
        self.weights = {}

    def add(self, node1, node2, weight):
        if (node1, node2) in self.weights:
            self.weights[(node1, node2)] = min(self.weights[(node1, node2)], weight)
        else:
            self.weights[(node1, node2)] = weight

    def to_csr(self):
        n1, n2, w = [], [], []
        for (node1, node2), weight in self.weights.items():
            n1.append(node1)
            n2.append(node2)
            w.append(weight)
        return csr_matrix((w, (n1, n2)), shape=(self.K, self.K))


K = int(input())
g = Graph(K)

for i in range(K):
    if i == K - 1:
        g.add(i, 0, 1)
    else:
        g.add(i, i + 1, 1)
    g.add(i, (i * 10) % K, 10**(-8))

d = dijkstra(g.to_csr(), directed=True, indices=1)
print(int(d[0]) + 1)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
x = [50 for i in range(k)]
x[1],q = 0,deque()
q.append(1)
while q:
	n = q.pop()
	m = n	
	while 1:
		m2 = (m*10)%k
		if x[m2]>x[m]:
			x[m2],m = x[m],m2
			q.append(m)
		else: break
	if x[(n+1)%k]==50:
		x[(n+1)%k] = x[n]+1
		q.appendleft((n+1)%k)
print(x[0]+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

K = int(input())


lines = defaultdict(set)
for i in range(K-1):
	lines[i].add((i+1,1))
lines[K-1].add((0,1))

for s in range(K):
	t = s*10 % K
	if s != t:
		lines[s].add((t,0))

def search (s,w_0): #s->t
	global weight
	global q

	for line in list(lines[s]):
		t = line[0]
		w = w_0 + line[1]
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w

s = 1
weight = [INF]*K
weight[s] = 0
q = [[0,s]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

print(weight[0]+1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(K:int) -> list:
    hasChecked = [False]*(K+1)
    cost_list = [0]*(K+1)
    cost_list[1] = 1
    
    que = deque([(cost_list[1], 1)])
    
    while que:
        cost, res = que.popleft()
        if hasChecked[res]:
            continue
        
        hasChecked[res] = True
        cost_list[res] = cost
        
        if not hasChecked[10*res%K]:
            que.appendleft((cost, 10*res%K))
            
        if not hasChecked[(res+1)%K]:
            que.append((cost+1, (res+1)%K))
            
            
    return cost_list


K = int(input())
cost_list = bfs(K)
print(cost_list[0])

Submission status: Accepted

Solution code:
K = int(input())

import heapq
def dijkstra(adj, n, start):
    dj = [10**6] * (n + 1)
    dj[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[tn] > dj[fn] + lc:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = {}
for i in range(K):
    t = adj.setdefault(i, [])
    t.append(((i + 1) % K, 1))
    t.append(((i * 10) % K, 0))

costs = dijkstra(adj, K - 1, 1)
print(costs[0] + 1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra, shortest_path
from scipy.sparse import csr_matrix
K = int(input())

class Graph(object):

    def __init__(self, K):
        self.K = K
        self.weights = {}

    def add_edge(self, node1, node2, weight):
        if (node1, node2) in self.weights:
            self.weights[(node1, node2)] = min(self.weights[(node1, node2)], weight)
        else:
            self.weights[(node1, node2)] = weight

    def get_csr_matrix(self):
        n1, n2, w = [], [], []
        for (node1, node2), weight in self.weights.items():
            n1.append(node1)
            n2.append(node2)
            w.append(weight)
        return csr_matrix((w, (n1, n2)), shape=(self.K, self.K))

g = Graph(K)

for i in range(K - 1):
    g.add_edge(i, i + 1, 1)
    g.add_edge(i, (i * 10) % K, 10**(-16))

g.add_edge(K - 1, 0, 1)
g.add_edge(K - 1, ((K - 1) * 10) % K, 10**(-16))
d = dijkstra(g.get_csr_matrix(), directed=True, indices=1)
print(int(d[0]) + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

K = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

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

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

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


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

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

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

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

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
for i in range(K - 1):
    g.add_edge(i, i + 1, 1)
    g.add_edge(i, (i * 10) % K, 0)
g.add_edge(K - 1, 0, 1)
g.add_edge(K - 1, ((K - 1) * 10) % K, 0)

d = Dijkstra(g, 1)
print(d.shortest_distance(0) + 1)