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:
from collections import deque
K=int(input())

INF=10**9
res=[INF]*(K)

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

Submission status: Wrong Answer

Solution code:
def digitsum(n):
  L=list(str(n))
  L=list(map(int,L))
  return sum(L)
N=int(input())
mina=10**10
while True:
  if N%2==0:
    N=N//2
  else:
    break
while True:
  if N%5==0:
    N=N//5
  else:
    break
for i in range(1,1000001):
  mina=min(mina,digitsum(i*N))
print(mina)

Submission status: Wrong Answer

Solution code:
def digitsum(n):
  L=list(str(n))
  L=list(map(int,L))
  return sum(L)
N=int(input())
mina=10**10
for i in range(1,1000001):
  mina=min(mina,digitsum(i*N))
print(mina)

Submission status: Wrong Answer

Solution code:
K = int(input())

N = 10**6
ans = N

for n in range(1,N+1):
    ans = min(ans,sum(list(map(int,list(str(K*n))))))
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

N = 10**5
ans = N

for n in range(1,N+1):
    ans = min(ans,sum(list(map(int,list(str(K*n))))))
print(ans)

Submission status: Wrong Answer

Solution code:
k = int(input())
ans = float("inf")
for i in range(1, 3 * 10 ** 6):
    ans = min(ans, sum(list(map(int, list(str(k * i))))))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import *
K=int(input())
D=[K+1]*K
D[1]=1
Q=deque()
S=set()
def qao(x,y):
  if x in S:
    return False
  S.add(x)
  if y:
    Q.append(x)
  else:
    Q.appendleft(x)
  return True

def bfs():
  global Q,D,K
  v=0
  for i in range(len(Q)):
    v=Q.popleft()
    if qao(v*10%K,0):
      D[v*10%K]=D[v]
    if qao((v+1)%K,1):
      D[(v+1)%K]=D[v]+1
  return len(Q)

qao(1,0)
while bfs():
  pass
print(D[0])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

print(D[0])

Submission status: Wrong Answer

Solution code:
from collections import deque

K = int(input())
D = [sum(map(int,list(str(K))))]*K
D[1] = 1
H = deque()
H.append(1)
while len(H) != 0:
    h = H.pop()
    if D[(h+1)%K] < D[h] + 1:
        D[(h+1)%K] = D[h] + 1
        H.appendleft((h+1)%K)
    if D[(h*10)%K] < D[h]:
        D[(h*10)%K] = D[h]
        H.append((h*10)%K)

print(D[0])

Submission status: Wrong Answer

Solution code:
def mizu(x,ans):
    temp=0
    while x>0:
        temp+=x%10
        x//=10
        if ans<temp:
            return 10**9+1
            break
    else:
        return temp 

def main():
    K=int(input())
    ans=10**9
    for i in range(1,12**6):
        if i%10!=0:
            ans=min(ans,mizu(i*K,ans))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def mizu(x,ans):
    temp=0
    while x>0:
        temp+=x%10
        x//=10
        if ans<temp:
            return 10**9+1
            break
    else:
        return temp 

def main():
    K=int(input())
    ans=10**9
    for i in range(1,10**7):
        ans=min(ans,mizu(i*K,ans))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def mizu(x,ans):
    temp=0
    while x>0:
        temp+=x%10
        x//=10
        if ans<temp:
            return 10**9+1
            break
    else:
        return temp 

def main():
    K=int(input())
    ans=10**9
    for i in range(1,10**6):
        ans=min(ans,mizu(i*K,ans))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def digit_sum(x):
  y=list(str(x))
  res=0
  for i in range(len(y)):
    res+=int(y[i])
  return res
k=int(input())
ans=10**9
for i in range(1,10**6+1):
  ans=min(ans,digit_sum(k*i))
print(ans)

Submission status: Wrong Answer

Solution code:
def digit_sum(x):
  y=list(str(x))
  res=0
  for i in range(len(y)):
    res+=int(y[i])
  return res
k=int(input())
ans=10**9
for i in range(1,10**5+1):
  ans=min(ans,digit_sum(k*i))
print(ans)

Submission status: Wrong Answer

Solution code:
k=int(input())
def digitsum(i):
  s=str(i)
  arr=list(map(int,s))
  return sum(arr)
ans=10**9
for i in range(1,7*10**5):
  j=digitsum(i*k)
  if ans>j:
    ans=j
print(ans)

Submission status: Wrong Answer

Solution code:
k=int(input())
def digitsum(i):
  s=str(i)
  arr=list(map(int,s))
  return sum(arr)
