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:
k=int(input())
lst = [k+1]*k
queue = [1]
lst[1] = 1
while queue:
    a = queue.pop(0)
    if lst[a*10%k] > lst[a]:
        lst[a*10%k] = lst[a]
        queue.insert(0,a*10%k)
    if lst[(a+1)%k]>= lst[a]+1:
        lst[(a+1)%k] = lst[a]+1
        queue.append((a+1)%k)
print(lst[0])

Submission status: Time Limit Exceeded

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

q = deque([1])
used = [False] * K
def cost(x):
    ret = 0
    while x:
        ret += x % 10
        x //= 10
    return ret

while True:
    x = q.popleft()
    if x % K == 0:
        print(cost(x))
        break
    elif used[x % K]:
        continue
    used[x % K] = True
    if (x+1) % 10 == 0:
        q.appendleft(x+1)
    else:
        q.append(x+1)
    q.appendleft(10*x)

Submission status: Time Limit Exceeded

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

q = deque([1])
used = [False] * K
def cost(x):
    ret = 0
    while x:
        ret += x % 10
        x //= 10
    return ret

while True:
    x = q.popleft()
    if x % K == 0:
        print(cost(x))
        break
    elif used[x % K]:
        continue
    used[x % K] = True
    q.appendleft(10*x)
    q.append(x+1)

Submission status: Time Limit Exceeded

Solution code:
#http://abc077.contest.atcoder.jp/
# -*- coding: utf-8 -*-

k = int(input())

def keta_sum(n):
    l = [int(x) for x in list(str(n))]
    return sum(l)

n_list = []
for i in range(1000000):
    a = keta_sum( k * (i+2) )
    if a not in n_list:
        n_list.append( a )

print( min(n_list) )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from sys import stdin, stdout
from bisect import bisect
def rint():
   return map(int, stdin.readline().split())

K = int(input())

