Problem:


Score : 500 points

Problem Statement

Let S(n) denote the sum of the digits in the decimal notation of n.
For example, S(123) = 1 + 2 + 3 = 6.

We will call an integer n a Snuke number when, for all positive integers m such that m > n, \frac{n}{S(n)} \leq \frac{m}{S(m)} holds.

Given an integer K, list the K smallest Snuke numbers.

Constraints

1 \leq K

The K-th smallest Snuke number is not greater than 10^{15}.

Input

Input is given from Standard Input in the following format:

K

Output

Print K lines. The i-th line should contain the i-th smallest Snuke number.

Sample Input 1

10

Sample Output 1

1
2
3
4
5
6
7
8
9
19



Sample input:
10


Sample output:
1
2
3
4
5
6
7
8
9
19

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()
carry = False

def f(n):
    """
    順番に貪欲するのではなく、「ある数 n 以上で n/S(n) を最小にする数 f(n) を求める」と言い換えれば
    このクエリを K 回繰り返せばよい。

    例えば n = 314159265 の場合に考えてみる。仮にf(n) = 314234567だったとしてこれが間違いであることを示しつつ
    最善手を模索してみる。
    実際これよりも小さい数で n/S(n) が小さいものが存在して、例えば 314199999である。なぜなら
    まず明らかにこれは 314234567より小さく、さらに各桁の和も後半がすべて9であることから S(n) は増加しているので
    n/S(n) は小さくなっている。

    これより、n が与えられたら f(n) は n の下の桁からどこかまで順に...999と埋めたものになる。
    """
    c = str(n)
    L = len(c)
    digit_sum = [0] * (L + 1)
    for i in range(1, L + 1): digit_sum[i] = digit_sum[i - 1] + int(c[i - 1])

    ret = n
    val = n / digit_sum[-1]
    for d in range(L - 1, -1, -1):
        N = int(c[:d] + '9' * (L - d))
        valN = N / (digit_sum[d] + 9 * (L - d))
        if val > valN:
            ret = N
            val = valN
    # 多分nの桁数を超えたところに最小値はない気がする
    return ret



def main():
    K = int(input())
    print(1)
    n = 1
    for _ in range(1, K):
        n = f(n + 1)
        print(n)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k = int(input())

l = []
for i in range(17):
    ten = 10**i
    for j in range(1,1000):
        a = ten
        b = j
        n = a*b-1
        if n == 0:
            continue
        s = sum(map(int,str(n)))
        l.append([n/s,n])
l.sort()
now = 0
count = 0
i = 0
while count < k:
    if l[i][1] > now:
        now = l[i][1]
        count += 1
        print(l[i][1])
    i += 1

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

# 1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 99, 199, 299, 399, ... , 1999, 2999, ...

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

ANS = []
tmp = INF
for i in reversed(range(16)):
    for j in reversed(range(100, 1000)):
        x = int(str(j)+'9'*i)
        if f(x) <= tmp:
            ANS.append(x)
            tmp = f(x)

for x in reversed([1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 99]):
    ANS.append(x)

ANS.reverse()
# print(ANS)

k = I()
for i in range(k):
    print(ANS[i])

Submission status: Accepted

Solution code:
def S(n):
    k=list(str(n))
    import functools
    return functools.reduce(lambda x,y:x+y,[int(i) for i in k])
k=int(input())
def T(n):
    return n/S(n)
