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:
K = int(input())
ans = 10**18
for i in range(1, 10**5+1):
    tmp = K*i
    tmp_ans = 0
    cnt = 1
    while tmp:
        tmp_ans += tmp%10
        tmp //= 10
        cnt += 1
    ans = min(ans, tmp_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
ans = 10**18
for i in range(1, 10):
    tmp = K*i
    tmp_ans = 0
    cnt = 1
    while tmp:
        tmp_ans += tmp%10
        tmp //= 10
        cnt += 1
    ans = min(ans, tmp_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import count
from collections import namedtuple, deque

def main():
    K = int(input())
    #桁和不変操作：現在の数値を10倍
    #桁和を１増やす操作：現在の数値に+1
    #0からこの操作を繰り返し、Kの倍数への最短経路が答え
    #Kの倍数⇔mod K が0
    node = namedtuple('node', ['rank', 'value'])
    operated = namedtuple('operated', ['value', 'rank_to_add','method'])
    ope = (lambda str: (lambda x:operated(value=x*10, rank_to_add=0, method='appendleft')) if str == 'mul10' 
                 else  (lambda x:operated(value=x+1, rank_to_add=1,method='append')))
    #01bfs   
    reserved = deque()
    reserved.append(node(rank=1,value=1))
    seen = {1} #mod K
    operate_str = ['mul10', 'plus1']
    while True:
        v = reserved.popleft()
        if v.value % K == 0:
            ans = v.rank
            break
        for str in operate_str:
            nv = ope(str)(v.value)
            if (nv.value % K) in seen:
                continue
            if v.value >= K:
                seen.add(nv.value % K)
            eval('reserved.'+nv.method)(node(rank=v.rank+nv.rank_to_add,value=nv.value))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from itertools import count
from collections import namedtuple, deque

def main():
    K = int(input())
    #桁和不変操作：現在の数値を10倍
    #桁和を１増やす操作：現在の数値に+1
    #0からこの操作を繰り返し、Kの倍数への最短経路が答え
    #Kの倍数⇔mod K が0
    node = namedtuple('node', ['rank', 'value'])
    operated = namedtuple('operated', ['value', 'rank_to_add','method'])
    ope = (lambda str: (lambda x:operated(value=x*10, rank_to_add=0, method='appendleft')) if str == 'mul10' 
                 else  (lambda x:operated(value=x+1, rank_to_add=1,method='append')))
    #01bfs   
    reserved = deque()
    reserved.append(node(rank=1,value=1))
    seen = {1} #mod K
    operate_str = ['mul10', 'plus1']
    while True:
        v = reserved.popleft()
        if v.value % K == 0:
            ans = v.rank
            break
        for str in operate_str:
            nv = ope(str)(v.value)
            if nv.value >= K and (nv.value % K) in seen:
                continue
            seen.add(nv.value % K)
            eval('reserved.'+nv.method)(node(rank=v.rank+nv.rank_to_add,value=nv.value))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from itertools import count
import heapq as hq
from collections import namedtuple

def main():
    K = int(input())
    #桁和不変操作：現在の数値を10倍
    #桁和を１増やす操作：現在の数値に+1
    #0からこの操作を繰り返し、Kの倍数への最短経路が答え
    #Kの倍数⇔mod K が0
    node = namedtuple('node', ['rank', 'value','modK'])
    operated = namedtuple('operated', ['value', 'rank_to_add'])
    ope = (lambda str: (lambda x:operated(value=x*10, rank_to_add=0)) if str == 'mul10' 
                 else  (lambda x:operated(value=x+1, rank_to_add=1)))
    #01bfs   
    reserved = []
    hq.heappush(reserved, node(rank=1,value=1,modK=1))
    seen = {1} #mod K
    operate_str = ['mul10', 'plus1']
    while True:
        v = hq.heappop(reserved)
        if v.modK == 0:
            ans = v.rank
            break
        for str in operate_str:
            nv = ope(str)(v.value)
            if (nv.value % K) in seen:
                continue
            seen.add(nv.value % K)
            hq.heappush(reserved, node(rank=v.rank+nv.rank_to_add,value=nv.value,modK=nv.value % K))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from itertools import count
import heapq as hq
from collections import namedtuple

def main():
    K = int(input())
    #桁和不変操作：現在の数値を10倍
    #桁和を１増やす操作：現在の数値に+1
    #0からこの操作を繰り返し、Kの倍数への最短経路が答え
    #Kの倍数⇔mod K が0
    node = namedtuple('node', ['rank', 'value','modK'])
    operated = namedtuple('operated', ['value', 'rank_to_add'])
    ope = (lambda str: (lambda x:operated(value=x*10, rank_to_add=0)) if str == 'mul10' 
                 else  (lambda x:operated(value=x+1, rank_to_add=1)))
    #01bfs   
    reserved = []
    hq.heappush(reserved, node(rank=1,value=1,modK=1))
    seen = {1} #mod K
    operate_str = ['mul10', 'plus1']
    while True:
        v = hq.heappop(reserved)
        if v.modK == 0:
            ans = v.rank
            break
        for str in operate_str:
            nv = ope(str)(v.value)
            if nv.value >= K and (nv.value % K) in seen:
                continue
            seen.add(nv.value % K)
            hq.heappush(reserved, node(rank=v.rank+nv.rank_to_add,value=nv.value,modK=nv.value % K))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
k=int(input())
def f(x):
    z=0
    while x>0:
        z+=x%10
        x=x//10
    return z
ans=10000
for i in range(1,10**7):
    ans=min(ans,f(i*k))
print(ans)

Submission status: Wrong Answer

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

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

q=deque()
q.append(1)
res[1]=''
res2=[INF]*(K)
res2[1]=0
while q:
    r=q.popleft()
    nr=(r+1)%K
    if res[nr]==INF:
        res[nr]=res[r]+'1'
        res2[nr]=res2[r]+1
        q.append(nr)
    nr=(10*r)%K
    if res[nr]==INF:
        res[nr]=res[r]+'0'
        res2[nr]=res2[r]
        q.appendleft(nr)
tmp=1
for i in res[0]:
    if i=='1':
        tmp+=1
    else:
        tmp*=10
        

print(sum([int(i) for i in list(str(tmp))]))

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.popleft()
    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:
K = int(input())
def f(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret
ans = f(K)
MAX = 10 ** 6
for i in range(1, MAX):
    now = f(i * K)
    ans = min(ans, now)
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
def f(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret
ans = f(K)
MAX = 10 ** 5
for i in range(1, MAX):
    now = f(i * K)
    ans = min(ans, now)
print(ans)

Submission status: Wrong Answer

Solution code:
k=int(input())
mn=999999
for i in range(1,1000000):
  x=str(k*i)
  sm=0
  for j in x:
    sm+=int(j)
  mn=min(mn,sm)
print(mn)

Submission status: Wrong Answer

Solution code:
k=int(input())
mn=999999
for i in range(1,100000):
  x=str(k*i)
  sm=0
  for j in x:
    sm+=int(j)
  mn=min(mn,sm)
print(mn)

Submission status: Wrong Answer

Solution code:
k=int(input())
mn=999999
for i in range(1,10000):
  x=str(k*i)
  sm=0
  for j in x:
    sm+=int(j)
  mn=min(mn,sm)
print(mn)

Submission status: Wrong Answer

Solution code:
k=int(input())
mn=999999
for i in range(1,500):
  x=str(k*i)
  sm=0
  for j in x:
    sm+=int(j)
  mn=min(mn,sm)
print(mn)

Submission status: Wrong Answer

Solution code:
k=int(input())
mn=999999
for i in range(1,20):
  x=str(k*i)
  sm=0
  for j in x:
    sm+=int(j)
  mn=min(mn,sm)
print(mn)

Submission status: Wrong Answer

Solution code:
N=int(input())
while True:
  if N%2==0:
    N=N//2
  else:
    break
while True:
  if N%5==0:
    N=N//5
  else:
    break
print(sum(list(map(int,list(str(N))))))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


k = I()
q = deque([1])
cost = [-1] * k
cost[1] = 1
while q:
    u = q.popleft()
    if cost[(u*10)%k]==-1:
        cost[u*10%k] = cost[u]
        q.appendleft(u*10%k)
    if cost[(u+1)%k]==-1:
        cost[(u + 1) % k]=cost[u]+1
        q.append((u + 1) % k)

print(cost[0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


k = I()
q = deque([1])
cost = [-1] * k
cost[1] = 1
while q:
    u = q.popleft()
    if cost[(u+1)%k]==-1:
        cost[(u + 1) % k]=cost[u]+1
        q.append((u + 1) % k)
    if cost[(u*10)%k]==-1:
        cost[u*10%k] = cost[u]
        q.appendleft(u*10%k)

print(cost[0])

Submission status: Wrong Answer

Solution code:
K=int(input())

def func(n):
  return sum(map(int,list(str(n))))

MIN=10**9
for i in range(10**6):
  tmp = func(K*(i+1))
  MIN = min(MIN,tmp)
  
print(MIN)

Submission status: Wrong Answer

Solution code:
K=int(input())

def func(n):
  return sum(map(int,list(str(n))))

MIN=10**9
for i in range(5*10**5):
  tmp = func(K*(i+1))
  MIN = min(MIN,tmp)
  
print(MIN)

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,100000):
  mina=min(mina,digitsum(N*i))
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,100):
  mina=min(mina,digitsum(N*i))
print(mina)

Submission status: Wrong Answer

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

K = I()

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

from collections import deque

q = deque([1])
d = [0]*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] == 0:
                d[a] = d[n]+b
                if b == 0:
                    q.append(a)
                else:
                    q.appendleft(a)

print(d[0])

Submission status: Wrong Answer

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 and i % 10 != 9:
        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 = [0]*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] == 0:
                d[a] = d[n]+b
                if b == 0:
                    q.append(a)
                else:
                    q.appendleft(a)

print(d[0])

Submission status: Wrong Answer

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 = [0]*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] == 0:
                d[a] = d[n]+b
                if b == 0:
                    q.append(a)
                else:
                    q.appendleft(a)

print(d[0])

Submission status: Wrong Answer

Solution code:
from math import sqrt,floor,gcd

k=int(input())
d=gcd(k,10)
while d>1:
  k=k//d
  d=gcd(k,10)

def digisum(n):
  if n<10:
    return n
  else:
    return digisum(n//10)+n%10

s=digisum(k)
a=1
for i in range(k):
  s=min(s,digisum(k-a))
  a=a*10 % k
  if a==1:
    break
print(s+1)

Submission status: Wrong Answer

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

K = I()

A = []
a = 1
for i in range(K+1):
    a *= 10
    a %= K
    A.append(K-a+1)

ans = 45
for a in A:
    ans = min(ans,sum(int(i) for i in str(a)))

print(ans)

Submission status: Wrong Answer

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

K = I()

ans = 45
for i in range(1,100000):
    ans = min(ans,sum(int(j) for j in str(K*i)))

print(ans)

Submission status: Wrong Answer

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)
    visited[s[0]] = True

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

    while True:
        c = q.popleft()

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

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

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


print(ans())

Submission status: Wrong Answer

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 - 1].append((1, i))
    graph[i].append((0, 10 * i % k))

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

Submission status: Wrong Answer

Solution code:
N = int(input())

small = 100000

A = []

for i in range (1, 1000000):
	A.append(int(N*i))
    
summa = 0
for i in range (0, 999999):
	summa = 0
	P = len(str(A[i]))
	for j in range (0, P):
		summa+= A[i]%10
		A[i]=A[i]//10
	if summa < small:
		small = summa
                    
print(small)

Submission status: Wrong Answer

Solution code:
N = int(input())

small = 100000

A = []

for i in range (1, 100000):
	A.append(int(N*i))
    
summa = 0
for i in range (0, 99999):
	summa = 0
	P = len(str(A[i]))
	for j in range (0, P):
		summa+= A[i]%10
		A[i]=A[i]//10
	if summa < small:
		small = summa
                    
print(small)