ans = 10**100
for i in range(1,10**6):
   tmp = K*i
   tmps = str(tmp)
   tmp = 0
   for kk in tmps:
      tmp += int(kk)
   ans = min(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = input()


def get_sum(n):
    s = str(n)
    arr = list(map(int, list(s)))
    return sum(arr)

ans = get_sum(n)
i = 1
for i in range(1, 10000):
    m = get_sum(n * i)
    if ans > m:
        ans = m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
l = [x for x in list(str(a))]
keta = len(l)
list_ = []
#Bunkatsu
def Dround(a):
    for i in range(2,10**5):
        a = a * i
        l = [x for x in list(str(a))]
        answer = sum(map(int,l))
        list_.append(answer)
#        if answer >= s:
#            s = answer
#        else:
#            continue
    return list_
print(min(Dround(a)))

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    k = int(input())
    dist = [INF] * k
    dist[1] = 1
    queue = [1]

    for v in queue:
        tmp = [v]
        for v in tmp:
            if dist[10 * v % k] > dist[v]:
                dist[10 * v % k] = dist[v]
                tmp.append(10 * v % k)
            if dist[(v + 1) % k] > dist[v] + 1:
                dist[(v + 1) % k] = dist[v] + 1
                queue.append((v + 1) % k)

    print(dist[0])
resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    k = int(input())
    dist = [INF] * k
    dist[1] = 1
    queue = deque([1])

    while queue:
        v = queue.pop()
        if dist[10 * v % k] > dist[v]:
            dist[10 * v % k] = dist[v]
            queue.appendleft(10 * v % k)
        if dist[(v + 1) % k] > dist[v] + 1:
            dist[(v + 1) % k] = dist[v] + 1
            queue.append((v + 1) % k)

    print(dist[0])
resolve()

Submission status: Accepted

Solution code:
import heapq
k = int(input())
graph = [[] for i in range(k)]
for i in range(k):
    if i != k-1: graph[i].append((1, i+1))
    else: graph[i].append((1, 0))
    if (i * 10) % k != i: graph[i].append((0, (i * 10) % k))

que = []
heapq.heappush(que, (0, 1, 1)) #現在の頂点の始点からの距離,頂点の番号, 操作途中の数
dist = [1145141919] * k
dist[1] = 0

ans = 1145141919
while len(que) > 0:
    d, v, num = heapq.heappop(que)
    for cost, place in graph[v]:
        if place == 0:
            ans = min(ans, num + 1 if cost else num)
        if d + cost < dist[place]:
            dist[place] = d + cost
            heapq.heappush(que, (d + cost, place, (num + 1 if cost else num)))

print(ans)

Submission status: Accepted

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


INF=10**9
res=[INF]*(K)
res[1]=1
q=deque()
q.append(1)
while q:
    r=q.popleft()
    if r==0:
        break
    nr=(r+1)%K
    if res[r]<res[nr]:
        res[nr]=res[r]+1
        q.append(nr)
    nr=(10*r)%K
    if res[r]<res[nr]:
        res[nr]=res[r]
        q.appendleft(nr)
print(res[0])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
K = int(input())
q = deque()
q.append((1, 1))
visited = [False] * K
ans = 0
while True:
    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:
from collections import deque
k=int(input())
t=[1]*k
q=deque()
q.append((1,1))

while q:
  p,r=q.popleft()
  if p==0:
    print(r)
    break
  if t[p]:
    t[p]=0
    q.appendleft(((p*10)%k,r))
    q.append(((p+1)%k,r+1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(readline())
edges = [[] for _ in range(K)]
INF = 10 ** 31
dist = [INF]*K
for i in range(K):
    edges[i].append(((i+1)%K,1))
    j = 10*i % K
    if i != j:
        edges[i].append((j,0))

q = deque([1])
dist[1] = 0
while q:
    x = q.popleft()
    for y,c in edges[x]:
        d = dist[x] + c
        if d < dist[y]:
            dist[y] = d
            if c == 1:
                q.append(y)
            else:
                q.appendleft(y)
print(dist[0]+1)

Submission status: Accepted

Solution code:
k = int(input())

ones = set()
x = 1
while(not x in ones):
    ones.add(x)
    x = (x*10)%k

num = 1
mask = (1<<k) -1
for i in range(1,46):
    next = 0
    for j in ones:
        next |= (num<<j)
    num = (next&mask) | (next>>k)

    if(num%2==1):
        print(i)
        exit()

Submission status: Accepted

Solution code:
# 桁和最小の自然数は1
from collections import deque
k = int(input())
d = [k] * k
e = [[(0, i * 10 % k), (1, (i + 1) % k)] for i in range(k)]
dq = deque()
dq.append((1, 1))
while dq:
    c, v = dq.popleft()
    for v2nv, nv in e[v]:
        if v2nv == 0:
            if c < d[nv]:
                d[nv] = c
                dq.appendleft((d[nv], nv))
        else:
            if c + 1 < d[nv]:
                d[nv] = c + 1
                dq.append((d[nv], nv))
print(d[0])

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
k=int(input())
edge=[[]for _ in range(k)]
for i in range(1,k):
    edge[i].append(((i*10)%k,0))
    edge[i].append(((i+1)%k,1))
ans=dijkstra(1,k,edge)
print(ans[0]+1)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
d = [-1] * (k * 10)
d[0] = 0
q = deque([0])
ans = 100000000
while q:
    p = q.pop()
    x, r = p // 10, p % 10
    if r < 9:
        t = (x + 1) % k * 10 + r + 1
        if t // 10 == 0:
            ans = min(ans, d[p] + 1)
        elif d[t] == -1:
            q.appendleft(t)
            d[t] = d[p] + 1
    t = (x * 10) % k * 10
    if d[p] != 0 and t // 10 == 0:
        ans = min(ans, d[p])
    elif d[t] == -1:
        q.append(t)
        d[t] = d[p]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

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

# (辺の伸びる先, コスト)
G = [((10 * i % k, 0), ((i + 1) % k, 1)) for i in range(k)]
s = 1

# 01 - BFS
dist = [INF] * k
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = d + c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0] + 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    """
    「数字の桁数の和に関する問題としては初見はキツいが割と典型らしい」

    全ての整数は1から出発して次の操作のいずれかを組み合わせて表現できる：
        a. 1を加える（ただし一の位が9の時はこの操作は許さない）
        b. 10倍する
    なぜこのような分解をしたかというと、整数をこのように表現することで
        （各桁の和）=（a.の操作を行った回数）+ 1
    と言い換えることができるから。

    そこで頂点を数字、辺を上の操作に当ててBFSすることを考える。
    このままでは頂点数が無限だが、辺の張られ方はmod Kをとっても同様の構造が出てくる。
    そこで無限グラフをmod Kで圧縮して有限グラフに直した上で頂点1から頂点0に移動するための
    最小コストが答え。

    ここでa.の操作で9->10のような遷移は許さなかったが、求めるのは最小コストであって
    1から10にたどり着くにはa.を10回するよりb.を1回する方がコストが低いので、a.の操作を
    一の位が9の場合に許容したとしても最短経路長は変化しない。
    """
    K = int(input())
    repn = [[] for _ in range(K)]
    for i in range(K):
        repn[i].append(10**6 + (i + 1) % K)
        repn[i].append((i * 10) % K)
    q = deque([])
    cost = [0] * K
    cost[1] = 1
    for val in repn[1]:
        type, toward = val // 10**6, val % 10**6
        # コスト0の辺は即popされるようにキューの左に入れる
        if type == 0:
            q.appendleft(1 * 10**6 + toward)
        else:
            q.append(10**12 + 1 * 10**6 + toward)

    while q:
        x = q.popleft()
        type, x = x // 10**12, x % 10**12
        pre, now = x // 10**6, x % 10**6
        if cost[now] != 0: continue
        cost[now] = cost[pre] + type
        for val in repn[now]:
            type, toward = val // 10**6, val % 10**6
            if type == 0:
                q.appendleft(now * 10**6 + toward)
            else:
                q.append(10**12 + now * 10**6 + toward)

    print(cost[0])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

K = I()

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

# dijkstra

from heapq import heappush,heappop

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

print(d[0])

Submission status: Accepted

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

K = I()

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

from collections import deque

q = deque([1])
d = [100]*K
d[1] = 1
# 01-BFS
while q:
    n = q.pop()
    if n == 0:
        continue
    else:
        for a,b in Graph[n]:
            if d[a] > d[n]+b:
                d[a] = d[n]+b
                if b == 0:
                    q.append(a)
                else:
                    q.appendleft(a)

print(d[0])

Submission status: Accepted

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

def main():
    k=int(readline())
    v=list(range(k))
    inf=float('inf')
    dist=[inf]*k
    visited=[0]*k
    stack=deque([1])
    dist[1]=0
    while stack:
        v=stack.pop()
        if not visited[v]:
            nv0=10*v%k
            nv1=(v+1)%k
            if dist[nv0]>dist[v]:
                dist[nv0]=dist[v]
                stack.append(nv0)
            if dist[nv1]>dist[v]+1:
                dist[nv1]=dist[v]+1
                stack.appendleft(nv1)
            visited[v]=1
    print(dist[0]+1)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

k=int(input())
v=list(range(k))
stack=deque([1])
inf=float('inf')
visited=[0]*k
dist=[inf]*k
dist[1]=0
while stack:
  v=stack.pop()
  if not visited[v]:
    nv0=10*v%k
    nv1=(v+1)%k
    if dist[nv0]>dist[v]:
      dist[nv0]=dist[v]
      stack.append(nv0)
    if dist[nv1]>1+dist[v]:
      stack.appendleft(nv1)
      dist[nv1]=dist[v]+1
    visited[v]=1
print(dist[0]+1)

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())

visited=[False]*K
s=(1,1)

q = deque()
q.append(s)

while True:
  c = q.popleft()
  visited[c[0]] = True

  if c[0] == 0:
    print(c[1])
    exit()

  if not visited[(c[0] * 10) % K] and not visited[(c[0] * 10) % K]:
    q.appendleft(((c[0] * 10) % K, c[1]))

  if not visited[(c[0] + 1) % K] and not visited[(c[0] + 1) % K]:
    q.append(((c[0] + 1) % K, c[1] + 1))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
graph = [[] for i in range(N)]
for i in range(N):
  graph[i].append((1,(i+1)%N))
for i in range(N):
  graph[i].append((0,(i*10)%N))
  
  
def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    for c,v in graph[u]:
      if d[v] <= d[u] + c: continue
      d[v] = d[u] + c
      if c:
        q.append(v)
      else:
        q.appendleft(v)
  return d

d = bfs(graph,1)

print(d[0]+1)

Submission status: Accepted

Solution code:
import collections
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

K = int(input())


def ans():
    visited = [False] * K

    s = (1, 1)

    q = collections.deque()
    q.append(s)

    while True:
        c = q.popleft()
        visited[c[0]] = True

        if c[0] == 0:
            return c[1]

        if not visited[(c[0] * 10) % K] and not visited[(c[0] * 10) % K]:
            q.appendleft(((c[0] * 10) % K, c[1]))

        if not visited[(c[0] + 1) % K] and not visited[(c[0] + 1) % K]:
            q.append(((c[0] + 1) % K, c[1] + 1))


print(ans())

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


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

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


k = int(input())

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

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

Submission status: Accepted

Solution code:
K = int(input())
import collections
d = [float('inf')]*(K)
d[1] = 1
path = [[] for _ in range(K)]
for i in range(K-1):
    path[i].append((i+1,1))

path[-1].append((0,1))
for i in range(K):
    path[i].append(((i*10)%K,0))
deque = collections.deque([1])
while deque:
    s = deque.popleft()
    for e,cost in path[s]:
        if d[s] + cost < d[e]:
            d[e] = d[s]+cost
            if cost ==0: deque.appendleft(e)
            else: deque.append(e)
print(d[0])
#1から10倍（コスト0）か1足す（コスト1）で任意の整数を作成可能
#上記を満たすグラフを考えれば題意とイコール
#1から0への最小経路こそが各桁の最小和

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
def bfs01(K,adjlist):
    reached=[False]*K
    d=deque()
    d.append((1,0))
    reached[1]=True
    while True:
        cur=d.popleft()
        reached[cur[0]]=True
        if cur[0]==0:
            return cur[1]
        for j,w in adjlist[cur[0]]:
            if w==0:
                if not reached[j]:
                    d.appendleft((j,cur[1]))
            elif w==1:
                if not reached[j]:
                    d.append((j,cur[1]+1))
                
    

K=int(input())
adjlist=[[] for _ in range(K)]
for i in range(K):
    to1=(i+1)%K
    to2=(10*i)%K
    if to1==to2:
        adjlist[i]=[(to2,0)]
    else:
        adjlist[i]=[(to1,1),(to2,0)]
print(bfs01(K,adjlist)+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  k = ni()
  q = deque()
  q.append(1)
  dist = [k]*k
  dist[1] = 1
  while q:
    v = q.popleft()
    if dist[(v + 1) % k] > dist[v] + 1:
      dist[(v + 1) % k] = dist[v] + 1
      q.append((v + 1) % k)
    if dist[v*10%k] > dist[v]:
      dist[v*10%k] = dist[v]
      q.appendleft(v*10%k)
  print(dist[0])
  return

solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    K = II()

    q = deque([(1, 1)])
    used = [0 for _ in range(K)]
    while len(q) > 0:
        # print(q)
        v, cost = q.popleft()
        if v == 0:
            print(cost)
            return

        if used[v]:
            continue
        used[v] = 1

        q.appendleft(((v*10) % K, cost))
        q.append(((v+1) % K, cost+1))



if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

d = [-1]*k
d[1] = 0
q = deque([])
q.append((1,0))
while q:
    now,dis = q.popleft()

    for nex,cost in e[now]:
        if d[nex] == -1 or d[nex] > dis+cost:
            d[nex] = dis+cost
            if cost == 0:
                q.appendleft((nex,dis))
            else:
                q.append((nex,dis+1))

print(d[0]+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
K=int(input())

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

dist=[-1]*K
s,t=1,0
queue=[s]
d=0
while queue:
  new_queue=set()
  
  while queue:
    q=queue.pop()  
    if dist[q]==-1:
      dist[q]=d
      for v,w in graph[q]:
        if w==0:
          queue.append(v)
        else:
          new_queue.add(v)
  
  d+=1
  queue=list(new_queue)
  
#print(dist)
print(dist[0]+1)

Submission status: Accepted

Solution code:
K=int(input())
a=K
while a%2==0:
    a//=2
while a%5==0:
    a//=5
if a==1:
    print(1)
else:
    mod=set([])
    a=1
    while a not in mod:
        mod.add(a)
        a*=10
        a%=K

    mod=list(mod)
    n=len(mod)
    wei=pow(2,K)-1
    check=1
    ans=0
    for j in range(0,n):
        ans=ans|(check<<mod[j])
    check=ans
    for i in range(1,46):
        if check>>0 &1==1:
            print(i)
            exit()
        ans=check
        for j in range(0,n):
            ans=ans|(check<<mod[j])
        ans1=ans&wei
        ans2=ans>>K
        check=ans1|ans2

Submission status: Accepted

Solution code:
# solution

import io
import math
import scipy.sparse
import numpy
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:
import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)

Submission status: Accepted

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

K = int(input())

D = [-1]*K

q = deque()
q.append(1)
D[1] = 1
while q:
    p = q.pop()
    n1 = (p*10)%K
    if D[n1] == -1 or D[n1] > D[p]:
        D[n1] = D[p]
        q.append(n1)
    n2 = (p+1)%K
    if D[n2] == -1:
        D[n2] = D[p] + 1
        q.appendleft(n2)
print(D[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
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))
dq=deque([1])
res=[float('inf')]*k
res[1]=1
while dq:
  v=dq.popleft()
  if v==0:
    break
  for t,cost in g[v]:
    if res[t]<=res[v]+cost:
      continue
    res[t]=res[v]+cost
    if cost:
      dq.append(t)
    else:
      dq.appendleft(t)
print(res[0])

Submission status: Accepted

Solution code:
from collections import deque


K = int(input())
path = [K] * K

q = deque()
path[1] = 0
q.append(1)
while q:
    p = q.popleft()
    p1 = (p + 1) % K
    if path[p1] > path[p] + 1:
        path[p1] = path[p] + 1
        q.append(p1)
    
    p10 = (p * 10) % K
    if path[p10] > path[p]:
        path[p10] = path[p]
        q.appendleft(p10)

print(path[0] + 1)

Submission status: Accepted

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


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

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

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

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

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    def dijkstra(start,n,edges):
        d=[INF]*n
        used=[False]*n
        d[start]=0
        used[start]=True
        edgelist=[]
        for edge in edges[start]:
            heappush(edgelist,edge)
        while edgelist:
            minedge=heappop(edgelist)
            if used[minedge[1]]:
                continue
            v=minedge[1]
            d[v]=minedge[0]
            used[v]=True
            for edge in edges[v]:
                if not used[edge[1]]:
                    heappush(edgelist,(edge[0]+d[v],edge[1]))
        return d
    
    K=int(input())
    edges=[[] for _ in range(K)]
    for i in range(K):
        edges[i].append((1,(i+1)%K))
        edges[i].append((0,i*10%K))
    d=dijkstra(1,K,edges)
    print(d[0]+1)

if __name__ == '__main__':
    main()