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:
s = input()
k = int(s)
pre = sum([int(c) for c in s])
ans = pre
a = k
for _ in range(10*k):
    a += k
    b = a
    now = 0
    while b > 0:
        r = b % 10
        if r: now += r
        b //= 10
    ans = min(ans, now)
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(s)
pre = sum([int(c) for c in s])
ans = pre
a = k
for _ in range(2*k):
    a += k
    b = a
    now = 0
    while b > 0:
        r = b % 10
        if r: now += r
        b //= 10
    ans = min(ans, now)
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(s)
# print(k)
pre = sum([int(c) for c in s])
ans = pre
a = k
for _ in range(k):
    a += k
    b = a
    now = 0
    while b > 0:
        r = b % 10
        if r: now += r
        b //= 10
    # print(a, now)
    ans = min(ans, now)
    # if pre == now: break

print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
k = int(s)
# print(k)
pre = sum([int(c) for c in s])
ans = pre
a = k
for _ in range(k):
    a += k
    b = a
    now = 0
    while b > 0:
        r = b % 10
        if r: now += r
        b //= 10
    # print(a, now)
    ans = min(ans, now)
    if pre == now: break

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
ans = 10**18

for i in range(1, 10**5 + 100):
  i *= K
  cnt = 0
  while i > 0:
    i, r = divmod(i, 10)
    cnt += r
  ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
ans = 10**18

for i in range(1, 10**6+1):
  i *= K
  cnt = 0
  while i > 0:
    i, r = divmod(i, 10)
    cnt += r
  ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
ans = 10**18

for i in range(1, K + 1):
  i *= K
  cnt = 0
  while i > 0:
    q, r = divmod(i, 10)
    cnt += r
    i = q
  ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
ans = 10**18

for i in range(1, K + 1):
  i *= K
  cnt = 0
  while i > 0:
    q, r = divmod(i, 10)
    cnt += r
    i = r
  ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

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


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

        v1 = E[n][0]
        if used[v1] == 0:
            used[v1] = 1
            q.append((v1, cost+1))

        v10 = E[n][1]
        if used[v10] == 0:
            used[v10] = 1
            q.appendleft((v10, cost))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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


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

        v1 = E[n][0]
        if used[v1] == 0:
            used[v1] = 1
            q.append((E[n][0], cost+1))

        v10 = E[n][1]
        if used[v10] == 0:
            used[v10] = 1
            q.appendleft((E[n][1], cost))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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])
print(m)

Submission status: Wrong Answer

Solution code:
K=int(input())
ans=float("inf")
for i in range(1,11):
    n=K*i
    n=str(n)
    val=0
    for j in range(len(n)):
        val+=int(n[j])
    ans=min(ans,val)
print(ans)

Submission status: Wrong Answer

Solution code:
K = input()
keta = len(K)
K = int(K)
ans = 10000000000
for i in range(1, 10**keta):
    n = K * i
    kakui_sum = 0
    for j in range(100):
        kakui_sum += n % 10
        n = n // 10
        if n == 0:
            break

    ans = min(ans, kakui_sum)

print(ans)

Submission status: Wrong Answer

Solution code:
K = input()
keta = len(K)
K = int(K)
ans = float('inf')
for i in range(1, 10**keta):
    n = K * i
    n = str(n)
    kakui_sum = 0
    for kakui in n:
        kakui_sum += int(kakui)
    ans = min(ans, kakui_sum)
print(ans)

Submission status: Wrong Answer

Solution code:
K = input()
numK = int(K)
leastsum = 0
k = 0
for i in K:
    leastsum += int(i)
while True:
    k += 1
    numK *= k
    K = str(numK)
    newsum = 0
    for i in K:
        newsum += int(i)
    leastsum = newsum if leastsum > newsum else leastsum
    if len(K) > leastsum:
        break
print(leastsum)

Submission status: Wrong Answer

Solution code:
K = input()
numK = int(K)
leastsum = 0
k = 1
for i in K:
    leastsum += int(i)
while True:
    k += 1
    numK *= k
    K = str(numK)
    newsum = 0
    for i in K:
        newsum += int(i)
    leastsum = newsum if leastsum > newsum else leastsum
    if len(K) > leastsum:
        break
