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: Wrong Answer

Solution code:
n = int(input())
ans = 0
temp = n
while( n < 10 ):
	n += temp
temp = (n%9)
print( temp if temp != 0 else sum([int(x) for x in str(n)]) )

Submission status: Wrong Answer

Solution code:
def s(n):
    ret = 0
    sn = str(n)
    for c in sn:
        ret += int(c)
    return ret

N = int(input())
t = N

ans = float('inf')
for i in range(100000):
    t += N
    ans = min(s(t), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
def s(n):
    return sum(int(c) for c in str(n))

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

    digsum = s(n)
    for k in range(int(1e4)):
        digsum = s(k * n)

    powers = [10]
    for _ in range(60):
        powers.append(powers[-1] * 10)

    for power in powers:
        if power < n:
            continue
        k = (power + n - 1) // n
# print(power, n * k)
        digsum = min(digsum, s(n * k))

    print(digsum)

main()

Submission status: Wrong Answer

Solution code:
def func(n, k):
    ret = sum(map(int, str(n*k)))
    return ret
k = int(input())
m = 10e9
for i in range(1, 10):
    m = min(m, func(i, k))
print(m)

Submission status: Wrong Answer

Solution code:
def get_sum(n):
	sum = 0
	for byte in str(n):
		sum += int(byte)
	return sum
a = input()
minn = 9999999999999999999999999999L
for x in xrange(1, 200000):
	minn = min(get_sum(a * x), minn)
print minn

Submission status: Wrong Answer

Solution code:
def s(n):
    return sum(int(c) for c in str(n))

def main():
    n = int(input())
    powers = [10]
    for _ in range(800):
        powers.append(powers[-1] * 10)

    digsum = s(n)
    for power in powers:
        if power < n:
            continue
        k = (power + n - 1) // n
        # print(power, n * k)
        digsum = min(digsum, s(n * k))

    print(digsum)

main()

Submission status: Wrong Answer

Solution code:
def s(n):
    return sum(int(c) for c in str(n))

def main():
    n = int(input())
    powers = [10]
    for _ in range(50):
        powers.append(powers[-1] * 10)

    digsum = s(n)
    for power in powers:
        if power < n:
            continue
        k = (power + n - 1) // n
        #print(power, n * k)
        digsum = min(digsum, s(n * k))

    print(digsum)

main()

Submission status: Wrong Answer

Solution code:
def s(n):
    return sum(int(c) for c in str(n))

def main():
    n = int(input())
    powers = [10]
    for _ in range(11):
        powers.append(powers[-1] * 10)

    digsum = s(n)
    for power in powers:
        if power < n:
            continue
        k = (power + n - 1) // n
# print(power, n * k)
        digsum = min(digsum, s(n * k))

    print(digsum)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import*
q=[(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=[(-~n%k,s+1)]+q
print(m[0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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)
    check=1
    table=[0 for i in range(0,n)]
    for i in range(1,46):
        for j in range(0,n):
            table[j]=(check<<mod[j])|check
        ans=0
        for j in range(0,n):
            ans=ans|table[j]
        check=ans
        for j in range(1,46):
            if (check>>j*K)&1==1:
                print(i)
                exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
# import math
# import queue
# import copy
# import bisect#2分探索


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

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    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.insert(0,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: Time Limit Exceeded

Solution code:
import sys
# import math
# import queue
# import copy
# import bisect#2分探索

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

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    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.insert(0,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: Time Limit Exceeded

Solution code:
import sys
# import math
# import queue
# import copy
# import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())
def inputl():
    return list(map(int, input().split()))
def printl(li):
    print(*li, sep="\n")
def argsort(s):
    return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = inputi()
#N, K = inputl()
#L = [int(input()) for i in range(N)]
#A = inputl()
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)


#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    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.insert(0,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: Time Limit Exceeded

Solution code:
import math
import sys
import queue
import copy
import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())
def inputl():
    return list(map(int, input().split()))
def printl(li):
    print(*li, sep="\n")
def argsort(s):
    return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = inputi()
#N, K = inputl()
#L = [int(input()) for i in range(N)]
#A = inputl()
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)


#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    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.insert(0,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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from numpy.fft import rfft, irfft
import numpy as np

K = int(input())

tmp = 1
dp = np.zeros(K, dtype=int)
while dp[tmp] == 0:
    dp[tmp] = 1
    tmp = tmp * 10 % K

init = dp[:]
KDP = rfft(init, 2*K)
for c in range(1,50):
    if dp[0] > 0:
        print(c)
        break
    NDP = rfft(dp, 2*K)
    Tmp = (irfft(KDP*NDP)[:2*K]+0.5).astype(int)
    dp = np.minimum(Tmp[:K] + Tmp[K:] + init, np.ones(K, dtype=int))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
k=int(input())
ans=float("inf")
for i in range(1,10000000):
    n=str(k*i)
    a=sum(map(int, n))
    ans=min(ans,a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
min_=10**10
for i in range(1,10**7):
    min_=min(min_,sum(list(map(int, str(N*i)))))
print(min_)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush 
k=int(input())
inf=float("inf")
data=[[] for i in range(k)]
for i in range(1,k):
    if i%10==9:
        data[i]=[[i*10%k,0]]
    else:
        data[i]=[[i*10%k,0],[(i+1)%k,1]]

que=[[1,1]]
ans=[inf]*k
count=1
while que:
    c,u=heappop(que)
    ans[u]=c
    for v,d in data[u]:
        if ans[v]==inf:
            heappush(que,[d+c,v])
    if ans[0]!=inf:
        break
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
n = input()
c = 0
for i in n:
  c += int(i)
for i in range(1,10**7):
  d = 0
  l = str(int(n)*(i+1))
  for j in l:
    d += int(j)
  c = min(c, d)
print(c)

Submission status: Time Limit Exceeded

Solution code:
mini=10**9 
k=int(input())
p=10**7 
def s(x):
    sm=0 
    while x:
        sm+=(x%10)
        x//=10 
    return sm 
for z in range(1,p):
    a=k*z 
    mini=min(mini,s(a)) 
print(mini)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
cmin = 10**10
for i in range(1,1000001):
    s= str(K*i)
    cnt = 0
    for j in range(len(s)):
        cnt += int(s[j])
    cmin = min(cmin,cnt)
print(cmin)

Submission status: Time Limit Exceeded

Solution code:
import heapq
K=int(input())
G=[[(1,(i+1)%K)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((0,a))
stack=list(G[1])
heapq.heapify(stack)
reached=[0]*K
reached[1]=1
while(stack):
    c,g=heapq.heappop(stack)
    if g==0:
        print(c+1)
        quit()
    reached[g]=1
    for i in G[g]:
        if reached[i[1]]:
            continue
        heapq.heappush(stack,(c+i[0],i[1]))

Submission status: Time Limit Exceeded

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

def DIJKSTRA(point,d,n):
    cost      = {node:float("inf") for node in range(n)}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    k=int(input())
    d=defaultdict(list)
    for i in range(k-1): #１加算をつなぐ
        d[i].append([i+1,1])
    d[k-1].append([0,1])
    for i in range(k):  #10倍をつなぐ
        d[i].append([(i*10)%k,0])
    #print(d)
    
    
    print(DIJKSTRA(1,d,k)[0]+1)

    
    
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

def DIJKSTRA(point,d,n):
    cost      = {node:float("inf") for node in range(n)}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

def main():
    k=int(input())
    d=defaultdict(list)
    for i in range(k-1): #１加算をつなぐ
        d[i].append([i+1,1])
    d[k-1].append([0,1])
    for i in range(k):  #10倍をつなぐ
        d[i].append([(i*10)%k,0])
    #print(d)
    
    
    print(DIJKSTRA(1,d,k)[0]+1)

    
    
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
K = int(input())
Q = collections.deque([(1, 1)])
searched = set()
while True:
    n, d = Q.popleft()
    r = n % K
    if not r in searched:
        if r == 0:
            break
        else:
            searched.add(r)
            Q.append((n + 1, d + 1))
            Q.appendleft((n * 10, d))
print(d)
# https://img.atcoder.jp/arc084/editorial.pdf

Submission status: Time Limit Exceeded

Solution code:
import collections
K = int(input())
Q = collections.deque([[1, 1]])
searched = set()
while True:
    n, d = Q.popleft()
    r = n % K
    if not r in searched:
        if r == 0:
            break
        else:
            searched.add(r)
            Q.append([n + 1, d + 1])
            Q.appendleft([n * 10, d])
print(d)
# https://img.atcoder.jp/arc084/editorial.pdf

Submission status: Time Limit Exceeded

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

q = [1]
arrival = [-1 for i in range(k)]
while len(q) != 0:
    if arrival[q[0]] == -1:
        arrival[q[0]] = 0
    for i in range(len(graph[q[0]])):
        if arrival[graph[q[0]][i][0]] == -1:
            arrival[graph[q[0]][i][0]] = arrival[q[0]] + graph[q[0]][i][1]
            q.append(graph[q[0]][i][0])
        else:
            if arrival[graph[q[0]][i][0]] > arrival[q[0]] + graph[q[0]][i][1]:
                arrival[graph[q[0]][i][0]] = arrival[q[0]] + graph[q[0]][i][1]
                q.append(graph[q[0]][i][0])
    q.pop(0)

print(arrival[0]+1)

Submission status: Time Limit Exceeded

Solution code:
import heapq


def small_multiple(k):
    # kの倍数で各桁の総数が最も小さくなるような、各桁の総数
    dist = [float("inf")] * k
    q = []
    # kで割った余りが1になるような最小の数は1
    heapq.heappush(q, (1, 1))

    while q:
        n, c = heapq.heappop(q)
        if dist[n] <= c:
            continue
        dist[n] = c

        if dist[(n + 1) % k] > c + 1:
            heapq.heappush(q, ((n + 1) % k, c + 1))
        if dist[(n * 10) % k] > c:
            heapq.heappush(q, ((n * 10) % k, c))

    print(dist[0])


def main():
    k = int(input())
    small_multiple(k)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq


k = int(input())
dist = [float("inf")] * k
q = []
heapq.heappush(q, (1, 1))

while q:
    n, c = heapq.heappop(q)
    if dist[n] <= c:
        continue
    dist[n] = c

    if dist[(n+1) % k] > c + 1:
        heapq.heappush(q, ((n + 1) % k, c + 1))
    if dist[(n*10) % k] > c:
        heapq.heappush(q, ((n * 10) % k, c))

print(dist[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

while n%2 == 0:
  n = n//2
while n%5 == 0:
  n = n//5
  
def f(l):
  l0 = []
  for t in l:
    x = t
    while x not in l0:
      l0.append(x)
      x = (10*x)%n
  return l0
  
p = f([1])
q = []
a = 1

while 0 not in p:
  for t in p:
    q.append((t+1)%n)
  p = f(q)[:]
  q = []
  a += 1
    
print(a)

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
ans=len(str(K))*9
for i in range(1,3*10**6):
    a=list(str(K*i))
    a2=list(map(int,a))
 
    ans=min(ans,sum(a2))
 
print(ans)

Submission status: Time Limit Exceeded

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
V = [-1] * (K)
V[1] = 1
q = deque([1])
i = 1
while V[0] == -1:
    i = q.popleft()
    if i != E[i][0]:
        q.appendleft(E[i][0])
        V[E[i][0]] = V[i]
    if V[E[i][1]] == -1:
        q.append(E[i][1])
        V[E[i][1]] = V[i]+1
print(V[0])

Submission status: Time Limit Exceeded

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
V = [-1] * (K)
V[1] = 1
q = deque([1])
i = 1
while V[0] == -1:
    i = q.popleft()
    q.appendleft(E[i][0])
    V[E[i][0]] = V[i]
    if V[E[i][1]] == -1:
        q.append(E[i][1])
        V[E[i][1]] = V[i]+1
print(V[0])

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
# A,B,C = [int(n) for n in input().split()]

# a = [int(input()) for _ in range(N)]
# S = str(input())
# L = len(S)
# T = str(input())
# exit()
N = int(input())
K = 10**7
i = 1
ss = set()
while(i != K):
    s = list(str(N*i))
    # print(s)
    tmp = 0
    for j in range(len(s)):
        tmp+=int(s[j])
    # print(tmp)
    ss.add(tmp)
    i+=1
print(sorted(list(ss))[0])

Submission status: Time Limit Exceeded

Solution code:
k = int(input())

a = [0]*(10**6)
for i in range(10**6):
    a[i] = sum([int(c) for c in str(k*(i+1))])

print(min(a))

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
c=float("inf")
for i in range(10**5,10**6+1):
    c=min(c,sum([int(d) for d in str(k*i)]))
print(c)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
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)]
mod = 1000000007

#A
"""
a = input()
b = input()
if a[2] == b[0] and a[1] == b[1] and a[0] == b[2]:
    print("YES")
else:
    print("NO")
"""

#B
"""
n = I()
n = int(math.sqrt(n))
print(n**2)
"""

#C
"""
n = I()
a = LI()
a.sort()
b = LI()
b.sort()
c = LI()
c.sort()
ans = 0
for i in b:
    x = bisect.bisect_left(a, i)
    x = x * (n - bisect.bisect_right(c, i))
    ans += x
print(ans)
"""

#D
k = I()
ans = list(str(k))
ans = sum(list(map(int, ans)))
for i in range(2, 10**10):
    bk = list(str(k*i))
    bk = list(map(int, bk))
    ans = min(ans, sum(bk))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
# while n%10 == 0:
#   n //= 10
a = []
x = 1
while not x in a:
  a += [x]
  x = (10*x)%n
# print(a)

b = a[::]
# print(b)
k = 1
while not 0 in b:
  c = []
  for x in a:
    for y in b:
      c += [(x+y)%n]
  b = list(set(c))
  k += 1
print(k)

Submission status: Time Limit Exceeded

Solution code:
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=[((n+1)%K,s+1)]+q
 if n==0:print(s);exit()

Submission status: Time Limit Exceeded

Solution code:
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=[((n+1)%K,s+1)]+q
print(m[0])

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
min_ans=10**28
for i in range(1,1000000):
    a = N*i
    a = str(a)
    ans=0
    for i in range(len(a)):
        ans+=int(a[i])
    min_ans=min(ans,min_ans)
print(min_ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
K = int(input())
INF = float("inf")
d = [INF] * K
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))

d[1] = 0
que = [(1, 0)]
while que:
    v, cost = heappop(que)
    if d[v] < cost:
        continue

    for w, c in G[v]:
        if d[w] > d[v] + c:
            d[w] = d[v] + c
            heappush(que, (w, d[w]))

print(d[0] + 1)

Submission status: Time Limit Exceeded

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, cur = que.popleft()
    if kmod[cur%k] == 0:
        kmod[cur%k] = cost
        que.appendleft((cost, 10*cur))
        que.append((cost+1, cur+1))            
        
print(kmod[0])

Submission status: Time Limit Exceeded

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, cur = que.popleft()
    if kmod[cur%k] == 0:
        kmod[cur%k] = cost
        if kmod[(10*cur)%k] == 0:
            que.appendleft((cost, 10*cur))
        if kmod[(cur+1)%k] == 0:
            que.append((cost+1, cur+1))            
        
print(kmod[0])

Submission status: Time Limit Exceeded

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, cur = que.popleft()
    if kmod[cur%k] == 0:
        kmod[cur%k] = cost
    
    if kmod[(10*cur)%k] == 0:
        que.appendleft((cost, 10*cur))
    
    if kmod[(cur+1)%k] == 0:
        que.append((cost+1, cur+1))
            
        
print(kmod[0])

Submission status: Time Limit Exceeded

Solution code:
a=int(input())

b = []

for i in range(1,1000000):
    c = a*i
    k = 0
    for j in range(0,13):
        k += (c//(10**j))%10
    b.append(k)

print(min(b))

Submission status: Time Limit Exceeded

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

D = lil_matrix((K, K))
for i in range(K-1):
    D[i, i + 1] = 1
    D[i, (i * 10) % K] = 10**(-8)
D[K - 1, 0] = 1
D[K - 1, ((K - 1) * 10) % K] = 10**(-8)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = [(1, 0)]
    vis = {}
    while q:
        # print(len(q))
        u, cc = q.pop(0)
        if u == 0:
            return cc + 1
        vis[u] = True
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.insert(0, (v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(K):

    g = defaultdict(dict)
    for i in range(1, K+1):
        g[i % K][(i+1) % K] = 1
        g[i % K][(i*10) % K] = 0

    q = [(1, 0)]
    vis = []
    while q:
        # print(len(q))
        u, cc = q.pop(0)
        if u == 0:
            return cc + 1
        vis.append(u)
        for v, c in g[u].items():
            if v in vis:
                continue
            if c == 0:
                q.insert(0, (v, cc))
            else:
                q.append((v, cc+c))


def main():
    K = read_int()
    print(slv(K))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

INF = 1000000007
K = int(input())

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

h = []
hq.heappush(h, (1, 1))

while h:
    v, c = hq.heappop(h)
    if dist[v] <= c:
        continue
    dist[v] = c
    
    if dist[(v+1)%K] > c+1:
        hq.heappush(h, ((v+1)%K, c+1))
    if dist[(v*10)%K] > c:
        hq.heappush(h, ((v*10)%K, c))

print(dist[0])

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
ans=float("Inf")
for i in range(1,6*10**6):
    a=list(str(K*i))
    a2=list(map(int,a))
 
    ans=min(ans,sum(a2))
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(K):
    checked = [99999999999] * (K + 1)
    queue = [(1, 1)]
    checked[1] = 1
    while queue:
        x, n = queue.pop(0)
        if x == 0:
            return n
        _ = (x * 10) % K 
        if n < checked[_]:
            queue.insert(0, (_, 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))

Submission status: Time Limit Exceeded

Solution code:
def solve(K):
    checked = [0] * (K + 1)
    queue = [(1, 1)]
    checked[1] = 1
    while queue:
        x, n = queue.pop(0)
        # print((x, n), queue)
        if x == 0:
            return n
        _ = (x * 10) % K 
        if checked[_] == 0 or n < checked[_]:
            queue.insert(0, (_, n))
            checked[_] = n
        _ = (x + 1) % K 
        if checked[_] == 0 or n + 1 < checked[_]:
            queue.append((_, n + 1))
            checked[_] = n + 1
    return None

K = int(input())
print(solve(K))

Submission status: Time Limit Exceeded

Solution code:
from datetime import datetime
K = int(input())
start = datetime.now()
def KSum(n):
    k = 0
    for i in str(n):
        k += int(i)
    return k

m = KSum(K)
j = 1
while((datetime.now()-start).total_seconds()<1.9):
    P = KSum(K*j)
    if m > P:
        m = P
    j += 1

print(m)

Submission status: Time Limit Exceeded

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

q = deque()
q.append((1, 1, 1))
used = set()
while True:
    x, y, k = q.popleft()
    if (x, y, k) in used:
        continue
    else:
        used.add((x, y, k))
    # print(x, y, k)
    if k % K == 0:
        print(x)
        break
    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))

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict,deque

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 = [] #後ろの方が優先度高いqueue
que.append((0,1))
while len(que)!=0:
    temp=que.pop()
    now=temp[1]
    v_now=graph[now]
    for c,n in v_now: #v nowから出てる総てのノードについて操作する c→ノードのコスト n→行き先
        if costs[n]>c+costs[now]: #改善したのでそのvは走査の余地あり
            costs[n]=c+costs[now]
            que.append((c,n))
    que=sorted(que,reverse=True)
print(costs[0])

Submission status: Time Limit Exceeded

Solution code:
import heapq
def dijkstra(N,start, goal, E):
    """最短距離,経路を返すプログラム"""
    dist = [float('inf')] * N          #dist[i]:始点からの距離
    path = [tuple() for n in range(N)] #path[i]:(start,...,i)までの経路をカンマで区切ったもの
    dist[start] = 0
    path[start] = (start, )            
    pq = [(0, path[start])]

    while pq:
        di, pathi = heapq.heappop(pq)
        v = pathi[-1]

        if v == goal:
            return di,pathi

        #辺を全部見る
        for vertex, weight in E[v].items():
            new_di = di + weight
            if (new_di < dist[vertex]) or (new_di == dist[vertex] and pathi + (vertex, ) < path[vertex]):
                dist[vertex] = new_di
                path[vertex] = pathi + (vertex, )
                heapq.heappush(pq, (new_di, path[vertex]))

K = int(input())
E = [dict() for _ in range(K)]

for i in range(K-1):
    E[i][i+1] = 1
    E[i][((i * 10) % K)] = 0

E[K-1][0] = 1
E[(K-1)][((K-1)*10)%K] = 0

ans,path = dijkstra(K,1,0,E)

print(ans+1)