def f(N):
    len_N=len(str(N))
    A=[10**len_N+10**i-1 for i in range(len_N)]
    B=[T(i) for i in A]
    ans1=A[B.index(min(B))]
    i=0
    while True:
        I=10**(len_N-1)+10**i-1
        J=10**(len_N-1)+10**(i+1)-1
        if T(J)<T(I):
            i+=1
        else:
            break
    C=[((N+1)//(10**i))*10**i+j*10**i-1 for j in range(1,11)]
    D=[T(i) for i in C]
    ans2=C[D.index(min(D))]
    if T(ans1)<T(ans2):
        return(ans1)
    else:
        return(ans2)
K=[]
N=1
while len(K)<k:
    K.append(N)
    N=f(N)
for i in range(k):
    print(K[i])

Submission status: Accepted

Solution code:
def s(n):
  return n / sum(map(int, str(n)))
k = int(input())
p = 1
e = 0
i = 0
while i < k:
  n = (p + 1) * 10**e - 1
  nxt = (p + 2) * 10**e - 1
  if s(n) <= s(nxt):
    print(n)
    p += 1
    i += 1
  else:
    e += 1
    p = (p + 1) // 10

Submission status: Accepted

Solution code:
k = int(input())

l = []
for i in range(17):
    ten = 10**i
    for j in range(1,1000):
        a = ten
        b = j
        n = a*b-1
        if n == 0:
            continue
        s = sum(map(int,str(n)))
        l.append([n/s,n])
l.sort()
now = 0
count = 0
i = 0
while count < k:
    if l[i][1] > now:
        now = l[i][1]
        count += 1
        print(l[i][1])
    i += 1

Submission status: Accepted

Solution code:
k=int(input())
A=[]
for i in range(1,9):
    A.append([i,1])
now=0
for i in range(15):
    now+=9*10**i
    for j in range(1000):
        c=now+j*10**(i+1)
        S=str(c)
        cnt=0
        for s in S:
            cnt+=int(s)
        A.append([c,c/cnt])
A=list(reversed(sorted(A)))
now=0
m=A[0][1]
Ans=[]
for a in A:
    if a[0]==now:
        continue
    else:
        now=a[0]
        if a[1]<=m:
            Ans.append(now)
            m=a[1]
Ans=list(reversed(Ans))
for i in range(k):
    print(Ans[i])

Submission status: Accepted

Solution code:
K = int(input())


def ns(n):
    ret, tmp = 0, n

    while tmp > 0:
        tmp, r = divmod(tmp, 10)
        ret += r

    return ret


ans, base = 0, 1
for _ in range(K):
    ans += base
    print(ans)

    if (ans + base) / ns(ans + base) > (ans + 10 * base) / ns(ans + 10 * base):
        base *= 10

Submission status: Accepted

Solution code:
K = int(input())


def ns(n):
    ret, tmp = 0, n

    while tmp > 0:
        #        tmp, r = divmod(tmp, 10)
        r = tmp % 10
        tmp //= 10
        ret += r

    return ret


ans, base = 0, 1
for _ in range(K):
    ans += base
    print(ans)

    if (ans + base) / ns(ans + base) > (ans + 10 * base) / ns(ans + 10 * base):
        base *= 10

Submission status: Accepted

Solution code:
K = int(input())


def ns(n):
    return sum([int(c) for c in str(n)])


ans, base = 0, 1
for _ in range(K):
    ans += base
    print(ans)

    if (ans + base) / ns(ans + base) > (ans + 10 * base) / ns(ans + 10 * base):
        base *= 10

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from fractions import Fraction
import sys


def g():
    i = 1
    while True:
        si = str(i)
        ni = min({
            int(si[:j] + "9" * (len(si) - j))
            for j in range(len(si) + 1)
        }, key=lambda a: (Fraction(a, sum(int(x) for x in str(a))), a))
        yield ni
        i = ni + 1


def solve(K: int):
    it = g()
    for i in range(K):
        print(next(it))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import log10


def S(x):
    a = [int(i) for i in str(x)]
    return sum(a)

def f(N):
    tmp = (N, N / S(N))
    for d in range(int(log10(N) - 1) + 1):
        x = pow(10, d + 1) * int(N / pow(10, d + 1) + 1) - 1
        sunuke = x / S(x)
        if tmp[1] > sunuke:
            tmp = (x, sunuke)
    return tmp[0]


K = int(input())
ans = [1]
N = 1
K -= 1
while K > 0:
    N = f(N + 1)
    ans.append(N)
    K -= 1

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from math import log10
def nsn(N):
    K = sum( list( map( int, list( str(N)))))
    return N/K

def snuke(N):
    k = int( log10(N))+1
    s = N
    now = nsn(N)
    for d in range(k+1):
        x = (10**(d+1))*(N//(10**(d+1)) + 1) - 1
        y = nsn(x)
        if y < now:
            s = x
            now = y
    return s

K = int( input())
ans = 1
print(1)
for i in range(K-1):
    ans = snuke( ans + 1)
    print(ans)

Submission status: Accepted

Solution code:
K=int(input())

def NS(N):
  NS=0
  while(N>0):
    NS+=N%10
    N//=10
  return NS

answer,diff=0,1
for i in range(K):
  answer+=diff
  print(answer)
  
  if (answer+diff)/NS(answer+diff)>(answer+10*diff)/NS(answer+10*diff):
    diff*=10

Submission status: Accepted

Solution code:
K=int(input())

def NS(N):
  NS=0
  while(N>0):
    NS+=N%10
    N//=10
  return NS

answer,diff=0,1
for i in range(K):
  answer+=diff
  print(answer)
  
  if diff<(answer+diff)/NS(answer+diff):
    diff*=10

Submission status: Accepted

Solution code:
def digitsum(n):#nは正の整数、各位の和、許容は１０＾１０００
    if n<10:
        return n
    else:
        m=n//10
        return n%10+digitsum(m)

snuke=[]
for i in range(4,16):
    #i桁のsnuke数を調べる
    #10**i-1はsnuke数
    #上三桁以外は9で確定なので10**i-1から順に調べればよい
    snuke.append(10**i-1)
    min=10**i-1
    k=998
    while k>=100:
        test=k*10**(i-3)+10**(i-3)-1
        if min*digitsum(test)>=test*digitsum(min):
            snuke.append(test)
            min=test
        k-=1


snuke.append(999)
min=999
k=998
while k>0:
    if min*digitsum(k)>=k*digitsum(min):
        snuke.append(k)
        min=k
    k-=1

snuke.sort()

K=int(input())
for i in range(0,K):
    print(snuke[i])

Submission status: Accepted

Solution code:
k=int(input())
a=0
b=1
for i in range(k):
  a+=b
  print(a)
  if b<(a+b)/sum(map(int,str(a+b))):
    b*=10

Submission status: Accepted

Solution code:
from math import log10


def S(x):
    rst = 0
    while x > 0:
        rst += x % 10
        x //= 10
    return rst


def f(N):
    rst = (N, N / S(N))
    for d in range(int(log10(N) - 1) + 1):
        x = pow(10, d + 1) * int(N / pow(10, d + 1) + 1) - 1
        sunuke = x / S(x)
        if rst[1] > sunuke:
            rst = (x, sunuke)
    return rst[0]


K = int(input())
ans = [1]
N = 1
K -= 1
while K > 0:
    N = f(N + 1)
    ans.append(N)
    K -= 1

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
def f(n):
    s=str(n)
    return sum([int(s[i]) for i in range(len(s))])

sunuke=[]
for i in range(16):
    for j in range(1,200):
        sunuke.append(j*(10**i)-1)

sunuke=list(set(sunuke))
sunuke.sort()
sunuke.pop(0)
L=len(sunuke)

tmp1,tmp2=sunuke[L-1],f(sunuke[L-1])
ans=[sunuke[L-1]]
for i in range(len(sunuke)-2,-1,-1):
    x=sunuke[i]
    if x*tmp2<=tmp1*f(x):
        ans.append(x)
        tmp1,tmp2=x,f(x)

ans.sort()

    

for i in range(int(input())):
    print(ans[i])

Submission status: Accepted

Solution code:
def f(n):
    s=str(n)
    return sum([int(s[i]) for i in range(len(s))])

sunuke=[]
for i in range(16):
    for j in range(1,500):
        sunuke.append(j*(10**i)-1)

sunuke=list(set(sunuke))
sunuke.sort()
sunuke.pop(0)
L=len(sunuke)

tmp1,tmp2=sunuke[L-1],f(sunuke[L-1])
ans=[sunuke[L-1]]
for i in range(len(sunuke)-2,-1,-1):
    x=sunuke[i]
    if x*tmp2<=tmp1*f(x):
        ans.append(x)
        tmp1,tmp2=x,f(x)

ans.sort()

    

for i in range(int(input())):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
def S(n):
  ans=0
  while n>0:
    ans=ans+n%10
    n=n//10
  return ans
ans=[]
A=[i for i in range(1,10**5)]
for i in range(1,11):
  for j in range(10**4,10**5):
    A.append(j*10**i+10**i-1)
A=A[::-1]
a=10**20
for i in range(len(A)):
  b=A[i]/S(A[i])
  if a>=b:
    ans.append(A[i])
    a=b
ans=ans[::-1]
for i in range(int(input())):
  print(ans[i])

Submission status: Accepted

Solution code:
K=int(input())
D={}
for i in range(1,10**4):
    for j in range(12):
        Sunuke=str(i)+("9"*j)
        if len(Sunuke)<=15 and Sunuke not in D:
            S=0
            for k in range(len(Sunuke)):
                S+=int(Sunuke[k])
            D[int(Sunuke)]=S
D=list(D.items())
D.sort()
#print(D[:10])
import bisect

d=[10**16 for i in range(len(D))]
d[0]=0
ans=[0 for i in range(len(D))]
for i in range(len(D)):
    ans[bisect.bisect_right(d,D[i][0]/D[i][1])]=D[i][0]
    d[bisect.bisect_right(d,D[i][0]/D[i][1])]=D[i][0]/D[i][1]
    
#print(ans[:50])
ANS=[]
MAX=0
for i in range(len(ans)):
    if ans[i]>MAX:
        ANS.append(ans[i])
        MAX=ans[i]
#print(ANS[:100])
for i in range(K):
    print(ANS[i])
#print(d[:10])

Submission status: Accepted

Solution code:
K = int(input())

def snuke(n):
  n_list = [int(i) for i in list(str(n))]
  return n / sum(n_list)

ans = 1
digit = 0

while K > 0:
  print(ans)
  if snuke(ans + 10**digit) > snuke(ans + 10**(digit+1)):
    digit += 1
  ans += 10**digit
  K -= 1

Submission status: Accepted

Solution code:
K = int(input())

def snuke(n):
  sum_num = sum(map(int, list(str(n))))
  return n / sum_num

ans = 1
digit = 0
while K > 0:
  print(ans)
  if snuke(ans + 10**digit) > snuke(ans + 10**(digit+1)):
    digit += 1
  ans += 10**digit
  K -= 1

Submission status: Accepted

Solution code:
def S(n):
    return sum(map(int, str(n)))


K = int(input())

x = 1
d = 1
while K > 0:
    if S(x) * d < x:
        x += 9 * d
        d *= 10
    else:
        print(x)
        x += d
        K -= 1

Submission status: Accepted

Solution code:
"""
A = []

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

def f(d, a, s):
  global A
  if d>=20:
    return True
  if s==0:
    t = int("9"*len(str(a)))
    if a*S(t)<=t*S(a):
      if a<=10**15:
        A += [a]
      return True
    else:
      return False
  for i in range(min(s, 9)+1)[::-1]:
    if not f(d+1, a+i*10**d, s-i):
      return False
  return True

for i in range(1, 9*15+1):
  print i
  f(0, 0, i)

A.sort()
B = []

m = A[-1]
for i in range(len(A))[::-1]:
  if A[i]*S(m)<=m*S(A[i]):
    m = A[i]
    B += [A[i]]
for b in B[::-1]:
  print b
"""

"""
def S(x):
  return sum(map(int, str(x)))

A = []
for i in range(10000):
  for j in range(15):
    s = int(str(i)+"9"*j)
    if 0<s<=10**15:
      A += [s]
A = list(set(A))
A.sort()

B = []
m = A[-1]
for i in range(len(A))[::-1]:
  if A[i]*S(m)<=m*S(A[i]):
    m = A[i]
    B += [A[i]]
for b in B[::-1]:
  print b
"""

S = [
1,
2,
3,
4,
5,
6,
7,
8,
9,
19,
29,
39,
49,
59,
69,
79,
89,
99,
199,
299,
399,
499,
599,
699,
799,
899,
999,
1099,
1199,
1299,
1399,
1499,
1599,
1699,
1799,
1899,
1999,
2999,
3999,
4999,
5999,
6999,
7999,
8999,
9999,
10999,
11999,
12999,
13999,
14999,
15999,
16999,
17999,
18999,
19999,
20999,
21999,
22999,
23999,
24999,
25999,
26999,
27999,
28999,
29999,
39999,
49999,
59999,
69999,
79999,
89999,
99999,
109999,
119999,
129999,
139999,
149999,
159999,
169999,
179999,
189999,
199999,
209999,
219999,
229999,
239999,
249999,
259999,
269999,
279999,
289999,
299999,
309999,
319999,
329999,
339999,
349999,
359999,
369999,
379999,
389999,
399999,
499999,
599999,
699999,
799999,
899999,
999999,
1099999,
1199999,
1299999,
1399999,
1499999,
1599999,
1699999,
1799999,
1899999,
1999999,
2099999,
2199999,
2299999,
2399999,
2499999,
2599999,
2699999,
2799999,
2899999,
2999999,
3099999,
3199999,
3299999,
3399999,
3499999,
3599999,
3699999,
3799999,
3899999,
3999999,
4099999,
4199999,
4299999,
4399999,
4499999,
4599999,
4699999,
4799999,
4899999,
4999999,
5999999,
6999999,
7999999,
8999999,
9999999,
10999999,
11999999,
12999999,
13999999,
14999999,
15999999,
16999999,
17999999,
18999999,
19999999,
20999999,
21999999,
22999999,
23999999,
24999999,
25999999,
26999999,
27999999,
28999999,
29999999,
30999999,
31999999,
32999999,
33999999,
34999999,
35999999,
36999999,
37999999,
38999999,
39999999,
40999999,
41999999,
42999999,
43999999,
44999999,
45999999,
46999999,
47999999,
48999999,
49999999,
50999999,
51999999,
52999999,
53999999,
54999999,
55999999,
56999999,
57999999,
58999999,
59999999,
69999999,
79999999,
89999999,
99999999,
109999999,
119999999,
129999999,
139999999,
149999999,
159999999,
169999999,
179999999,
189999999,
199999999,
209999999,
219999999,
229999999,
239999999,
249999999,
259999999,
269999999,
279999999,
289999999,
299999999,
309999999,
319999999,
329999999,
339999999,
349999999,
359999999,
369999999,
379999999,
389999999,
399999999,
409999999,
419999999,
429999999,
439999999,
449999999,
459999999,
469999999,
479999999,
489999999,
499999999,
509999999,
519999999,
529999999,
539999999,
549999999,
559999999,
569999999,
579999999,
589999999,
599999999,
609999999,
619999999,
629999999,
639999999,
649999999,
659999999,
669999999,
679999999,
689999999,
699999999,
799999999,
899999999,
999999999,
1099999999,
1199999999,
1299999999,
1399999999,
1499999999,
1599999999,
1699999999,
1799999999,
1899999999,
1999999999,
2099999999,
2199999999,
2299999999,
2399999999,
2499999999,
2599999999,
2699999999,
2799999999,
2899999999,
2999999999,
3099999999,
3199999999,
3299999999,
3399999999,
3499999999,
3599999999,
3699999999,
3799999999,
3899999999,
3999999999,
4099999999,
4199999999,
4299999999,
4399999999,
4499999999,
4599999999,
4699999999,
4799999999,
4899999999,
4999999999,
5099999999,
5199999999,
5299999999,
5399999999,
5499999999,
5599999999,
5699999999,
5799999999,
5899999999,
5999999999,
6099999999,
6199999999,
6299999999,
6399999999,
6499999999,
6599999999,
6699999999,
6799999999,
6899999999,
6999999999,
7099999999,
7199999999,
7299999999,
7399999999,
7499999999,
7599999999,
7699999999,
7799999999,
7899999999,
7999999999,
8999999999,
9999999999,
10999999999,
11999999999,
12999999999,
13999999999,
14999999999,
15999999999,
16999999999,
17999999999,
18999999999,
19999999999,
20999999999,
21999999999,
22999999999,
23999999999,
24999999999,
25999999999,
26999999999,
27999999999,
28999999999,
29999999999,
30999999999,
31999999999,
32999999999,
33999999999,
34999999999,
35999999999,
36999999999,
37999999999,
38999999999,
39999999999,
40999999999,
41999999999,
42999999999,
43999999999,
44999999999,
45999999999,
46999999999,
47999999999,
48999999999,
49999999999,
50999999999,
51999999999,
52999999999,
53999999999,
54999999999,
55999999999,
56999999999,
57999999999,
58999999999,
59999999999,
60999999999,
61999999999,
62999999999,
63999999999,
64999999999,
65999999999,
66999999999,
67999999999,
68999999999,
69999999999,
70999999999,
71999999999,
72999999999,
73999999999,
74999999999,
75999999999,
76999999999,
77999999999,
78999999999,
79999999999,
80999999999,
81999999999,
82999999999,
83999999999,
84999999999,
85999999999,
86999999999,
87999999999,
88999999999,
89999999999,
99999999999,
109999999999,
119999999999,
129999999999,
139999999999,
149999999999,
159999999999,
169999999999,
179999999999,
189999999999,
199999999999,
209999999999,
219999999999,
229999999999,
239999999999,
249999999999,
259999999999,
269999999999,
279999999999,
289999999999,
299999999999,
309999999999,
319999999999,
329999999999,
339999999999,
349999999999,
359999999999,
369999999999,
379999999999,
389999999999,
399999999999,
409999999999,
419999999999,
429999999999,
439999999999,
449999999999,
459999999999,
469999999999,
479999999999,
489999999999,
499999999999,
509999999999,
519999999999,
529999999999,
539999999999,
549999999999,
559999999999,
569999999999,
579999999999,
589999999999,
599999999999,
609999999999,
619999999999,
629999999999,
639999999999,
649999999999,
659999999999,
669999999999,
679999999999,
689999999999,
699999999999,
709999999999,
719999999999,
729999999999,
739999999999,
749999999999,
759999999999,
769999999999,
779999999999,
789999999999,
799999999999,
809999999999,
819999999999,
829999999999,
839999999999,
849999999999,
859999999999,
869999999999,
879999999999,
889999999999,
899999999999,
909999999999,
919999999999,
929999999999,
939999999999,
949999999999,
959999999999,
969999999999,
979999999999,
989999999999,
999999999999,
1099999999999,
1199999999999,
1299999999999,
1399999999999,
1499999999999,
1599999999999,
1699999999999,
1799999999999,
1899999999999,
1999999999999,
2099999999999,
2199999999999,
2299999999999,
2399999999999,
2499999999999,
2599999999999,
2699999999999,
2799999999999,
2899999999999,
2999999999999,
3099999999999,
3199999999999,
3299999999999,
3399999999999,
3499999999999,
3599999999999,
3699999999999,
3799999999999,
3899999999999,
3999999999999,
4099999999999,
4199999999999,
4299999999999,
4399999999999,
4499999999999,
4599999999999,
4699999999999,
4799999999999,
4899999999999,
4999999999999,
5099999999999,
5199999999999,
5299999999999,
5399999999999,
5499999999999,
5599999999999,
5699999999999,
5799999999999,
5899999999999,
5999999999999,
6099999999999,
6199999999999,
6299999999999,
6399999999999,
6499999999999,
6599999999999,
6699999999999,
6799999999999,
6899999999999,
6999999999999,
7099999999999,
7199999999999,
7299999999999,
7399999999999,
7499999999999,
7599999999999,
7699999999999,
7799999999999,
7899999999999,
7999999999999,
8099999999999,
8199999999999,
8299999999999,
8399999999999,
8499999999999,
8599999999999,
8699999999999,
8799999999999,
8899999999999,
8999999999999,
9099999999999,
9199999999999,
9299999999999,
9399999999999,
9499999999999,
9599999999999,
9699999999999,
9799999999999,
9899999999999,
9999999999999,
10999999999999,
11999999999999,
12999999999999,
13999999999999,
14999999999999,
15999999999999,
16999999999999,
17999999999999,
18999999999999,
19999999999999,
20999999999999,
21999999999999,
22999999999999,
23999999999999,
24999999999999,
25999999999999,
26999999999999,
27999999999999,
28999999999999,
29999999999999,
30999999999999,
31999999999999,
32999999999999,
33999999999999,
34999999999999,
35999999999999,
36999999999999,
37999999999999,
38999999999999,
39999999999999,
40999999999999,
41999999999999,
42999999999999,
43999999999999,
44999999999999,
45999999999999,
46999999999999,
47999999999999,
48999999999999,
49999999999999,
50999999999999,
51999999999999,
52999999999999,
53999999999999,
54999999999999,
55999999999999,
56999999999999,
57999999999999,
58999999999999,
59999999999999,
60999999999999,
61999999999999,
62999999999999,
63999999999999,
64999999999999,
65999999999999,
66999999999999,
67999999999999,
68999999999999,
69999999999999,
70999999999999,
71999999999999,
72999999999999,
73999999999999,
74999999999999,
75999999999999,
76999999999999,
77999999999999,
78999999999999,
79999999999999,
80999999999999,
81999999999999,
82999999999999,
83999999999999,
84999999999999,
85999999999999,
86999999999999,
87999999999999,
88999999999999,
89999999999999,
90999999999999,
91999999999999,
92999999999999,
93999999999999,
94999999999999,
95999999999999,
96999999999999,
97999999999999,
98999999999999,
99999999999999,
100999999999999,
101999999999999,
102999999999999,
103999999999999,
104999999999999,
105999999999999,
106999999999999,
107999999999999,
108999999999999,
109999999999999,
119999999999999,
129999999999999,
139999999999999,
149999999999999,
159999999999999,
169999999999999,
179999999999999,
189999999999999,
199999999999999,
209999999999999,
219999999999999,
229999999999999,
239999999999999,
249999999999999,
259999999999999,
269999999999999,
279999999999999,
289999999999999,
299999999999999,
309999999999999,
319999999999999,
329999999999999,
339999999999999,
349999999999999,
359999999999999,
369999999999999,
379999999999999,
389999999999999,
399999999999999,
409999999999999,
419999999999999,
429999999999999,
439999999999999,
449999999999999,
459999999999999,
469999999999999,
479999999999999,
489999999999999,
499999999999999,
509999999999999,
519999999999999,
529999999999999,
539999999999999,
549999999999999,
559999999999999,
569999999999999,
579999999999999,
589999999999999,
599999999999999,
609999999999999,
619999999999999,
629999999999999,
639999999999999,
649999999999999,
659999999999999,
669999999999999,
679999999999999,
689999999999999,
699999999999999,
709999999999999,
719999999999999,
729999999999999,
739999999999999,
749999999999999,
759999999999999,
769999999999999,
779999999999999,
789999999999999,
799999999999999,
809999999999999,
819999999999999,
829999999999999,
839999999999999,
849999999999999,
859999999999999,
869999999999999,
879999999999999,
889999999999999,
899999999999999,
909999999999999,
919999999999999,
929999999999999,
939999999999999,
949999999999999,
959999999999999,
969999999999999,
979999999999999,
989999999999999,
999999999999999,
]

K = input()
for s in S[:K]:
  print s

Submission status: Accepted

Solution code:
def sunuke_sum(arg):
    sum_digit = 0
    for char in arg:
        sum_digit += int(char)
    return sum_digit


input_num = int(input())

sunuke_dict = {}

min_sunuke_div = 10 ** 20
for d in reversed(range(1, 16)):
    for n in reversed(range(10, 1000)):
        i = n * (10 ** d) + (10 ** d - 1)
        sunuke_div = i / sunuke_sum(str(i))
        sunuke_dict[i] = sunuke_div

for i in reversed(range(1, 110)):
    sunuke_div = i / sunuke_sum(str(i))
    sunuke_dict[i] = sunuke_div

sunuke_sorted = sorted(sunuke_dict.items())
sunuke_list = []

for value, div_value in reversed(sunuke_sorted):
    if min_sunuke_div >= div_value:
        sunuke_list.append(value)
        min_sunuke_div = div_value

sunuke_list.reverse()

for i in range(0, input_num):
    print(str(sunuke_list[i]))

Submission status: Accepted

Solution code:
m=float("INF")
sunukes=[]
for i in range(7,-1,-1):
    for j in range(1000,10,-1):
        #print(i,j)
        sunuke=j*(100**i)-1
        s=str(sunuke)
        sn=0
        for k in range(len(s)):
            sn+=int(s[k])
        x=sunuke/sn
        #print(sunuke,x)
        if x<=m :
            m=x
            sunukes.append(sunuke)
for i in range(9,0,-1):
    sunukes.append(i)
sunukes=sunukes[::-1]
k=int(input())
#print(sunukes)
for i in range(k):
    print(sunukes[i])

Submission status: Accepted

Solution code:
K = int(input())
 
res = [(0, 0)]
mm = 0
cands = []
for i in range(1, 1000):
  v = i
  for j in range(16):
    cands.append(v)
    v = 10 * v + 9

cands = list(sorted(set(cands)))

for x in cands:
  i = sum(ord(c) - ord('0') for c in str(x))
  while x / i < res[-1][0]:
    res = res[:-1]
  res.append((x / i, x))
 
for i in range(1, K + 1):
  print(res[i][1])

Submission status: Accepted

Solution code:
K = int(input())

P = [n for n in range(1, 10)]
Q = [n for n in range(1, 10)]
for d in range(20):
    if d < 12:
        for m in range(10, 100):
            P.append(int(str(m)+"9"*d))
            Q.append(m//10+m%10+9*d)
    else:
        for m in range(100, 1000):
            P.append(int(str(m)+"9"*(d-1)))
            Q.append(sum([int(s) for s in str(m)])+9*(d-1))

L = len(P)
c = 0
for i, (p, q) in enumerate(zip(P, Q)):
    ok = True
    for j in range(i+1, L):
        np, nq = P[j], Q[j]
        if np*q < nq*p:
            ok = False
            break
    if ok:
        print(p)
        c += 1
    if c == K:
        break


"""
import matplotlib.pyplot as plt

A = []
B = []
for n in range(-1+10**10, 10**14, 10**10):
    m = sum([int(s) for s in str(n)])
    A.append(n)
    B.append(n/m)


plt.plot(A, B)
plt.show()
"""

Submission status: Accepted

Solution code:
k = int(input())

# 関数S(n)
def S(num):
  s = sum(map(int,list(str(num))))
  return num/s

#1~9と 〇9-> 〇99 -> 〇999 を出力
ten = 0
now = 1
# k回ループ
for _ in range(k) :
  print(now)
  # 桁が変わる時にten+=1する
  if S(now + 10**ten) > S(now + 10**(ten + 1)) :
    #print(now,S(now + 10**ten), S(now + 10**(ten + 1)))
    ten += 1
  now += 10**ten

Submission status: Accepted

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

from math import log10

def f(x):
    s=sum(int(c) for c in str(x))
    return x/s

def next(x):
    d=int(log10(x))
    A=list(str(x))
    res=-1
    score=INF
    for i in range(d,-1,-1):
        A[i]='9'
        tmp=int(''.join(A))
        if(score>f(tmp)):
            score=f(tmp)
            res=tmp
    return res

def resolve():
    k=int(input())
    if(k<10):
        for i in range(1,k+1):
            print(i)
        return
    for i in range(1,10):
        print(i)
    k-=9
    now=9
    for _ in range(k):
        now=next(now+1)
        print(now)
resolve()

Submission status: Accepted

Solution code:
def s(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret
numbers = [999999999999999999]
while numbers[-1] > 1:
    for d in range(0, 100):
        n = numbers[-1]
        m = n - 10 ** d
        if n * s(m) >= m * s(n):
            numbers.append(m)
            break
numbers = list(reversed(numbers))

n = int(input())
for i in range(n):
    print(numbers[i])

Submission status: Accepted

Solution code:
import sys
k=int(input())
if k<=9:
    for i in range(1,k+1):
        print(i)
    sys.exit()
for i in range(1,9):
    print(i)
count=8
s=0
lst=[]
for i in range(1,17):
    for j in range(1,1000):
        a=j*(10**i)-1
        b=list(str(a))
        c=0
        for u in b:
            c+=int(u)
        if (10**i)*c>=a:
            lst.append(a)
            count+=1
        else:
            break
lst.sort()
s=1
while s<len(lst):
    if lst[s]==lst[s-1]:
        lst.pop(s)
    else:
        s+=1
for i in range(k-8):
    print(lst[i])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(read())

cand = set()
for d in range(15):
    for x in range(1,1000):
        y = x*(10**d)-1
        cand.add(y)
cand.remove(0)

cand = sorted(cand,reverse=True)

def S(n):
    x = 0
    while n:
        q,r = divmod(n,10)
        x += r
        n = q
    return x

answer = []
opt_S = 1
opt_N = cand[0]+1
for x in cand:
    s = S(x)
    if x*opt_S <= s * opt_N:
        answer.append(x)
        opt_S = s; opt_N = x

print('\n'.join(map(str,answer[::-1][:K])))

Submission status: Accepted

Solution code:
K = int(input())

def S(x) :
    ret = 0
    while x :
        ret += x % 10
        x //= 10
    return ret

L = set()
nine = ''
for i in range(16) :
    for j in range(1, 1000) :
        x = int(str(j) + nine)
        L.add(x)
    nine += '9'
    
L = list(L)
L.sort()

v = [1]
n = [1]

for l in L[1:] :
    x = l / S(l)
    while v[-1] > x :
        v.pop()
        n.pop()
    v.append(x)
    n.append(l)

for i in range(K) :
    print(n[i])