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 defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    K = int(input())
    dp = [INF] * K
    dp[1] = 1

    for i in range(1, K):
        dp[(i + 1) % K] = min(dp[(i + 1) % K], dp[i] + 1)
        dp[(i * 10) % K] = min(dp[(i * 10) % K], dp[i])

    print(dp[0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
K = int(input())
def digit_sum(K):
  cnt = 0
  for s in str(K):
    cnt += int(s)
  return cnt
while K % 2 == 0:
  K //= 2
while K % 5 == 0:
  K //= 5
ans = digit_sum(K)
for i in range(2, 10):
  ans = min(digit_sum(K * i), ans)
print(digit_sum(K))

Submission status: Wrong Answer

Solution code:
K = int(input())
def digit_sum(K):
  cnt = 0
  for s in str(K):
    cnt += int(s)
  return cnt
while K % 2 == 0:
  K //= 2
while K % 5 == 0:
  K //= 5
print(digit_sum(K))

Submission status: Wrong Answer

Solution code:
from collections import deque
k = int(input())
x = [50 for i in range(k)]
x[1],q = 0,deque()
q.append(1)
while q:
	n = q.pop()
	m = n	
	while 1:
		m2 = (m*10)%k
		if x[m2]==50:
			x[m2],m = x[m],m2
			q.append(m)
		else: break
	if x[(n+1)%k]==50:
		x[(n+1)%k] = x[n]+1
		q.appendleft((n+1)%k)
print(x[0]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
k = int(input())
x = [50 for i in range(k)]
x[1],q = 0,deque()
q.append(1)
while q:
	n = q.pop()
	if x[(n+1)%k]==50:
		x[(n+1)%k] = x[n]+1
		q.appendleft((n+1)%k)
	while 1:
		m = (n*10)%k
		if x[m]==50:
			x[m],n = x[n],m
			q.append(n)
		else: break
print(x[0]+1)

Submission status: Wrong Answer

Solution code:
k=int(input())
f=lambda x:sum(map(int,str(x)))
v=min(map(f,range(k,1+k*k*k,k)))
print(v)

Submission status: Wrong Answer

Solution code:
k=int(input())
f=lambda x:sum(map(int,str(x)))
v=min(map(f,range(k,1+k*k,k)))
print(v)

Submission status: Wrong Answer

Solution code:
from time import monotonic
begin=monotonic()
def sum(i):
    s=str(i)
    ret=0
    for c in s:
        ret+=int(c)
    return ret

n=int(input())
res=sum(n)
i=2
while True:
    x=n*i
    res=min(res,sum(x))
    i+=1
    if monotonic()-begin>1.9:
        break
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

K = int(input())


lines = defaultdict(set)
for i in range(K-1):
	lines[i].add((i+1,1))
lines[K-1].add((0,1))

for s in range(K-1):
	t = s*10 % K
	if s != t:
		lines[s].add((t,0))

def search (s,w_0): #s->t
	global weight
	global q

	for line in list(lines[s]):
		t = line[0]
		w = w_0 + line[1]
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w

s = 1
weight = [INF]*K
weight[s] = 0
q = [[0,s]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

print(weight[0]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(K:int) -> list:
    hasChecked = [False]*(K+1)
    cost_list = [0]*(K+1)
    cost_list[1] = 1
    
    que = deque([(cost_list[1], 1)])
    
    while que:
        cost, res = que.popleft()
        if hasChecked[res]:
            continue
        
        hasChecked[res] = True

        
        if not hasChecked[10*res%K]:
            cost_list[10*res%K] = cost
            que.appendleft((cost_list[10*res%K], 10*res%K))
            
        if not hasChecked[(res+1)%K]:
            cost_list[(res+1)%K] = cost+1
            que.append((cost_list[(res+1)%K], (res+1)%K))
            
            
    return cost_list


K = int(input())
cost_list = bfs(K)
print(cost_list[0])

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(K:int) -> list:
    cost_list = [0]*(K+1)
    cost_list[1] = 1
    
    que = deque([(cost_list[1], 1)])
    
    while que:
        cost, res = que.popleft()
        res = res%K
    
        if cost_list[10*res%K] == 0:
            cost_list[10*res%K] = cost
            que.appendleft((cost_list[10*res%K], 10*res%K))
            
        if cost_list[(res+1)%K] == 0:
            cost_list[(res+1)%K] = cost+1
            que.append((cost_list[(res+1)%K], (res+1)%K))
            
            
    return cost_list


K = int(input())
cost_list = bfs(K)
print(cost_list[0])

Submission status: Wrong Answer

Solution code:
a=int(input())

b = []

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

print(min(b))

Submission status: Wrong Answer

Solution code:
def digit_sum(n:int) -> int:
    ans = 0
    while n>0:
        ans += n%10
        n //= 10
        
    return ans

def judge(n:int) -> int:
    pow2 = [2**i for i in range(21)]
    pow5 = [5**i for i in range(11)]
    pow10 = [10**i for i in range(7)]
    
    if n%99999 == 0:
        return 9*5
    elif n%9999 == 0:
        return 9*4
    elif n%999 == 0:
        return 9*3
    elif n%99 == 0:
        return 9*2
    elif n%33 == 0:
        return 6
    elif n in pow2:
        return 1
    elif n in pow5:
        return 1
    elif n in pow10:
        return 1
    else:
        ans = 10**10
        for i in range(1,100000):
            ans = min(ans, digit_sum(i*n))
            
        return ans

n = int(input())

        
print(judge(n))

Submission status: Wrong Answer

Solution code:
ktw=lambda x:sum(int(i) for i in list(str(x)))
a=int(input())
while True:
  if a % 2 ==0:
    a=a//2
  elif a % 5==0:
    a=a//5
  else:
    break
    
m=ktw(a)
for i in range(2,10**5):
  m=min(m,ktw(a*i))
print(m)

Submission status: Wrong Answer

Solution code:
def m():
    def solve(p):
        a = 0
        while p != 0:
            a += p % 10
            p //= 10
        return a
    k = int(input())
    MAX = solve(k)
    ans = 9999999999
    for i in range(1, 9):
        ans = min(ans, solve(k*i))

    return ans

print(m())

Submission status: Wrong Answer

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

node1, node2, weight = [], [], []

def add_edge(n1, n2, w):
    node1.append(n1)
    node2.append(n2)
    weight.append(w)

for i in range(K - 1):
    add_edge(i, i + 1, 1)
    add_edge(i, (i * 10) % K, 10**(-16))

add_edge(K - 1, 0, 1)
add_edge(K - 1, ((K - 1) * 10) % K, 10**(-16))
G = csr_matrix((weight, (node1, node2)), shape=(K, K))
d = dijkstra(G, directed=True, indices=1)
print(int(d[0]) + 1)

Submission status: Wrong Answer

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

node1, node2, weight = [], [], []

def add_edge(n1, n2, w):
    node1.append(n1)
    node2.append(n2)
    weight.append(w)

for i in range(K-1):
    add_edge(i, i + 1, 1)
    add_edge(i, (i * 10) % K, 10**(-8))

add_edge(K - 1, 0, 1)
add_edge(K - 1, ((K - 1) * 10) % K, 10**(-8))
G = csr_matrix((weight, (node1, node2)), shape=(K, K))
d = dijkstra(G, directed=True, indices=1)
print(int(d[0]) + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

K = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
for i in range(K - 1):
    g.add_edge(i, i + 1, 1)
    j = (i * 10) % K
    if i != j:
        g.add_edge(i, j, 0)
g.add_edge(K - 1, 0, 1)

d = Dijkstra(g, 1)
print(d.shortest_distance(0) + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

K = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
for i in range(K - 1):
    g.add_edge(i, i + 1, 1)
    g.add_edge(i, i * 10 % K, 0)
g.add_edge(K - 1, 0, 1)

d = Dijkstra(g, 1)
print(d.shortest_distance(0) + 1)

Submission status: Wrong Answer

Solution code:
K = int(input())

ans = float('inf')
for i in range(1, 10 ** 5):
    x = K * i
    ans = min(ans, sum(map(int, str(x))))
print(ans)

Submission status: Wrong Answer

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):
    def s(n):
        r = 0
        while n != 0:
            r += n % 10
            n //= 10

        return r

    ans = sys.maxsize
    for i in range(1, 1000000):
        ans = min(ans, s(K*i))

    return ans


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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):
    def s(n):
        r = 0
        while n != 0:
            r += n % 10
            n //= 10

        return r

    ans = sys.maxsize
    for i in range(1, 10000):
        ans = min(ans, s(K*i))

    return ans


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
  INF = 10 ** 20
  k = int(input())
  n = 10 ** len(str(k))
  ans = INF
  for i in range(1, n + 1):
    ans = min(ans, sum(map(int, list(str(k * i)))))
  print(ans)

main()

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20
k = int(input())
n = 10 ** len(str(k))
ans = INF
for i in range(1, n + 1):
  ans = min(ans, sum(list(map(int, str(k * i)))))
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
def keta(x):
  wa = 0
  while x>0:
    wa += x%10
    x = x//10
  return wa
ans = keta(K)
for i in range(2,100):
  ans = min(ans,keta(K*i))
print(ans)

Submission status: Wrong Answer

Solution code:
K =int(input())
A = [1]
B = [[x,0] for x in range(K)]
C = [1]
B[1][1] = 1
while B[0][1] == 0:
    for x in C:
        b = (10*x)%K
        c = (x+1)%K
        if b == 0:
            B[0][1] = B[x][1]
            break
        elif c == 0:
            B[0][1] = B[x][1] + 1
            break
        else:
            if b in C:
                pass
            else:
                C += [b]
                B[b][1] = B[x][1]
            if c in C:
                pass
            else:
                C += [c]
                B[c][1] = B[x][1] + 1
print(B[0][1])

Submission status: Wrong Answer

Solution code:
K = int(input())

ans = float('inf')
for i in range(1, 100000):
    x = sum(map(int, str(K * i)))
    ans = min(ans, x)
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

ans = float("inf")
tmp = 0
for i in range(800000):
    tmp += K
    tmpstr = str(tmp)
    a = 0
    for c in tmpstr:
        a += int(c)
        if a >= ans:
            continue
    ans = a
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

ans = float("inf")
tmp = 0
for i in range(100000):
    tmp += K
    tmpstr = str(tmp)
    a = 0
    for c in tmpstr:
        a += int(c)
    ans = min(ans, a)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    K = int(input())
    cost = [0 for _ in range(9)]
    for i in range(1,10):
        k = K*i
        for kk in str(k):
            cost[i-1] += int(kk)
    return min(cost)

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())

def digit_sum(value):
    total = 0
    while value:
        total += value % 10
        value = int(value/10)
    return total

minimamu = 99999999999

for k in range(2,10**5):
    minimamu = min(minimamu,digit_sum(k*n))

print(minimamu)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 9999999
for i in range(1, 100001):
    p = 0
    r = str(n * i)
    for i in range(len(r)):
        p += int(r[i])
    ans = min(ans, p)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 9999999
for i in range(1, 11):
    p = 0
    r = str(n * i)
    for i in range(len(r)):
        p += int(r[i])
    ans = min(ans, p)
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
multiple = 100
for i in range(1,100000):
    s = str(K*i)
    n = 0
    for m in range(len(s)):
        n += int(s[m])
    multiple =min(multiple,n)
    

print(multiple)

Submission status: Wrong Answer

Solution code:
K = int(input())

m = 0
K_str = str(K)
for i in range(len(K_str)):
    m += int(K_str[i])

score = 100
c = 1
k = 0
ans = m
while c < 100:
    k = K*c
    kstr = str(k)
    m_k = 0
    for j in range(len(kstr)):
        m_k += int(kstr[j])
    ans = min(m_k,ans)
    c += 1
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

m = 0
K_str = str(K)
for i in range(len(K_str)):
    m += int(K_str[i])

score = 100
c = 1
k = 0
while c < 100:
    k = K*c
    kstr = str(k)
    m_k = 0
    for j in range(len(kstr)):
        m_k += int(kstr[j])
    ans = min(m_k,m)
    c += 1

print(ans)

Submission status: Wrong Answer

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.8):
    for x in range(100):
        P = KSum(K*j)
        if m > P:
            m = P
        j += 1
print(m)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# Set 2 dimension list
def dim2input(N):
    li = []
    for _ in range(N):
        li.append(list(map(int, input())))
    return li

# --------------------------------------------

dp = None

def sum_of_digit(k):
    k_str = str(k)
    _sum = 0

    for k_letter in k_str:
        _sum += int(k_letter)

    return _sum

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

    tmp_min = 10**10
    for multiplier in range(1, 100000):
        tmp_min = min(sum_of_digit(k * multiplier), tmp_min)

    print(tmp_min)

main()

Submission status: Wrong Answer

Solution code:
def getSum(K):
    ans=0
    digits=0
    while K>0:
        ans+=K%10
        K=int(K/10)
        digits+=1
    return ans,digits

K=int(input())
minSum, digits=getSum(K)
MAX=0xffffffff
tmpK=K+K

while tmpK<MAX:
    tmpSum, digits=getSum(tmpK)
    if minSum <= digits:
        break
    if tmpSum < minSum:
        minSum=tmpSum
    tmpK+=K

print(minSum)

Submission status: Wrong Answer

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

if ans>10**50:
    raise ValueError("error!")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def solve(K):
    checked = [False] * K
    def calc(x):
        while not checked[x]:
            checked[x] = True
            yield x
            x = (x * 10) % K
    i = 0
    xs = [0]
    while 1:
        i += 1
        ys = []
        for x in xs:
            y = (x + 1) % K
            if y == 0:
                return i
            ys += calc(y)
        xs = ys

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

Submission status: Wrong Answer

Solution code:
from collections import deque
K = int(input())
dist = {1: 1}

deq = deque([1])
while deq:
    v = deq.popleft()
    # x10: +0
    w = (10 * v) % K
    if w not in dist:
        dist[w] = dist[v]
        deq.appendleft(w)
    # +1: +1
    w = (v + 1) % K
    if w not in dist:
        dist[w] = dist[v] + 1
        deq.append(w)
print(dist[0])

Submission status: Wrong Answer

Solution code:
from collections import deque
K = int(input())
dist = {1: 1}

deq = deque([1])
while deq:
    v = deq.popleft()
    # +1: +1
    w = (v + 1) % K
    if w not in dist:
        dist[w] = dist[v] + 1
        deq.append(w)
    # x10: +0
    w = (10 * v) % K
    if w not in dist:
        dist[w] = dist[v]
        deq.appendleft(w)
print(dist[0])

Submission status: Wrong Answer

Solution code:
from collections import deque
K = int(input())
dist = {1: 1}

ans = -1
deq = deque([1])
while deq:
    v = deq.popleft()
    # +1: +1
    w = (v + 1) % K
    if w not in dist:
        dist[w] = dist[v] + 1
        deq.append(w)
        if w == 0: break
    # x10: +0
    w = (10 * v) % K
    if w not in dist:
        dist[w] = dist[v]
        deq.appendleft(w)
        if w == 0: break
print(dist[0])

Submission status: Wrong Answer

Solution code:
K=int(input())
def f(x):
    ret=0
    while x > 0:
        ret+=x%10
        x//=10
    return ret

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

print(min(a))

Submission status: Wrong Answer

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.8):
    P = KSum(K*j)
    if m > P:
        m = P
    j += 1

print(m)

Submission status: Wrong Answer

Solution code:
def F(i):
    """
    整数iの各桁の和
    """
    i0=i
    q=0
    while i0 != 0:
        q += i0%10
        i0 = i0//10
    return q

def F2(i):
    """
    整数iの桁数
    """
    i0=i
    k=0
    while i0!=0:
        k+=1
        i0=i0//10
    return k

k=int(input())
if F(k) == 1:
    print('1')
else:
    k0 = F2(k)
    L=F(k)
    j = k*2
    while j < (k*10**k0):
        if L > F(j):
            L = F(j)
        j += k
    print(L)

Submission status: Wrong Answer

Solution code:
def foo(s):
    return sum(map(int, str(s)))

k = int(input())

x = k
seen = set()

while True:
    v = foo(x)
    if v in seen:
        break
    seen.add(v)
    x += k

print(min(seen))

Submission status: Wrong Answer

Solution code:

def foo(s):
    return sum(map(int, str(s)))


k = int(input())

x = k
y = k
for i in range(10000):
    y = min(foo(x), y)
    x += k

print(y)

Submission status: Wrong Answer

Solution code:


def foo(s):
    return sum(map(int, str(s)))


k = int(input())

x = k
y = k
for i in range(k):
    y = min(foo(x), y)
    x += k

print(y)

Submission status: Wrong Answer

Solution code:
def foo(s):
    return sum(map(int, str(s)))


k = int(input())

x = k
y = k
for i in range(100):
    y = min(foo(x), y)
    x += k

print(y)

Submission status: Wrong Answer

Solution code:
import math


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


a=input()
a=int(a)
mae=0
# for k in range(10000):
#     print(wa_sum(a*k))
nums=[]    
for i in range(1,1000000):
    nums.append(wa_sum(i*a))
    # mae=a*(i-1)
    # mae=wa_sum(mae)
    # ima=a*i
    # ima=wa_sum(ima)
    # ato=a*(i+1)
    # ato=wa_sum(ato)
    # if mae>=ima and ima<=ato:
    #     print(ima)
    #     break
    
print(min(nums))

Submission status: Wrong Answer

Solution code:
import math


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


a=input()
a=int(a)
mae=0
# for k in range(10000):
#     print(wa_sum(a*k))
nums=[]    
for i in range(1,10000):
    nums.append(wa_sum(i*a))
    # mae=a*(i-1)
    # mae=wa_sum(mae)
    # ima=a*i
    # ima=wa_sum(ima)
    # ato=a*(i+1)
    # ato=wa_sum(ato)
    # if mae>=ima and ima<=ato:
    #     print(ima)
    #     break
    
print(min(nums))

Submission status: Wrong Answer

Solution code:
import math


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


a=input()
a=int(a)
mae=0
for i in range(1,10000000000):
    mae=a*(i-1)
    mae=wa_sum(mae)
    ima=a*i
    ima=wa_sum(ima)
    ato=a*(i+1)
    ato=wa_sum(ato)
    if mae>=ima and ima<=ato:
        print(ima)
        break

Submission status: Wrong Answer

Solution code:
K = int(input())
ans = 100000

for i in range(1, 8*10**5):
    Z = K * i
    Z = sum(map(int, list(str(Z))))
    ans = min(Z, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
ans = 100000

for i in range(1, 46000):
    Z = K * i
    Z = sum(map(int, list(str(Z))))
    ans = min(Z, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
ans = 100000

for i in range(1, 100001):
    Z = K * i
    Z = sum(map(int, list(str(Z))))
    ans = min(Z, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
k=int(input())
lst = [k+1]*k
queue = [1]
lst[1] = 1
while queue:
    a = queue.pop(0)
    if lst[a*10%k] == k+1:
        lst[a*10%k] = lst[a]
        queue.insert(0,a*10%k)
    if lst[(a+1)%k]==k+1:
        lst[(a+1)%k] = lst[a]+1
        queue.append((a+1)%k)
print(lst[0])

Submission status: Wrong Answer

Solution code:
a=int(input())
 
y=10000000000000
for j in range(1,100000):
  b=sum([int(i) for i in list(str(a*j))])
  y=min(y,b)
 
x=0
for j in range(1,18):
  if a % 2**j==0:
    x = j

c = sum([int(i) for i in list(str(a * (5**x)))])    
print(min(y,c))

Submission status: Wrong Answer

Solution code:
a=int(input())

y=10000000000000
for j in range(1,100000):
  b=sum([int(i) for i in list(str(a*j))])
  y=min(y,b)

x=0
for j in range(1,18):
  if a % 2**j==0:
    x = j
print(x)
c = sum([int(i) for i in list(str(a * (5**x)))])    
print(min(y,c))

Submission status: Wrong Answer

Solution code:
a=int(input())

y=10000000000000
for j in range(1,500000):
  b=sum([int(i) for i in list(str(a*j))])
  y=min(y,b)
print(y)

Submission status: Wrong Answer

Solution code:
K = int(input())
MAX_K = int(1e5)
ks = [K * i for i in range(1, MAX_K)]
def f(n):
    ret = 0
    while n:
        ret += n % 10
        n //= 10
    return ret
ans = min(map(f, ks))
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
ks = [K * i for i in range(1, 10)]
def f(n):
    ret = 0
    while n:
        ret += n % 10
        n //= 10
    return ret
ans = min(map(f, ks))
print(ans)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
k=i1()
m=float("inf")
for i in range(1,10):
 m=min(m,sum([int(j) for j in list(str(k*i))]))
print(m)

Submission status: Wrong Answer

Solution code:
K = int(input())

L = {i: -1 for i in range(K)}
L[1] = 1
biq = [1]

while len(biq) > 0:
    i = biq.pop(0)
    j = (i * 10) % K
    if L[j] < 0:
        L[j] = L[i]
        biq.insert(0, j)
    k = 0 if i == K - 1 else i + 1
    if L[k] < 0:
        L[k] = L[i] + 1
        biq.insert(-1, k)

print(L[0])

Submission status: Wrong Answer

Solution code:
K = int(input())

L = {i: 10**10 for i in range(K)}
L[1] = 1
biq = [1]

while len(biq) > 0:
    i = biq.pop(0)
    j = (i * 10) % K
    if L[j] == 10**10:
        L[j] = L[i]
        biq.insert(0, j)
    k = 0 if i == K - 1 else i + 1
    if L[k] == 10**10:
        L[k] = L[i] + 1
        biq.insert(-1, k)

print(L[0])

Submission status: Wrong Answer

Solution code:
K = int(input())

mi = 10*10

for i in range(1,K):
    k = K * i

    count = 0
    while k > 0:
        count += k % 10
        k //= 10

    if mi > count:
        mi = count

print(mi)

Submission status: Wrong Answer

Solution code:
K = int(input())

mi = 10*10

for i in range(9):
    k = K * (i + 1)

    count = 0
    while k > 0:
        count += k % 10
        k //= 10

    if mi > count:
        mi = count

print(mi)

Submission status: Wrong Answer

Solution code:
M = [[0 for _ in range(9)] for _ in range(9)]


def counter(x):
    if x < 10:
        return x
    else:
        return x % 10 + x // 10


for i in range(9):
    n = i + 1
    for j in range(9):
        m = j + 1
        M[i][j] = counter(n*m)

K = int(input())

xs = []
while K > 0:
    xs.append(K % 10)
    K = K // 10

xs = [x for x in xs if x != 0]

mi = 10*10

for i in range(9):
    tmp = sum([M[x-1][i] for x in xs])
    if mi > tmp:
        mi = tmp

print(mi)

Submission status: Wrong Answer

Solution code:
N = int(raw_input())

a = 100000
for i in xrange(1,400000):
    b = 0
    for j in str(N * i):
        b += int(j)
    if a > b:
        a = b
print a

Submission status: Wrong Answer

Solution code:
N = int(raw_input())

a = 100000
for i in xrange(100000):
    s = str(N * i * 2 + 1)
    b = 0
    for j in s:
        b += int(j)
    if a > b:
        a = b
print a

Submission status: Wrong Answer

Solution code:
N = int(raw_input())

a = 100000
for i in xrange(1,100000):
    s = str(N * i)
    b = 0
    for j in s:
        b += int(j)
    if a > b:
        a = b
print a

Submission status: Wrong Answer

Solution code:
from collections import deque
K = int(input())
E = [[((i + 1) % K, 1)] for i in range(K)]
for i in range(1, K):
	E[i].append((i * 10 % K, 0))
Q = deque([(1, 1)])
reached = set([1])
while 1:
	tmp_node, tmp_cost = Q.popleft()
	if tmp_node == 0:
		ans = tmp_cost
		break
	for nxt, dist in E[tmp_node]:
		if nxt in reached:
			continue
		reached.add(nxt)
		if dist == 0:
			Q.appendleft((nxt, tmp_cost))
		else:
			Q.append((nxt, tmp_cost + 1))
print(ans)

Submission status: Wrong Answer

Solution code:
K = [int(c) for c in input()]
ans = 9 * len(K)
Krev = K[::-1]
for prod in range(1, 10**5 + 1):
	digits = [0] * (len(K) + 10)
	for pos, k in enumerate(Krev):
		num = k * prod
		while num:
			digits[pos] += num % 10
			num //= 10
			pos += 1
	ans = min(ans, sum(digits))
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
def digitsum(n):
  nstr = str(n)
  sum = 0
  lowerbound = 0
  for c in nstr:
    sum += int(c)
    if c != '0' and c != '5':
      lowerbound += 2
    
  return sum,lowerbound
ans,lower = digitsum(K)
X = K
while ans > lower:
  X += K
  sum,lower = digitsum(K)
  ans = min(sum, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
def digitsum(n):
  nstr = str(n)
  sum = 0
  lowerbound = 0
  for c in nstr:
    sum += int(c)
    if c != '0' and c != '5':
      lowerbound += 2
    
  return sum,lowerbound
ans,lower = digitsum(K)

while ans > lower:
  K += K
  sum,lower = digitsum(K)
  ans = min(sum, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
def digitsum(n):
  nstr = str(n)
  sum = 0
  lowerbound = 0
  for c in nstr:
    sum += int(c)
    if c != '0' and c != '5':
      lowerbound += 2
    
  return sum,lowerbound
ans,lower = digitsum(K)

while ans > lower:
  K = 2 * K
  sum,lower = digitsum(K)
  ans = min(sum, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())
def digitsum(n):
  nstr = str(n)
  sum = 0
  for c in nstr:
    sum += int(c)
  return sum

ans = digitsum(K)
i = 0
while i < 5000:
  K += K
  i+=1
  ans = min (ans, digitsum(K))
print(ans)