print(leastsum)

Submission status: Wrong Answer

Solution code:
K = input()
numK = int(K)
leastsum = 0
k = 1
for i in K:
    leastsum += int(i)
while(len(K)<leastsum):
    k += 1
    numK *= k
    K = str(numK)
    newsum = 0
    for i in K:
        newsum += int(i)
    leastsum = newsum if leastsum > newsum else leastsum
print(leastsum)

Submission status: Wrong Answer

Solution code:
K=int(input())

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

answer=10**9
for i in range(1,10):
  answer=min(answer,sum_digit(i*K))

print(answer)

Submission status: Wrong Answer

Solution code:
k = int(input())
Min = sum([int(i) for i in str(k * 2)])
for j in range(3, 10000):
    Sum = sum([int(i) for i in str(k * j)])
    if Min > Sum:
        Min = Sum
print(Min)

Submission status: Wrong Answer

Solution code:
k = int(input())
Min = sum([int(i) for i in str(k * 2)])
for j in range(3, 1000):
    Sum = sum([int(i) for i in str(k * j)])
    if Min > Sum:
        Min = Sum
print(Min)

Submission status: Wrong Answer

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([])
    i=0
    while pow(10,i,K) not in mod:
        mod.add(pow(10,i,K))
        i+=1

    mod=list(mod)
    mod.sort(reverse=True)

    ans=float('inf')
    for i in range(1,11):
        X=i*K
        test=0
        for j in range(0,len(mod)):
            test+=X//mod[j]
            X%=mod[j]
        ans=min(ans,test)
    print(ans)

Submission status: Wrong Answer

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([])
    i=0
    while pow(10,i,K) not in mod:
        mod.add(pow(10,i,K))
        i+=1

    mod=list(mod)
    mod.sort(reverse=True)

    ans=float('inf')
    for i in range(1,10):
        X=i*K
        test=0
        for j in range(0,len(mod)):
            test+=X//mod[j]
            X%=mod[j]
        ans=min(ans,test)
    print(ans)

Submission status: Wrong Answer

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([])
    i=0
    while pow(10,i,K) not in mod:
        mod.add(pow(10,i,K))
        i+=1

    mod=list(mod)
    mod.sort(reverse=True)

    ans=float('inf')
    for i in range(1,9):
        X=i*K
        test=0
        for j in range(0,len(mod)):
            test+=X//mod[j]
            X%=mod[j]
        ans=min(ans,test)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


############ ---- Input Functions ---- ############
def in_int():
    return (int(input()))


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


def in_str():
    s = input()
    return (list(s[:len(s) - 1]))


def in_ints():
    return (map(int, input().split()))

n = in_int()


while n%2 == 0 :
    n = n//2

while n%5 == 0 :
    n = n // 5


ans = sum(list(map(int , list(str(n)))))

for i in range(1, n):
    x = sum(list(map(int , list(str(n*i)))))
    ans  = min(x, ans)
    
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


############ ---- Input Functions ---- ############
def in_int():
    return (int(input()))


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


def in_str():
    s = input()
    return (list(s[:len(s) - 1]))


def in_ints():
    return (map(int, input().split()))

n = in_int()


while n%2 == 0 :
    n = n//2

while n%5 == 0 :
    n = n // 5


ans = sum(list(map(int , list(str(n)))))

for i in range(1, 10):
    x = sum(list(map(int , list(str(n*i)))))
    ans  = min(x, ans)

Submission status: Wrong Answer

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

Solution code:
import heapq
def main():
    k= int(input())
    brdict = {}
    for i in range(1,k):
        if i==k-1: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: Wrong Answer

Solution code:
import heapq
def main():
    k=int(input())
    if k==2:print(1)
    elif k==3:print(3)
    elif k==8:print(1)
    elif k==9:print(9)
    else:
        brdict = {}
        for i in range(1,k):
            if i==k-1:brdict[i] = [(0,1)]
            else:
                brdict[i] = [((i*10)%k,0)]
                if (i*10)%k!=i+1:brdict[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):
            (fnode,fcost) = 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,(br[0],cost[br[0]]))
        print(cost[0])
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
k = int(input())
def check(k):
  result = 0
  for i in range(len(str(k))):
    result += int(str(k)[i])
  return result
