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

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

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

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

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

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

Solution (Python):
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 = [] 
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: 
        if costs[n]>c+costs[now]: 
            costs[n]=c+costs[now]
            heapq.heappush(que,(c,n))
            
print(costs[0])

Solution (Python):
from collections import deque


def foo(k):
    q = deque([(1, 0)])
    nodes = {} 
    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)

Solution (Python):

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

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

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

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

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

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

Solution (Python):
from collections import deque

K = int(input())
d = [-1] * K
Q = [0] * (K + 1)
p = 0 
q = 0 
d[1] = 1
Q[q] = 1
q += 1

while q - p > 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
    
    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])

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

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

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

Solution (Python):

import sys
import heapq
K=input()


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





Start=1


d=[-1 for i in range(K)]
d[Start]=0




q=[]
heapq.heappush(q, [0,Start])



while len(q)!=0:
	
	l,u=heapq.heappop(q)
	for val in a[u]:
		v=val[0]
		l_u_v=val[1]
		
		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 d[0]+1

Solution (Python):


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

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

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

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