ans=10**9
for i in range(1,10**5):
  j=digitsum(i*k)
  if ans>j:
    ans=j
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ls = []
for i in range(1,200001):
  x = list(str(n*i))
  y = 0
  for i in x:
    y += int(i)
  ls.append(y)
print(min(ls))

Submission status: Wrong Answer

Solution code:
from collections import deque

k = int(input())
dist = [-1]*k
dist[1] = 0
dq = deque([1])
while dq:
  v = dq.popleft()
  nv1, nv2 = (v*10)%k, (v+1)%k
  if dist[nv1] == -1:
    dist[nv1] = dist[v]
    if nv1 == 0:
      break
    dq.appendleft(nv1)
  if dist[nv2] == -1:
    dist[nv2] = dist[v]+1
    if nv2 == 0:
      break
    dq.append(nv2)
print(dist[0]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

k = int(input())
dist = [-1]*k
dist[1] = 0
dq = deque([1])
while dq:
  v = dq.popleft()
  nv1, nv2 = (v+1)%k, (v*10)%k
  if dist[nv1] == -1:
    dist[nv1] = dist[v] + 1
    if nv1 == 0:
      break
    dq.append(nv1)
  if dist[nv2] == -1:
    dist[nv2] = dist[v]
    if nv2 == 0:
      break
    dq.appendleft(nv2)
print(dist[0]+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
m = 100

for i in range(2, 1000000):
    x = n * i
    c = 0

    while x > 0:
        c += x % 10
        x //= 10

    m = min(c, m)

print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
m = 100

for i in range(2, 100000):
    x = n * i
    c = 0

    while x > 0:
        c += x % 10
        x //= 10

    m = min(c, m)

print(m)

Submission status: Wrong Answer

Solution code:
from collections import deque
K=int(input())
dist=[0 for i in range(K)]
reached=[0 for i in range(K)]
dist[1]=1
q=deque([1])
while(len(q)>0):
    x=q.popleft()
    reached[x]=1
    if reached[(x*10)%K]==0:
        dist[(x*10)%K]=dist[x]
        q.appendleft((x*10)%K)
    if reached[(x+1)%K]==0:
        dist[(x+1)%K]=dist[x]+1
        q.append((x+1)%K)
print(dist[0])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque
K=int(input())#modKのグラフ
Link=[[] for i in range(K)]
for i in range(K):
    Link[i].append((i*10)%K)
    Link[i].append((i+1)%K)
#BFSで1から0へ
went=[False]*K
went[1]=True
queue=deque()
queue.append((1,0))
while queue:
    cur,dim = queue.popleft()
    if cur==0:
        print(dim+1)
        break
    for distone,togo in enumerate(Link[cur]):
        if not went[togo]:
            went[togo] = True
            if distone:
                queue.append((togo,dim+1))
            else:
                queue.appendleft((togo,dim))

Submission status: Wrong Answer

Solution code:
from collections import deque
K=int(input())
dist=[-1 for i in range(K)]
dist[1]=1
q=deque([1])
while(len(q)>0):
    x=q.popleft()
    if dist[(x*10)%K]==-1:
        dist[(x*10)%K]=dist[x]
        q.appendleft((x*10)%K)
    if dist[(x+1)%K]==-1:
        dist[(x+1)%K]=dist[x]+1
        q.append((x+1)%K)
print(dist[0])

Submission status: Wrong Answer

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

print(dic[0])

Submission status: Wrong Answer

Solution code:
k = int(input())
g = [[] for _ in range(k)]
g[-1].append(0)
g[-1].append((k-1)*10%k)
for i in range(1,k-1):
    if str(i)[-1]!='9':
        g[i].append(i+1)
    if i*10%k!=i:
        g[i].append(i*10%k)
from collections import deque
done = set([])
queue = deque(g[1])
k = 0
ans = 0
while queue!=[]:
    new_queue = deque()
    while queue:
        v = queue.pop()
        for v_ in g[v]:
            if v_ == 0:
                k = 1
                break
            if not v_ in done:
                new_queue.append(v_)
                done |= set([v_])
    ans += 1
    if k==1:
        break
    queue = new_queue
print(ans+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq

# 1から初めて、xがあるとき10x、x+1のいずれかが行えるとしてqueue

K = int(input())
h = []
heapq.heappush(h,(1,1)) # 各桁の和、modulo K
visited = np.full(K,False)

ans = 0

while ans == 0:
  s,x = heapq.heappop(h)
  for ss,xx in [(s,(10*x)%K), (s+1,(x+1)%K)]:
    if visited[xx]:
      continue
    if xx == 0:
      ans = ss
      break
    visited[xx] = True
    heapq.heappush(h,(ss,xx))
  
print(ans)

Submission status: Wrong Answer

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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    a = II()
    ans = inf
    b = 0
    for k in range(1, 10 ** 5):
        b += a
        ans = min(ans, sum(list(map(int, list(str(b))))))
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

K=INT()
ans=INF
for i in range(1, 1000001):
    k=K*i
    sm=0
    for s in str(k):
        sm+=int(s)
    ans=min(ans, sm)
print(ans)

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

K=INT()
ans=INF
for i in range(1, 100001):
    k=K*i
    sm=0
    for s in str(k):
        sm+=int(s)
    ans=min(ans, sm)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(k):
    que = deque()
    que.append((1, 1))
    dp = {1: 1}
    while que:
        x, c = que.pop()
        y = (x + 1) % k
        if not y in dp:
            dp[y] = c + 1
            que.appendleft((y, c+1))
        z = (10 * x) % k
        if not z in dp:
            dp[z] = c
            que.append((z, c))
    return dp[0]

k = int(input())
print(solve(k))

Submission status: Wrong Answer

Solution code:
from collections import deque

def sum_digit(x):
    res = 0
    while x > 0:
        res += x % 10
        x //= 10
    return res

def solve(k):
    que = deque()
    que.append(1)
    best = sum_digit(k)
    used = {i: False for i in range(k)}
    while que:
        x = que.pop()
        if x % k == 0:
            best = min(best, sum_digit(x))
        y = x + 1
        if not used[y % k]:
            used[y % k] = True
            que.appendleft(y)
        z = 10 * x
        if not used[z % k]:
            used[z % k] = True
            que.append(z)
    return best

k = int(input())
print(solve(k))

Submission status: Wrong Answer

Solution code:
K = int(input())

result = 10**9
for i in range(1, 10**5):
    c = str(K*i)
    r = 0
    for j in range(len(c)):
        r += int(c[j])
    if r < result:
        result = r

print(result)

Submission status: Wrong Answer

Solution code:
K = int(input())
while not K%2:
    K //= 2
while not K%5:
    K //= 5
ans = sum(map(int, str(K)))
for i in range(1,100000):
    ans = min(ans, sum(map(int, str(K*i))))
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
while not K%2:
    K //= 2
while not K%5:
    K //= 5
if sum(map(int, str(K))) == K%9:
    print(K%9)
else:
    ans = sum(map(int, str(K)))
    for i in range(1,100000):
        ans = min(ans, sum(map(int, str(K*i))))
    print(ans)

Submission status: Wrong Answer

Solution code:
import time
n = int(input())
sTime = time.time()

def sum_digit(n):
    s = 0
    while n>0:
        s += n%10
        n //= 10
    return s


mi = n
t = 0
for i in range(1, 10**n):
    mi = min(mi, sum_digit(n*i))
    t = time.time() - sTime
    if t > 1.8:
        break
        
print(mi)

Submission status: Wrong Answer

Solution code:
x = [[]]
n = int(input())
while n % 2 == 0:
    n //= 2
while n % 5 == 0:
    n //= 5

if n == 1:
    print(1)
else:
    s = 10 % n
    for i in range(10):
        x[0].append(s)
        if s == 1:
            break
        s *= 10
        s %= n
    flg = 0
    for i in range(n):
        x.append([])
        for y in x[i]:
            for z in x[0]:
                w = (y+z) % n
                if w == 0:
                    print(i+2)
                    flg = 1
                    break
                if w not in x[i+1]:
                    x[i+1].append(w)
                    
            if flg > 0:
                break
        if flg > 0:
            break

Submission status: Wrong Answer

Solution code:
K=int(input())
a,b=0,0
while K%2==0:
  K=K//2
  a+=1
while K%5==0:
  K=K//5
  b+=1
if K==1:
  print(1)
  exit()

def S(x):
  res=0
  for i in range(len(str(x))):
    res+=int(str(x)[i])
  return res
r=1
p=0
t=10**10-1
for i in range(1,K+1):
  r=(r*10)%K
  if S(t)>S(K-r):
    t=K-r
    p=i

print(S((10**p+t)*10**(max(a,b))))

Submission status: Wrong Answer

Solution code:
K=int(input())
a,b=0,0
while K%2==0:
  K=K//2
  a+=1
while K%5==0:
  K=K//5
  b+=1
if K==1:
  print(1)
  exit()
m=0
p=0
t=10
for i in range(1,K+1):
  t=(t*10)%K
  if t>m:
    m=t
    p=i+1
S=1
for i in range(len(str(K-m))):
  S+=int(str(K-m)[i])
print(S)

Submission status: Wrong Answer

Solution code:
K=int(input())
while K%2==0:
  K=K//2
while K%5==0:
  K=K//5
m=0
t=10
for i in range(1,K+1):
  t=(t*10)%K
  m=max(t,m)
S=1
for i in range(len(str(K-m))):
  S+=int(str(K-m)[i])
print(S)

Submission status: Wrong Answer

Solution code:
K = int(input())
while not K%2:
    K //= 2
while not K%5:
    K //= 5
if sum(map(int, str(K))) == K%9:
    print(K%9)
ans = sum(map(int, str(K)))
for i in range(1,100000):
    ans = min(ans, sum(map(int, str(K*i))))
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
while not K%2:
    K //= 2
while not K%5:
    K //= 5
if sum(map(int, str(K))) == K%9:
    print(K%9)
ans = sum(map(int, str(K)))
for i in range(1,100000):
    ans = min(ans, sum(map(int, str(K*i))))

Submission status: Wrong Answer

Solution code:
K = int(input())
while not K%2:
    K //= 2
while not K%5:
    K //= 5
ans = sum(map(int, str(K)))
for i in range(1,10000):
    x = i*K
    ans = min(ans, sum(map(int, str(x))))
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
if K%9:
    while not K%2:
        K //= 2
    while not K%5:
        K //= 5
    print(K%9)
else:
    ans = sum(map(int, str(K)))
    for i in range(1,10000):
        x = i*K
        ans = min(ans, sum(map(int, str(x))))
    print(ans)

Submission status: Wrong Answer

Solution code:
def digsum(x):
	i = 0
	a = []
	while x!= 0:
		a.append((x % (10 ** (1+i))) // (10**i))
		x -= a[i] * 10**i
		i += 1
	s = 0
	for j in range(i):
		s += a[j]
	return s

K = int(input())

minimum = 100
for k in range(1,100000):
	if digsum(K * k) < minimum:
		minimum = digsum(K * k)
print(minimum)

Submission status: Wrong Answer

Solution code:
def digsum(x):
	i = 0
	a = []
	while x!= 0:
		a.append((x % (10 ** (1+i))) // (10**i))
		x -= a[i] * 10**i
		i += 1
	s = 0
	for j in range(i):
		s += a[j]
	return s

K = int(input())

minimum = 100
for k in range(1,1000):
	if digsum(K * k) < minimum:
		minimum = digsum(K * k)
print(minimum)

Submission status: Wrong Answer

Solution code:
def digsum(x):
	i = 0
	a = []
	while x!= 0:
		a.append((x % (10 ** (1+i))) // (10**i))
		x -= a[i] * 10**i
		i += 1
	s = 0
	for j in range(i):
		s += a[j]
	return s

K = int(input())

minimum = 1000
for k in range(1,9):
	if digsum(K * k) < minimum:
		minimum = digsum(K * k)
print(minimum)

Submission status: Wrong Answer

Solution code:
from collections import deque
K = int( input())
V = [0]*K
q = deque([(1,1)])
if K == 1:
    q.pop()
    ans = 1
while q:
    x, r = q.popleft()
    if V[x] == 1:
        continue
    V[x] = 1
    if 10*x%K == 0:
        ans = r
        break
    elif V[10*x%K] == 0:
        q.appendleft((10*x%K, r))
    if (x+1)%K == 0:
        ans = r+1
        break
    elif V[(x+1)%K] == 0:
        q.append(((x+1)%K, r+1))
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def digit_sum(num):
    ret = 0
    while num > 0:
        ret += num % 10
        num //= 10
    return ret

def main():
    n = int(input())
    ans = 1000000
    target = n
    for i in range(400):
        ans = min(ans, digit_sum(target))
        target *= n
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
k = int(input())


def count(x):
    return sum(map(int, str(x)))


result = 0x7ffffffff
for x in range(1, 100*k):
    result = min(result, count(x*k))
print(result)

Submission status: Wrong Answer

Solution code:
k = int(input())


def count(x):
    return sum(map(int, str(x)))


result = 0x7ffffffff
for x in range(1, 10*k):
    result = min(result, count(x*k))
print(result)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
from random import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def dsum(x):
  return sum(int(d) for d in str(x))

K = read()
ans = 1 << 31
for i in range(1, 10):
  ans = min(ans, dsum(K * i))
print(ans)

Submission status: Wrong Answer

Solution code:
def d(x):
    res = 0
    while x > 0:
        res += x % 10
        x /= 10
    return res

def solve(k):
    ans = d(k)
    for i in range(2, 1000000):
        ans = min(ans, d(k*i))
    return ans

# assert solve(6) == 3
# assert solve(41) == 5
# assert solve(79992) == 36
print solve(input())

Submission status: Wrong Answer

Solution code:
def d(x):
    res = 0
    while x > 0:
        res += x % 10
        x /= 10
    return res

def solve(k):
    ans = d(k)
    for i in range(2, 10000):
        ans = min(ans, d(k*i))
    return ans

assert solve(6) == 3
assert solve(41) == 5
assert solve(79992) == 36
print solve(input())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    k = f.read_int()

    depth = [-1] * k
    depth[1] = 1

    que = collections.deque([1])
    while len(que) > 0:
        num = que.popleft()
        n1 = (num*10)%k
        if depth[n1] < 0:
            depth[n1] = depth[num]
            que.appendleft(n1)
        n2 = (num+1)%k
        if depth[n2] < 0:
            depth[n2] = depth[num]+1
            que.append(n2)

    return depth[0]


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    k = f.read_int()

    depth = [-1] * k
    depth[1] = 0

    def dfs():
        que = collections.deque([1])
        while len(que) > 0:
            num = que.popleft()
            n1 = (num+1)%k
            if depth[n1] < 0:
                depth[n1] = depth[num]+1
                que.append(n1)
            n2 = (num*10)%k
            if depth[n2] < 0:
                depth[n2] = depth[num]
                que.appendleft(n2)

    dfs()
    return depth[0]+1


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
from collections import deque
K=int(input())
reached=[0 for i in range(K)]
reached[1]=1
dist=[0 for i in range(K)]
q=deque([])
q.append(1)
while(len(q)>0):
    r=q.pop()
    v=(r*10)%K
    if (reached[v]==0):
        q.appendleft(v)
        dist[v]=dist[r]
        reached[v]=1
    v=(r+1)%K
    if (reached[v]==0):
        q.append(v)
        dist[v]=dist[r]+1
        reached[v]=1
print(dist[0]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
K=int(input())
reached=[0 for i in range(K)]
reached[1]=1
dist=[0 for i in range(K)]
dist[1]=0
q=deque([])
q.append(1)
while(len(q)>0):
    r=q.popleft()
    v=(r*10)%K
    if (reached[v]==0):
        q.appendleft(v)
        dist[v]=dist[r]
        reached[v]=1
    v=(r+1)%K
    if (reached[v]==0):
        q.append(v)
        dist[v]=dist[r]+1
        reached[v]=1
print(dist[0]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
K=int(input())
reached=[0 for i in range(K)]
reached[1]=1
dist=[0 for i in range(K)]
dist[1]=1
q=deque([])
q.append(1)
while(len(q)>0):
    r=q.popleft()
    v=(r*10)%K
    if (reached[v]==0):
        q.appendleft(v)
        dist[v]=dist[r]
        reached[v]=1
    v=(r+1)%K
    if (reached[v]==0):
        q.append(v)
        dist[v]=dist[r]+1
        reached[v]=1
print(dist[0])

Submission status: Wrong Answer

Solution code:
import queue
K=int(input())
reached=[0 for i in range(K)]
reached[1]=1
dist=[0 for i in range(K)]
dist[1]=1
q=queue.Queue()
q.put(1)
while(not(q.empty())):
    r=q.get()
    v=(r*10)%K
    if (reached[v]==0):
        q.put(v)
        dist[v]=dist[r]
        reached[v]=1
    v=(r+1)%K
    if (reached[v]==0):
        q.put(v)
        dist[v]=dist[r]+1
        reached[v]=1
print(dist[0])

Submission status: Wrong Answer

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

K = int(input())

min_v = 100
for i in range(1,100000):
    tmp = K*i
    v = sum([int(c) for c in str(tmp)])
    min_v = min(min_v, v)
print(min_v)

Submission status: Wrong Answer

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

K = int(input())

min_v = 100
for i in range(1,10000):
    tmp = K*i
    v = sum([int(c) for c in str(tmp)])
    min_v = min(min_v, v)
print(min_v)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    K = I()

    # メソッドのみ版
    def search(s):
        q = [(1,s)]
        qi = 0
        v = [False] * (K+1)
        v[s] = True
        while len(q):
            k, u = heapq.heappop(q)
            t = u*10 % K
            while not v[t]:
                if t == 0:
                    return k
                heapq.heappush(q, (k, t))
                v[t] = True
                t = t*10 % K

            i = 1
            t = (u+i) % K
            while not v[t]:
                if t == 0:
                    return k+1
                heapq.heappush(q, (k+1, t))
                v[t] = True
                i = i*10 % K
                t = (u+i) % K

    return search(1)

print(main())