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:
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
                q.insert(0, (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
                q.append((k+1, t))
                v[t] = True
                i = i*10 % K
                t = (u+i) % K

    return search(1)

print(main())

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):
        d = collections.defaultdict(lambda: inf)
        q = [(1,s)]
        qi = 0
        v = [False] * (K+1)
        v[s] = True
        while len(q):
            k, u = q[0]
            q = q[1:]
            t = u*10 % K
            while not v[t]:
                if t == 0:
                    return k
                q.insert(0, (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
                q.append((k+1, t))
                v[t] = True
                i = i*10 % K
                t = (u+i) % K

    return search(1)

print(main())

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):
        d = collections.defaultdict(lambda: inf)
        q = [(1,s)]
        qi = 0
        v = collections.defaultdict(bool)
        v[s] = True
        while len(q):
            k, u = heapq.heappop(q)
            if u == 0:
                return k
            t = u*10 % K
            while not v[t]:
                q.append((k, t))
                v[t] = True
                t = t*10 % K

            i = 1
            t = (u+i) % K
            while not v[t]:
                q.append((k+1, t))
                v[t] = True
                i = i*10 % K
                t = u+i % K

    return search(1)

print(main())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left, insort
def inpl(): return tuple(map(int, input().split()))

K = int(input())

C1 = []

for i in range(1, 10**len(str(K))//K + 1):
    C1.append(sum(map(int, str(K*i))))

J = K * (10**len(str(K))//K + 1)
J -= 10**(len(str(J)) - 1)

rC2 = [J]
C2 = [sum(map(int, str(J))) + 1]
while True:
    J = (J*10)%K
    i = bisect_left(rC2, J)
    if i < len(rC2):
        if J == rC2[i]:
            break
    insort(rC2, J)
    C2.append(1 + sum(map(int, str(J))))
print(min(min(C1), min(C2)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

K = int(input())

C1 = []

for i in range(1, 10**len(str(K))//K + 1):
    C1.append(sum(map(int, str(K*i))))

J = K * (10**len(str(K))//K + 1)
J -= 10**(len(str(J)) - 1)

C2 = [J+1]

while True:
    J = (J*10)%K
    if J+1 in C2:
        break
    else:
        C2.append(J+1)

print(min(min(C1), min(C2)))

Submission status: Wrong Answer

Solution code:
target = int(input())
answer = float("inf")
for i in range(1, 10):
    mul = target * i
    temp = 0
    for j in str(mul):
        temp += int(j)
    answer = min(answer, temp)
print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
mn = 10000
for x in range(2,400000):
    ne = n*x
    ne = str(ne)
    su = 0
    for y in ne:
        su += int(y)
    mn = min(mn,su)
print(mn)

Submission status: Wrong Answer

Solution code:
n = int(input())
mn = 10000
for x in range(2,100000):
    ne = n*x
    ne = str(ne)
    su = 0
    for y in ne:
        su += int(y)
    mn = min(mn,su)
print(mn)

Submission status: Wrong Answer

Solution code:
n = int(input())
mn = 10000
for x in range(2,100):
    ne = n*x
    ne = str(ne)
    su = 0
    for y in ne:
        su += int(y)
    mn = min(mn,su)
print(mn)

Submission status: Wrong Answer

Solution code:
n = int(input())
mn = 10000
for x in range(2,10000):
    ne = n*x
    ne = str(n)
    su = 0
    for y in ne:
        su += int(y)
    mn = min(mn,su)
print(mn)

Submission status: Wrong Answer

Solution code:
n = int(input())
mn = 100
for x in range(2,100):
    ne = n*x
    ne = str(n)
    su = 0
    for y in ne:
        su += int(y)
    mn = min(mn,su)
print(mn)

Submission status: Wrong Answer

Solution code:
from collections import deque

K = int(input())

while K%2 == 0:
  K //= 2
while K%5 == 0:
  K //= 5

if K == 1:
  print(1)
  exit()

q0 = [1]
q1 = []

T = [True]*K
T[1] = False

x = 1

while True:
  while q0:
    v = q0.pop()
    if v == 0:
      print(x)
      exit()
    a = (v+1)%K
    if T[a]:
      q1.append(a)
      T[a] = False
    b = (v*10)%K
    if T[b]:
      q0.append(b)
      T[b] = False
  q0 = q1
  q1 = []
  x += 1

Submission status: Wrong Answer

Solution code:
from collections import deque

K = int(input())

while K%2 == 0:
  K //= 2
while K%5 == 0:
  K //= 5

if K == 1:
  print(1)
  exit()

q0 = [1]
q1 = []

T = [True]*K
T[1] = False

x = 1

while True:
  while q0:
    v = q0.pop()
    a = (v+1)%K
    if T[a]:
      q1.append(a)
      T[a] = False
    b = (v*10)%K
    if T[b]:
      q0.append(b)
      T[b] = False
    if a == 0:
      print(x+1)
      exit()
    if b == 0:
      print(x)
      exit()
  q0 = q1
  q1 = []
  x += 1

Submission status: Wrong Answer

Solution code:
from collections import deque

K = int(input())

Q = deque((1,))
inf = float('inf')
L = [inf]*K
L[1] = 1

while L[0] == inf:
  n = Q.popleft()
  a = (n+1)%K
  if L[a] > L[n]+1:
    L[a] = L[n]+1
    Q.append(a)
  b = (n*10)%K
  if L[b] > L[n]:
    L[b] = L[n]
    Q.appendleft(b)

print(L[0])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def solve(K):
	while K%2==0:
	    K /= 2
	while K%5==0:
	    K /= 5
	 
	T = [[0]*10 for _ in range(10)]
	for i in range(10):
	    for j in range(10):
	        T[i][i*j%10] = j
	 
	memo = [-1]*100000
	def f(x):
	    if x==0:
	        return 0
	    if memo[x]>=0:
	        return memo[x]
	    if memo[x]==-2:
	        return 999999
	    memo[x] = -2
	    ans = 99999999#sum(map(int, str(x)))
	    mini = -1
	    for i in range(10):
	        #for j in range(10):
	        #    if (j*K+x)%10==i:
	        #        ans = min(ans, i+f((j*K+x)/10))
	        if i+f((T[K%10][(i-x)%10]*K+x)/10) < ans:
	        	mini = i
	        ans = min(ans, i+f((T[K%10][(i-x)%10]*K+x)/10))
	    memo[x] = ans
	    #print x, ans, mini, (T[K%10][(mini-x)%10]*K+x)/10
	    return ans
	return f(K)

def naive(K):
	ans = 10**8
	for i in range(1,10000):
		ans = min(ans, sum(map(int, str(K*i))))
	return ans

"""
for K in range(1,10000):
	if K%2 and K%5:
		if naive(K)!=solve(K) and solve(K)!=2:
			print K, naive(K), solve(K)
"""

print naive(input())

Submission status: Wrong Answer

Solution code:
import numpy as np

V=int(input())


s=V*np.arange(1,int((10**5)))
res=list(map(lambda x:sum(list(map(np.int,str(x)))),s))
#plt.plot(res)
ans=min(res)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
 
K = input()
while K%2==0:
    K /= 2
while K%5==0:
    K /= 5
 
T = [[0]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        T[i][i*j%10] = j
 
memo = [-1]*100000
def f(x):
    if x==0:
        return 0
    if memo[x]>=0:
        return memo[x]
    if memo[x]==-2:
        return 999999
    memo[x] = -2
    ans = sum(map(int, str(x)))
    for i in range(10):
        #for j in range(10):
        #    if (j*K+x)%10==i:
        #        ans = min(ans, i+f((j*K+x)/10))
        ans = min(ans, i+f((T[K%10][(i-x)%10]*K+x)/10))
    memo[x] = ans
    return ans
print f(K)

Submission status: Wrong Answer

Solution code:
a = int(input())
while a % 2 == 0:
  a //= 2
while a % 5 == 0:
  a //= 5
s = 0
while a > 0:
  s += a % 10
  a //= 10
print(s)

Submission status: Wrong Answer

Solution code:

import numpy as np

V=int(input())


s=V*np.arange(1,int(V))
res=list(map(lambda x:sum(list(map(int,str(x)))),s))
#plt.plot(res)
ans=min(res)
print(ans)

Submission status: Wrong Answer

Solution code:
k = int(input())
kn = [0]*30
tmp = k
for i in range(30) :
    kn[i] = tmp%10
    tmp = tmp//10
p = [0,1,2,3,-4,-3,-2,-1,0]
ans = sum(kn)
for i in range(1, 10) :
    res = 0
    for j in range(30) :
        res += i*kn[j]%10
        res += i*kn[j]//10
    ans = min(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
k = int(input())
kn = [0]*30
tmp = k
for i in range(30) :
    kn[i] = tmp%10
    tmp = tmp//10
p = [0,1,2,3,-4,-3,-2,-1,0]
ans = sum(kn)
for i in range(1, 9) :
    res = 0
    for j in range(30) :
        res += i*kn[j]%10
        res += i*kn[j]//10
    ans = min(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

K = input()
while K%2==0:
    K /= 2
while K%5==0:
    K /= 5

T = [[0]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        T[i][i*j%10] = j

memo = [-1]*100000
def f(x):
    if x==0:
        return 0
    if memo[x]>=0:
        return x
    if memo[x]==-2:
        return 999999
    memo[x] = -2
    ans = sum(map(int, str(x)))
    for i in range(10):
        #for j in range(10):
        #    if (j*K+x)%10==i:
        #        ans = min(ans, i+f((j*K+x)/10))
        ans = min(ans, i+f((T[K%10][(i-x)%10]*K+x)/10))
    memo[x] = ans
    return ans
print f(K)

Submission status: Wrong Answer

Solution code:
import random
random.seed(71)

K = int(input())
ans = 0

K_copy = K
while K_copy > 0:
    ans += K_copy % 10
    K_copy //= 10

maxi = int('1' * ans)
maxi //= K

if maxi > 1:
    viewed = {1}
    for _ in range(10 ** 4):
        j = 1
        while j in viewed:
            j = random.randint(1, maxi)
        M = K * j
        m = 0
        while M > 0:
            m += M % 10
            M //= 10
        ans = min(ans, m)
        if len(viewed) == maxi:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import random
random.seed(1024)

K = int(input())
ans = 0

K_copy = K
while K_copy > 0:
    ans += K_copy % 10
    K_copy //= 10

maxi = int('1' * ans)
maxi //= K

if maxi > 1:
    viewed = {1}
    for _ in range(10 ** 4):
        j = 1
        while j in viewed:
            j = random.randint(1, maxi)
        M = K * j
        m = 0
        while M > 0:
            m += M % 10
            M //= 10
        ans = min(ans, m)
        if len(viewed) == maxi:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(raw_input())
ans = 999999
for i in xrange(1, 500000):
  a = sum(map(int, list(`K * i`)))
  if a < ans:
    ans = a

print ans

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

K = input()
while K%2==0:
    K /= 2
while K%5==0:
    K /= 5

T = [[0]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        T[i][i*j%10] = j

memo = [-1]*100000
def f(x):
    if x==0:
        return 0
    if memo[x]>=0:
        return x
    if memo[x]==-2:
        return 999999
    memo[x] = -2
    ans = sum(map(int, str(x)))
    for i in range(10):
        #for j in range(10):
        #    if (j*K+x)%10==i:
        #        ans = min(ans, i+f((j*K+x)/10))
        ans = min(ans, i+f((T[i][(-x)%10]*K+x)/10))
    memo[x] = ans
    return ans
print f(K)

Submission status: Wrong Answer

Solution code:
import math
def main():
    K = int(input())
    if K == 10**5:
        print(1)
        return

    d = math.ceil(math.log10(K))

    m = 1
    res = 10**5 + 1
    while True:
        res = min(calc(K*m), res)
        # if res < math.ceil(math.log10(K*m)):
        #     break
        if m > (10**5) + 1:
            break
        m += 1
    
    print(res)

def calc(N):
    count = 0
    d = math.ceil(math.log10(N))
    for i in range(d):
        count += ((N % 10**(i+1)) // (10**i))

    return count

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import random
random.seed(1024)

K = 10 # int(input())
ans = 0

K_copy = K
while K_copy > 0:
    ans += K_copy % 10
    K_copy //= 10

maxi = int('1' * ans)
maxi //= K

if maxi > 1:
    for _ in range(10 ** 4):
        j = random.randint(1, maxi)
        M = K * j
        m = 0
        while M > 0:
            m += M % 10
            M //= 10
        ans = min(ans, m)

print(ans)

Submission status: Wrong Answer

Solution code:
# python3
# utf-8

k = int(input())

ans = 50
for mult in range(1, 1000000):
    curr_ans = sum(int(x) for x in str(k * mult))
    ans = min(ans, curr_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

K = input()
while K%2==0:
    K /= 2
while K%5==0:
    K /= 5

T = [[0]*10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        T[i][i*j%10] = j

memo = [-1]*100000
def f(x):
    if x==0:
        return 0
    if memo[x]>=0:
        return x
    if memo[x]==-2:
        return 999999
    memo[x] = -2
    ans = sum(map(int, str(x)))
    for i in range(10):
        for j in range(10):
            if (j*K+x)%10==i:
                ans = min(ans, i+f((j*K+x)/10))
    memo[x] = ans
    return ans
print f(K)

Submission status: Wrong Answer

Solution code:
# python3
# utf-8

k = int(input())

ans = 50
for mult in range(1, 500000):
    curr_ans = sum(int(x) for x in str(k * mult))
    ans = min(ans, curr_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

N = 5 * 10 ** 5
m = 0
ans = float('inf')
for i in range(N):
    m += K
    s = sum(map(int, str(m)))
    ans = min(ans, s)

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

def get_sum(N):
    ret = 0
    for ch in str(N):
        ret += int(ch)
    return ret

def bf(N):
    ans = 1e9
    ans_num = None
    s = 0
    for i in range(100000):
        s += N
        tmp = get_sum(s)
        if tmp < ans:
            ans_num = s
            ans = tmp
    return ans, ans_num


def solve(N):
    def div2and5(N):
        while N % 2 == 0:
            N //= 2
        while N % 5 == 0:
            N //= 5
        return N
    N = div2and5(N)
    return bf(N)

print(solve(K)[0])

#for i in range(1, 1000):
#    solve(i)
#    #print("{}: {}".format(i, solve(i)))

Submission status: Wrong Answer

Solution code:
# python3
# utf-8

k = int(input())

ans = 50
for mult in range(1, 200000):
    curr_ans = sum(int(x) for x in str(k * mult))
    ans = min(ans, curr_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import random

K = 79992 # int(input())
ans = 0

K_copy = K
while K_copy > 0:
    ans += K_copy % 10
    K_copy //= 10

maxi = int('1' * ans)
maxi /= K

for _ in range(10 ** 4):
    j = random.randint(1, maxi)
    M = K * j
    m = 0
    while M > 0:
        m += M % 10
        M /= 10
    ans = min(ans, m)

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

N = 10 ** 5
m = 0
ans = float('inf')
for i in range(N):
    m += K
    s = sum(map(int, str(m)))
    ans = min(ans, s)

print(ans)

Submission status: Wrong Answer

Solution code:
K = int(input())

def dsum(n):
    ret = 0
    for c in str(n):
        ret += int(c)
    return ret

ans = dsum(K)
for i in range(2,400000):
    ans = min(ans, dsum(i * K))

print(ans)

Submission status: Wrong Answer

Solution code:
import math
def main():
    K = int(input())

    d = math.ceil(math.log10(K))

    m = 1
    res = 10**5 + 1
    while True:
        res = min(calc(K*m), res)
        # if res < math.ceil(math.log10(K*m)):
        #     break
        if m > 10**5:
            break
        m += 1
    
    print(res)

def calc(N):
    count = 0
    d = math.ceil(math.log10(N))
    for i in range(d):
        count += ((N % 10**(i+1)) // (10**i))

    return count

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
K = int(input())

def dsum(n):
    ret = 0
    for c in str(n):
        ret += int(c)
    return ret

ans = dsum(K)
for i in range(2,350000):
    ans = min(ans, dsum(i * K))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
tmp = n
while tmp % 5 == 0:
	tmp //= 5
while tmp % 2 == 0:
	tmp //= 2
if tmp == 1 or n == 100000:
	print(1)
else: print(min(sum(map(int, str(n * i))) for i in range(1, 10 ** (len(str(n))) + 1)))

Submission status: Wrong Answer

Solution code:
n = int(input())
if bin(n)[2:].count('1') == 1 or n == 100000:
	print(1)
else: print(min(sum(map(int, str(n * i))) for i in range(1, 10 ** (len(str(n))) + 1)))

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
INF = float("inf")

def f(x):
    return sum(int(a) for a in str(x))


def solve(K):
    ans = INF
    min_i = 0
    for i in range(1, 10**5 + 1):
        if ans > f(K * i):
            ans = f(K * i)
            min_i = i
    return K, min_i, ans

def main():
    K = int(input())
    print(solve(K)[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
k = int(input())

min_sum = 100

for i in range(1,10):
    k_ = k*i
#     print(k_)
    str_list = list(str(k_))
    num_list = [int(x) for x in str_list]
    if min_sum > sum(num_list):
        min_sum = sum(num_list)    

print(min_sum)

Submission status: Wrong Answer

Solution code:
import sys

cin = sys.stdin
# cin = open("in.txt", "r")

def line2N():
    return map(int, cin.readline().split())

K, = line2N()
t = 0
rMin = 0x7fff7fff
for i in range(1, K+1):
    t += K
    d = sum(map(int, str(t)))
    rMin = min(rMin, d)

print(rMin)

Submission status: Wrong Answer

Solution code:
K = int(input())

def digit_sum(n):
    s = str(n)
    ret = 0
    for i in s:
        ret += int(i)
    return ret

ans = digit_sum(K)
for i in range(1,10):
    ans = min(ans,digit_sum(i*K))

print(ans)

Submission status: Wrong Answer

Solution code:
def keta(n):
    return sum(int(k) for k in list(str(n)))

k = int(input().strip())
print(min(keta(k*n) for n in range(1,100000)))

Submission status: Wrong Answer

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

for i in range(1, 100):
    ch = int('1' * i)
    if (ch % n == 0):
        print(i)
        break

Submission status: Wrong Answer

Solution code:
k = int(input())
while k % 2 == 0:
    k //= 2
k = str(k)
ans = 0
p = ord("0")
for i in range(len(k)):
    ans += ord(k[i]) - p
print(ans)

Submission status: Wrong Answer

Solution code:
K = int(raw_input())
ans = 999999
for i in xrange(1, 100000):
  a = sum(map(int, list(`K * i`)))
  if a < ans:
    ans = a

print ans

Submission status: Wrong Answer

Solution code:
K=int(input())
st=str(K)
stl=len(st)
ans=0
for j in range(stl):
  ans+=int(st[j])

for i in range(1,10**5):
  st=str(K*i)
  stl=len(st)
  ans1=0
  for j in range(stl):
    ans1+=int(st[j])
  ans=min(ans,ans1)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3

import sys


def digit_sum(x):
    return sum(int(c) for c in str(x))


def calc_min_digit_sum(k):
    cands = (digit_sum(k * d) for d in range(1, 101))
    return min(cands)


def main():
    print(calc_min_digit_sum(int(input())))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import time

start = time.time()

import sys
if sys.version[0] == '2':
    input = raw_input
K = KK = int(input())
ans = sum(int(x) for x in str(K))
while time.time() - start < 1.8:
    K += KK
    now = sum(int(x) for x in str(K))
    if now < ans:
        ans = now
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
if n == 100000:
	print(1)
else: print(min(sum(map(int, str(n * i))) for i in range(1, 10 ** len(str(n)) + 1)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3


def digit_sum(x):
    return sum(int(c) for c in str(x))


def calc_min_digit_sum(k):
    return min(digit_sum(k * d) for d in range(1, 31))


def main():
    print(calc_min_digit_sum(int(input())))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
K = int(raw_input())

m = 10 ** (int(math.log(K, 10)) + 1)

ans = 99999
for i in xrange(1, m):
  a = sum(map(int, list(`K * i`)))
  if a < ans:
    ans = a

print ans

Submission status: Wrong Answer

Solution code:
import time

start = time.time()

import sys
if sys.version[0] == '2':
    input = raw_input
K = KK = int(input())
ans = sum(int(x) for x in str(K))
cnt = 0
while time.time() - start < 1.8:
    K += KK
    now = sum(int(x) for x in str(K))
    if now < ans:
        ans = now
    cnt += 1
print(ans, cnt)

Submission status: Wrong Answer

Solution code:
def getsum(x):
    s=str(x)
    ret=0
    for i in s:
        ret+=int(i)
    return ret
k=int(input())
while(k%5==0):
    k//=5
while(k%2==0):
    k//=2
ret=getsum(k)
for i in range(2,100000):
    ret=min(ret,getsum(i*k))
print(ret)

Submission status: Wrong Answer

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


n = int(input())
ans = f(n)
nn = n


for i in range(0, 501010):
	nn += n
	cur = f(nn)
	if cur < ans:
		ans = cur

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3


def digit_sum(x):
    return sum(int(c) for c in str(x))


def calc_min_digit_sum(k):
    return min(digit_sum(k * d) for d in range(1, 11))


def main():
    print(calc_min_digit_sum(int(input())))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def getsum(x):
    s=str(x)
    ret=0
    for i in s:
        ret+=int(i)
    return ret
k=int(input())
ret=getsum(k)
for i in range(1,100000):
    ret=min(ret,getsum(k*i))
print(ret)

Submission status: Wrong Answer

Solution code:
def siffsum(n):

    s=str(n)
    su=0
    for ch in s:
        su+=int(ch)
    return su
k=int(input())

best=siffsum(k)
for i in range(2,100000):
    best=min(best,siffsum(k*i))
print(best)

Submission status: Wrong Answer

Solution code:
def siffsum(n):

    s=str(n)
    su=0
    for ch in s:
        su+=int(ch)
    return su
k=int(input())

best=siffsum(k)
for i in range(2,10):
    best=min(best,siffsum(k*i))
print(best)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
D = [9999]*K
D[1] = 1
H = []
H.append(1)
while len(H) != 0:
    h = H.pop()
    if D[(h*10)%K] > D[h]:
        D[(h*10)%K] = D[h]
        H.append((h*10)%K)
    if D[(h+1)%K] > D[h] + 1:
        D[(h+1)%K] = D[h] + 1
        H.append((h+1)%K)

print(D[0])

Submission status: Time Limit Exceeded

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**8):
        ans=min(ans,mizu(i*K,ans))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.buffer.readline
N = int(input())
e = dd(list)
for i in range(1, N):
  n1 = 10 * i
  n2 = i + 1
  e[i].append((n1 % N, 0))
  e[i].append((n2 % N, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [(0, s)]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      if v in vis: continue
      vis.add(v[1])
      for p in self.e[v[1]]:
        d[p[0]] = min(d[p[0]], d[v[1]] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, (d[p[0]], p[0]))
    return d[t]
d = dijkstra(N, e)
print(d.path(1, 0) + 1)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
INF = float('inf')
D = [-1]*K
C = [1]*K
D[1] = 0
while C[0]:
    m = min(filter(lambda x:C[x] and D[x] != -1,range(K)),key=lambda x:D[x])
    j = (10*m)%K
    D[j] = D[m] if D[j]==-1 else min(D[j],D[m])
    l = (m+1)%K
    D[l] = D[m]+1 if D[l]==-1 else min(D[l],D[m]+1)
    C[m] = 0

print(D[0]+1)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
from collections import deque
dic = {1:1}
queue = deque()
queue.appendleft([1,1])
while queue:
    v,cost = queue.popleft()
    v_ = (v+1)%k
    if not v_ in dic or cost+1<dic[v_]:
        dic[v_] = cost+1
        queue.appendleft([v_,cost+1])
    v_ = v*10%k
    if not v_ in dic or cost<dic[v_]:
        dic[v_] = cost
        queue.appendleft([v_,cost])

print(dic[0])

Submission status: Time Limit Exceeded

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

print(dic[0])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

K = int(input())
q = deque()
q.append((1,1)) # 各桁の和、modulo K
visited = [False]*K

ans = 0

while ans == 0:
  s,x = q.popleft()
  visited[x] = True
  if x == 0:
    ans = s
    break
  q.appendleft((s,(10*x)%K))
  q.append((s+1,(x+1)%K))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
 
# 1から初めて、xがあるとき10x、x+1のいずれかが行えるとしてqueue
 
K = int(input())
h = []
heapq.heappush(h,(1,1)) # 各桁の和、modulo K
visited = [False]*K
 
ans = 0
 
while ans == 0:
  s,x = heapq.heappop(h)
  visited[x] = True
  for ss,xx in [(s,(10*x)%K), (s+1,(x+1)%K)]:
    if visited[xx]:
      continue
    if xx == 0:
      ans = ss
      break
    heapq.heappush(h,(ss,xx))
  
print(ans)

Submission status: Time Limit Exceeded

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)
  visited[x] = True
  for ss,xx in [(s,(10*x)%K), (s+1,(x+1)%K)]:
    if visited[xx]:
      continue
    if xx == 0:
      ans = ss
      break
    heapq.heappush(h,(ss,xx))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    K = int(input())
    q = deque([(1, 1)])
    visited = [False] * K
    while len(q):
        n, s = q.popleft()
        if visited[n % K]:
            continue
        visited[n % K] = True
        if n % K == 0:
            print(s)
            return
        q.appendleft((n*10, s))
        q.append((n+1, s+1))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    K = int(input())
    q = deque([(1, 1)])
    visited = [False] * K
    while len(q):
        n, s = q.popleft()
        if n % K == 0:
            print(s)
            return
        if visited[n % K]:
            continue
        visited[n % K] = True
        if not visited[n*10 % K]:
            q.appendleft((n*10, s))
        if not visited[(n+1) % K]:
            q.append((n+1, s+1))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    K = int(input())
    q = deque([(1, 1)])
    visited = [False] * K
    while len(q):
        n, s = q.popleft()
        if n % K == 0:
            print(s)
            return
        if visited[n % K]:
            continue
        visited[n % K] = True
        q.appendleft((n*10, s))
        q.append((n+1, s+1))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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 > 2.7:
        break
        
print(mi)

Submission status: Time Limit Exceeded

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 > 2.9:
        break
        
print(mi)