result = k
while True:
  if check(result) < check(result*2):
    break
  else:
    result = result * 2
  
print(check(result))

Submission status: Wrong Answer

Solution code:
K = int(input())

ans = 1e9
for i in range(1,400000):
    tmp = sum(list(map(int,str(K*i))))
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
K = input()
N = len(K)
K = int(K)

if K == 10 ** 5:
    print(1)
    exit()

ans = float('inf')
num = K
for i in range(10 ** N):
    num += K
    t = num
    cnt = 0
    while t > 0:
        cnt += t % 10
        t //= 10
    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
K = input()
N = len(K)
K = int(K)

if K == 10 ** 5:
    print(1)
    exit()

ans = float('inf')
num = 0
for i in range(10 ** (N + 1)):
    num += K
    t = num
    cnt = 0
    while t > 0:
        cnt += t % 10
        t //= 10
    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
K = input()
N = len(K)
K = int(K)

if K == 10 ** 5:
    print(1)
    exit()

ans = float('inf')
num = 0
for i in range(10 ** N):
    num += K
    t = num
    cnt = 0
    while t > 0:
        cnt += t % 10
        t //= 10
    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, = I()
ans = sum([int(j) for j in str(n)])
for i in range(n, 1000000 * n + 1, n):
    ans = min(ans, sum([int(j) for j in str(i)]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, = I()
l = len(str(n))
ans = sum([int(j) for j in str(n)])
for i in range(n, 10 ** l * n, n):
    ans = min(ans, sum([int(j) for j in str(i)]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, = I()
l = len(str(n))
ans = sum([int(j) for j in str(n)])
for i in range(n, l * n, n):
    ans = min(ans, sum([int(j) for j in str(i)]))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

y = []
for i in range(9):
  x = (i+1)*n
  y.append(sum(list(map(int, str(x)))))
  
print(min(y))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    def calc(a):
        nn=len(str(a))
        temp=0
        for i in range(nn):
            temp+=a%10
            a//=10
        return temp
    
    S=input()
    N=len(S)
    K=int(S)
    
    #a桁なら，10^i までかければ良い？,K=10**nだとかける数は1だけで良い
    t=pow(10,N)
    if K==10**5:
        t=2
    ans=100
    for i in range(1,t):
        ans=min(ans,calc(K*i))
    print(ans)   

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = sum(map(int,str(n)))
for i in range(1,100001):
    ans = min(ans,sum(map(int,str(n*i))))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = sum(map(int,str(n)))
for i in range(1,10001):
    ans = min(ans,sum(map(int,str(n*i))))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
mins = [1000 for i in range(n+1)]
used = [0 for i in range(n+1)]
deq = deque()
deq.append((1,1))
while deq:
  x,cnt = deq.popleft()
  mins[x] = cnt
  used[x] = 1
  if used[10*x%n] == 0:
    deq.appendleft((10*x%n,cnt))
  if used[(x+1)%n] == 0:
    deq.append(((x+1)%n,cnt+1))
print(mins[0])

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
mins = [100 for i in range(n+1)]
used = [0 for i in range(n+1)]
deq = deque()
deq.append((1,1))
while deq:
  x,cnt = deq.popleft()
  mins[x] = cnt
  used[x] = 1
  if used[10*x%n] == 0:
    deq.appendleft((10*x%n,cnt))
  if used[(x+1)%n] == 0:
    deq.append(((x+1)%n,cnt+1))
print(mins[0])

Submission status: Wrong Answer

Solution code:
from collections import deque
K = int(input())
cost = [-1] * K
cost[1] = 1
deq = deque([1])
while deq:
    x = deq.popleft()
    if x == 0: break
    d = cost[x]
    for y, c in [(10*x%K, 0), ((x+1)%K, 1)]:
        if cost[y] < 0:
            cost[y] = d + c
            if c: deq.append(y)
            else: deq.appendleft(y)
print(cost[0])

Submission status: Wrong Answer

Solution code:
def f(x): return sum(int(s) for s in str(x))
K = int(input())
while K%2==0: K//=2
while K%5==0: K//=5
if K in [1,3]:
    print(K)
    exit()
a={1:1,3:7,7:3,9:9}[K%10]
inv10 = pow(10, K-2, K)
D = K*a//10
print(f(min(D*pow(inv10,i,K)%K for i in range(K-1)))+1)
# prod = min(sum(f(i*K) for i in range(1,10000))
# dc = 1
# ss = set()
# for i in range(K):
#     if i in ss: continue
#     sss = set()
#     for j in range(K):
#         m=i*inv10**j%K
#         if m in sss:
#             break
#         else:
#             sss.add(m)
#     if D in sss:
#         break
#     else:
#         ss.update(sss)
# print(i+1)



# digit = []
# R0 = {(-K*i)%10: i for i in range(10)}
# prev = set([D])
# while True:
#     if D%10:
#         digit.append(1)
#     if sum(digit) >= prod:

#         break
#     D //= 10
#     if D == 1:
#         digit.append(1)
#         break
#     a = R0[D%10]
#     D += K*a
#     if D in prev:
#         a = R0[(D-1)%10]
#         D += K*a
#         prev.clear()
#     prev.add(D)
# print(min(sum(digit), prod))

Submission status: Wrong Answer

Solution code:
def f(x): return sum(int(s) for s in str(x))
K = int(input())
while K%2==0: K//=2
while K%5==0: K//=5
if K in [1,3]:
    print(K)
    exit()
a={1:1,3:7,7:3,9:9}[K%10]
inv10 = pow(10, K-2, K)
D = K*a//10
print(f(min(D*inv10**i%K for i in range(K-1)))+1)

Submission status: Wrong Answer

Solution code:
K = int(input())
while K%2==0: K//=2
while K%5==0: K//=5
if K in [1,3]:
    print(K)
    exit()
dc = 0
a={1:1,3:7,7:3,9:9}[K%10]
R0 = {(-K*i)%10: i for i in range(10)}
prod = min(sum(int(s) for s in str(i*K)) for i in range(1,10000))
D = K*a
prev = set([D])
while True:
    if D%10:
        dc += 1
    if dc >= prod:
        break
    D //= 10
    if D == 1:
        dc += 1
        break
    a = R0[D%10]
    D += K*a
    if D in prev:
        a = (R0[(D-1)%10])%10
        D += K*a
        prev.clear()
    prev.add(D)
print(min(dc, prod))

Submission status: Wrong Answer

Solution code:
K = int(input())
while K%2==0: K//=2
while K%5==0: K//=5
if K in [1,3]:
    print(K)
    exit()
dc = 0
a={1:1,3:7,7:3,9:9}[K%10]
R0 = {(-K*i)%10: i for i in range(10)}
prod = min(sum(int(s) for s in str(i*K)) for i in range(1,10000))
D = K*a
prev = set([D])
while True:
    if D%10:
        dc += 1
    if dc >= prod:
        break
    D //= 10
    if D == 1:
        dc += 1
        break
    a = R0[D%10]
    D += K*a
    if D in prev:
        prod = min(prod, dc+min(prev))
        a = (R0[D%10]+1)%10
        D += K*a
        prev.clear()
    prev.add(D)
print(min(dc, prod))

Submission status: Wrong Answer

Solution code:
K = int(input())
while K%2==0: K//=2
while K%5==0: K//=5
if K in [1,3]:
    print(K)
    exit()
dc = 0
a={1:1,3:7,7:3,9:9}[K%10]
R0 = {(-K*i)%10: i for i in range(10)}
prod = min(sum(int(s) for s in str(i*K)) for i in range(1,10000))
D = K*a
prev = set([D])
pD = D
while True:
    if D%10:
        dc += 1
    if dc >= prod:
        break
    D //= 10
    if D == 1:
        dc += 1
        break
    a = R0[D%10]
    D += K*a
    if D in prev:
        D = pD
        a = (R0[D%10]+1)%10
        D += K*a
        pD = D
        prev = set()
    prev.add(D)
print(min(dc, prod))

Submission status: Wrong Answer

Solution code:
K = int(input())
while K%2==0: K//=2
while K%5==0: K//=5
if K in [1,3]:
    print(K)
    exit()
dc = 0
a={1:1,3:7,7:3,9:9}[K%10]
R0 = {(-K*i)%10: i for i in range(10)}
prod = min(sum(int(s) for s in str(i*K)) for i in range(1,1000))
D = K*a
prev = set()
pD = D
while True:
    if D%10:
        dc += 1
    if dc >= prod:
        break
    D //= 10
    if D == 1:
        dc += 1
        break
    a = R0[D%10]
    D += K*a
    if D in prev:
        D = pD
        a = R0[D%10]+1
        D += K*a
        pD = D
        prev = set()
    prev.add(D)
print(min(dc, prod))

Submission status: Wrong Answer

Solution code:
def bi_power(n):
    rtn=0
    while n%2==0:
        n//=2
        rtn+=1
    return rtn

n=int(input())
print(n//(2**bi_power(n)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
k=int(input())
t=[0]*k
t[1]=1
q=deque()
q.append(1)
while q:
    p=q.popleft()
    if p==0:
        print(t[0])
        break
    if not t[(p*10)%k]:
        t[(p*10)%k]=t[p]
        q.appendleft((p*10)%k)
    if not t[(p+1)%k]:
        t[(p+1)%k]=t[p]+1
        q.append((p+1)%k)

Submission status: Wrong Answer

Solution code:
k=int(input())
t=[0]*k
t[1]=1
q=[1]
while q:
    p=q.pop(0)
    if p==0:
        break
    if t[p]:
        if not t[(p*10)%k]:
            t[(p*10)%k]=t[p]
            q.insert(0,(p*10)%k)
        if not t[(p+1)%k]:
            t[(p+1)%k]=t[p]+1
            q.append((p+1)%k)
print(t[0])

Submission status: Wrong Answer

Solution code:
k=int(input())
t=[-1]*k
t[1]=1
q=[1]
while q:
    p=q.pop(0)
    if p==0:
        break
    if t[(p*10)%k]==-1:
        t[(p*10)%k]=t[p]
        q.insert(0,(p*10)%k)
    if t[(p+1)%k]==-1:
        t[(p+1)%k]=t[p]+1
        q.append((p+1)%k)
print(t[0])

Submission status: Wrong Answer

Solution code:
k=int(input())
ans=10**9
seen=set()
for i in range(1,10**6):
  s=k*i
  v=0
  while s>0:
    v+=s%10
    s//=10
  if ans>v:
    ans=v
  
print(ans)

Submission status: Wrong Answer

Solution code:
k=int(input())
ans=10**9
seen=set()
i=1
while True:
  s=k*i
  v=0
  while s>0:
    v+=s%10
    s//=10
  if ans>v:
    ans=v
  elif ans==v:
    break
  i+=1
  
print(ans)

Submission status: Wrong Answer

Solution code:
k=int(input())
ans=10**9
for i in range(1,1000):
  s=k*i
  v=0
  while s>0:
    v+=s%10
    s//=10
  if ans>v:
    ans=v
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
G = [[] for _ in range(K)]
for i in range(K):
    G[i].append(((i+1)%K, 1))
    G[i].append(((i*10)%K, 0))
from collections import deque
que = deque([1])
dist = [-1]*K
dist[1] = 0
while que:
    v = que.pop()
    d = dist[v]
    for nv, c in G[v]:
        if dist[nv]>=0:
            continue
        if c == 0:
            que.append(nv)
            dist[nv] = d
        else:
            que.appendleft(nv)
            dist[nv] = d+1
print(dist[0]+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
num=int((n)**(1/2))
print((num)**2)

Submission status: Wrong Answer

Solution code:
N=int(input())
min_=10**10
for i in range(1,10**8):
    l=list(map(int, str(N*i)))
    if min_<len(l):
        break
    min_=min(min_,sum(l))
print(min_)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import deque
def resolve():
    k=int(input())
    E=[[] for _ in range(k)]
    for i in range(k):
        E[i].append(((i+1)%k,1))
        E[i].append(((10*i)%k,0))

    # 0-1 BFS
    dist=[INF]*k
    dist[1]=0
    Q=deque([1])
    while(Q):
        v=Q.popleft()
        for nv,w in E[v]:
            if(dist[nv]!=INF): continue
            dist[nv]=dist[v]+w
            if(w==0): Q.appendleft(nv)
            else: Q.append(nv)
    print(dist[0]+1)
resolve()

Submission status: Wrong Answer

Solution code:
#D-small multiple
k=int(input())
maxi=10**10
for i in range(1,5*10**5+1):
    a=str(k*i)
    sums=0
    for j in range(len(a)):
        sums+=int(a[j])
    maxi=min(maxi,sums)
print(maxi)

Submission status: Wrong Answer

Solution code:
#D-small multiple
k=int(input())
maxi=10**10
for i in range(1,10**5+1):
    a=str(k*i)
    sums=0
    for j in range(len(a)):
        sums+=int(a[j])
    maxi=min(maxi,sums)
print(maxi)

Submission status: Wrong Answer

Solution code:
K = int(input())

def Sum(n):
    m = str(n)
    res = 0
    for i in range(len(m)):
        res += int(m[i])
    return res

while K%2 == 0:
    K //= 2
while K%5 == 0:
    K //= 5
    
ans = 100
c = K
for i in range(10**5):
    ans = min(ans, Sum(c))
    c += K
    
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

def Sum(n):
    m = str(n)
    res = 0
    for i in range(len(m)):
        res += int(m[i])
    return res

while K%2 == 0:
    K //= 2
while K%5 == 0:
    K //= 5
    
print(Sum(K))

Submission status: Wrong Answer

Solution code:
K = int(input())

def Sum(n):
    m = str(n)
    res = 0
    for i in range(len(m)):
        res += int(m[i])
    return res

if K == 10**5:
    ans = 1
else:
    ans = 100
    for i in range(1, 10**(len(str(K))+1)):
        ans = min(ans, Sum(K*i))
        
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

def Sum(n):
    m = str(n)
    res = 0
    for i in range(len(m)):
        res += int(m[i])
    return res

if K == 10**5:
    ans = 1
else:
    ans = 100
    for i in range(1, 10**len(str(K))):
        ans = min(ans, Sum(K*i))
        
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

def Sum(n):
    m = str(n)
    res = 0
    for i in range(len(m)):
        res += int(m[i])
    return res

ans = 10**7
for i in range(1, 10**6):
    ans = min(ans, Sum(K*i))
    if len(str(K*i)) > ans:
        break
        
print(ans)

Submission status: Wrong Answer

Solution code:
def digit_sum(n):
    ret = 0
    while n:
        ret += n%10
        n //= 10
    return ret
def main():
    k = int(input())
    ans = float("inf")
    for i in range(1, 10**6+1):
        ans = min(ans, digit_sum(i*k))

    print(ans)
main()

Submission status: Wrong Answer

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

k = int(input())
ans = float("inf")
for i in range(1, 10**5+1):
    ans = min(ans, digit_sum(i*k))

print(ans)

Submission status: Wrong Answer

Solution code:
K=int(input())
ans=eval('+'.join(str(K)))
for i in range(2,10):
    ans=min(ans,eval('+'.join(str(K*i))))
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import random
s = input()
c = 0
for i in s:
  c += int(i)
print(random.randint(0, c))

Submission status: Wrong Answer

Solution code:
mini=10**9 
k=int(input())
p=10**6 
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: Wrong Answer

Solution code:
mini=10**9 
k=int(input())
p=10**5 
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: Wrong Answer

Solution code:
k = int(input())
a,b ,li=1, 500001,[]
ks = str(k)
n = 0
while a <= b:
    ks = str(k)
    ks = int(ks)*a
    ks = str(ks)
    for i in ks:
        n += int(i)
    li.append(n)
    n = 0
    a += 1
print(min(li))