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 os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

K = int(sys.stdin.buffer.readline())


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


def f(n):
    return n / S(n)


# @debug
def min_m(n, s):
    # n < m, S(m) == s となる最小の m
    assert S(n) < s
    ret = list(map(int, list(str(n))))
    d = 0
    for _ in range(s - S(n)):
        while ret[~d] == 9:
            d += 1
            if d >= len(ret):
                ret = [0] + ret
        ret[~d] += 1
    return int(''.join(map(str, ret)))


# n = 10 ** 15 - 1
# print(n, S(n), f(n))
# S(n) の最大値は 135


# S(m) / S(n) <= m / n
# 右辺は単調増加するので、
# S(m) <= S(n) のものは見なくていい。
# S(m) > S(n) のものを試す
# MAX_S = 200
# ans = set()
# # 最後に9がつくやつだけ試せば良さそう
# for cnt9 in range(16):
#     i = 1
#     ok = True
#     while ok:
#         n = int(str(i) + '9' * cnt9)
#         s = S(n)
#         ok = True
#         if n == 10099:
#             pass
#         for s in range(S(n) + 1, MAX_S):
#             m = min_m(n, s)
#             # S(m) / S(n) <= m / n
#             ok &= S(m) * n <= S(n) * m
#         if ok:
#             ans.add(n)
#         i += 1
# li = 'ans = [' + ','.join(map(str, sorted(ans))) + ']'
# print(li)

ans = [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,1009999999999999,1019999999999999,1029999999999999,1039999999999999,1049999999999999,1059999999999999,1069999999999999,1079999999999999,1089999999999999,1099999999999999,1109999999999999,1119999999999999,1129999999999999,1139999999999999,1149999999999999,1159999999999999,1169999999999999,1179999999999999,1189999999999999,1199999999999999,1299999999999999,1399999999999999,1499999999999999,1599999999999999,1699999999999999,1799999999999999,1899999999999999,1999999999999999,2099999999999999,2199999999999999,2299999999999999,2399999999999999,2499999999999999,2599999999999999,2699999999999999,2799999999999999,2899999999999999,2999999999999999,3099999999999999,3199999999999999,3299999999999999,3399999999999999,3499999999999999,3599999999999999,3699999999999999,3799999999999999,3899999999999999,3999999999999999,4099999999999999,4199999999999999,4299999999999999,4399999999999999,4499999999999999,4599999999999999,4699999999999999,4799999999999999,4899999999999999,4999999999999999,5099999999999999,5199999999999999,5299999999999999,5399999999999999,5499999999999999,5599999999999999,5699999999999999,5799999999999999,5899999999999999,5999999999999999,6099999999999999,6199999999999999,6299999999999999,6399999999999999,6499999999999999,6599999999999999,6699999999999999,6799999999999999,6899999999999999,6999999999999999,7099999999999999,7199999999999999,7299999999999999,7399999999999999,7499999999999999,7599999999999999,7699999999999999,7799999999999999,7899999999999999,7999999999999999,8099999999999999,8199999999999999,8299999999999999,8399999999999999,8499999999999999,8599999999999999,8699999999999999,8799999999999999,8899999999999999,8999999999999999,9099999999999999,9199999999999999,9299999999999999,9399999999999999,9499999999999999,9599999999999999,9699999999999999,9799999999999999,9899999999999999,9999999999999999,10099999999999999,10199999999999999,10299999999999999,10399999999999999,10499999999999999,10599999999999999,10699999999999999,10799999999999999,10899999999999999,10999999999999999,11099999999999999,11199999999999999,11299999999999999,11399999999999999,11499999999999999,11599999999999999,11699999999999999,11799999999999999,11899999999999999,11999999999999999,12099999999999999,12199999999999999,12299999999999999,12399999999999999,12499999999999999,12599999999999999,12699999999999999,12799999999999999,12899999999999999,12999999999999999,13999999999999999,14999999999999999,15999999999999999,16999999999999999,17999999999999999,18999999999999999,19999999999999999,20999999999999999,21999999999999999,22999999999999999,23999999999999999,24999999999999999,25999999999999999,26999999999999999,27999999999999999,28999999999999999,29999999999999999,30999999999999999,31999999999999999,32999999999999999,33999999999999999,34999999999999999,35999999999999999,36999999999999999,37999999999999999,38999999999999999,39999999999999999,40999999999999999,41999999999999999,42999999999999999,43999999999999999,44999999999999999,45999999999999999,46999999999999999,47999999999999999,48999999999999999,49999999999999999,50999999999999999,51999999999999999,52999999999999999,53999999999999999,54999999999999999,55999999999999999,56999999999999999,57999999999999999,58999999999999999,59999999999999999,60999999999999999,61999999999999999,62999999999999999,63999999999999999,64999999999999999,65999999999999999,66999999999999999,67999999999999999,68999999999999999,69999999999999999,70999999999999999,71999999999999999,72999999999999999,73999999999999999,74999999999999999,75999999999999999,76999999999999999,77999999999999999,78999999999999999,79999999999999999,80999999999999999,81999999999999999,82999999999999999,83999999999999999,84999999999999999,85999999999999999,86999999999999999,87999999999999999,88999999999999999,89999999999999999,90999999999999999,91999999999999999,92999999999999999,93999999999999999,94999999999999999,95999999999999999,96999999999999999,97999999999999999,98999999999999999,99999999999999999,100999999999999999,101999999999999999,102999999999999999,103999999999999999,104999999999999999,105999999999999999,106999999999999999,107999999999999999,108999999999999999,109999999999999999,110999999999999999,111999999999999999,112999999999999999,113999999999999999,114999999999999999,115999999999999999,116999999999999999,117999999999999999,118999999999999999,119999999999999999,120999999999999999,121999999999999999,122999999999999999,123999999999999999,124999999999999999,125999999999999999,126999999999999999,127999999999999999,128999999999999999,129999999999999999,130999999999999999,131999999999999999,132999999999999999,133999999999999999,134999999999999999,135999999999999999,136999999999999999,137999999999999999,138999999999999999,139999999999999999]
for a in ans[:K]:
    print(a)

Submission status: Accepted

Solution code:
def keta(string):
    t = int(string)
    keta_sum = sum([int(i) for i in string])
    return t / keta_sum, t
    
tmp = []
for j in range(20):
    for i in range(0, 10000):
        if (i + 1) % 10 == 0:
            continue
        num = str(i) + j*"9"
        if num == "0":
            continue
        tmp.append(keta(num))

k = int(input())
tmp = sorted(tmp)
ans = []
for i, num in tmp:
    if not ans:
        ans.append(num)
    elif ans[-1] < num:
        ans.append(num)
for i in range(k):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque
import math

def dig(K):
    k = str(K)
    ans = 0

    for i in k:
        ans += int(i)
    return ans

K = int(input())
m = 0
ans = []

q = deque([[1,1],[2,1]])
now = 1
i = 2

while True:

        i += now   
        
        num = i / dig(i)

        while q[-1][1] > num:
            q.pop()

        q.append([i , num])

        if len(q) > 2 * K:
            break

        if math.log10(q[-1][0] - q[-2][0]) == math.log10(q[-1][0] - q[-2][0]) // 1:
            now = 10 ** (int(math.log10(q[-1][0] - q[-2][0])))

for i in range(K):
    print (q[i][0])

Submission status: Accepted

Solution code:
# https://pitsbuffersolution.com/compro/atcoder/arc099d.php

k = int(input())

def calc_snuke(n):
    return n/sum(map(int,str(n)))

a = []
for i in range(1000):
    if i% 10 == 9 or i%100 == 99 or i%1000 == 999:
        continue
    a.append(i)

que = []
for i in range(16):
    m = 10**i-1
    for ai in a:
        w = ai*10**i+m
        if 0<w<=10**15-1:
            que.append(w)
que.sort(reverse=True)
mi = float("inf")
ans = []
for i in que:
    q = calc_snuke(i)
    if q > mi:
        continue
    ans.append(i)
    mi = q
ans.sort()
print(*ans[:k], sep="\n")

Submission status: Accepted

Solution code:
import math

def snuke(x):
    y=0
    xx=x
    while x!=0:
        y+=x%10
        x=x//10
    return xx/y

a=1
k=int(input())
kaisu=0
incre=1
        
while kaisu<k:
    before=a
    print(a)
    b=snuke(a)
    if (a+1)%(10*incre)!=0:
        a+=incre
    else:
        a+=1
        b=a
        snukes=[]
        for j in range(int(math.log10(a+1))):
            b+=9*(10**j)
            snukes.append(b)
        #print(snukes)
        snukes2=[]
        for sks in snukes:
            snukes2.append(snuke(sks))
        if len(snukes2)==1:
            a=snukes[0]
        else:
            answer=[]
            for sn2 in range(len(snukes2)-1):
                if snukes2[sn2]<=snukes2[sn2+1]:
                    answer.append(snukes[sn2])
            #print(answer)
            answer.append(snukes[-1])
            a=answer[0]
            incre=a-before
    kaisu+=1

Submission status: Accepted

Solution code:
def ss(n):
    return n / s(n)


def s(n):
    return sum([int(a) for a in str(n)])


K = int(input())
n = 0
d = 1
while K > 0:
    t1 = ss(n + d)
    t2 = ss(n + 10 * d)
    if t1 > t2:
        d *= 10
    n += d
    print(n)
    K -= 1

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:
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:
K=int(input())
a=0
from math import log10,ceil
from functools import lru_cache
@lru_cache(maxsize=None)
def sn(n):
    x=n
    y=0
    while x>0:
        y+=x%10
        x//=10
    return n/y
for i in range(K):
    if i<9:
        a+=1
        print(a)
        continue
    for d in range(int(log10(a))+1):
        y=10**(d+1)*ceil(a/(10**(d+1))+1)-1
        if d==0 or sn(y)<sn(at):
            at=y
    a=at
    print(a)

Submission status: Accepted

Solution code:
K = int(input())


def digitsum(x):
    if x == 0:
        return 0
    return x % 10 + digitsum(x // 10)


ans = set(list(range(1, 9)))
for i in range(1, 15):
    base = 10**i - 1
    j = 0
    while True:
        x = int(str(j) + str(base))
        y = int(str(j + 1) + str(base))
        if x * digitsum(y) <= y * digitsum(x):
            ans.add(x)
            j += 1
        else:
            break
print(*sorted(ans)[:K], sep='\n')

Submission status: Accepted

Solution code:
import sys
K=int(input())

def f(x):
    a=str(x)
    num=0
    for s in a:
        num+=int(s)
    return x/num
L=[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]
L=set(L)
for i in range(4,16):
    for j in range(10,1000):
        s=str(j)+'9'*(i-2)
        L.add(int(s))
L=list(L)
#print(len(L))
L.sort()
for j in range(len(L)):
    flag=True
    for k in range(j+1,len(L)):
        if L[k]/L[j]>20:
            break
        if f(L[j])>f(L[k]):
            flag=False
            break
    if flag:
        print(L[j])
        K=K-1
    if K==0:
        sys.exit()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

K = int(input())


def snuke_factor(n):
    """
    n / 各桁の和
    :param n:
    :return:
    """
    if n == 0:
        return INF
    return n / sum(list(map(int, str(n))))


# for i in range(9999, 1000000, 10000):
#     print(i, int(snuke_factor(i)))

# e ずつ増やす
d = 1
# 10 の倍数
e = 1
# 9999...
suffix = 0
for _ in range(K):
    print(d * e + suffix)
    if d % 10 == 9:
        if snuke_factor((d + 1) * e + suffix) > snuke_factor((d + 10) * e + suffix):
            # 増やす速度を 10 倍にする
            e *= 10
            d //= 10
            # 9 を 1 桁増やす
            suffix = (suffix + 1) * 10 - 1
    d += 1

Submission status: Accepted

Solution code:
A = []
p = 10**18
for i in range(15,2,-1):
  l = max(0,10**(i-3) - 1)
  m = 10**(i-3)
  for j in range(999,9,-1):
    c = l+m*j
    s = c/sum(map(int,str(c)))
    if s-p <= 1e-7:
      A.append(c)
      p = s

for i in range(9,0,-1):A.append(10*i+9)
for i in range(9,0,-1):A.append(i)
A = A[::-1]
A = list(set(A))
A.sort() 


X = int(input())
for i in range(X):print(A[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# Luis Yoichi Morales January 2019


K=int(raw_input())
 
s=0
tmp=1
ans=0
A=[]
bfr=0
def func(a):
    sa=str(a)
    tmp=sum(int(s) for s in sa)
    return float(a)/tmp
 
while(ans<K):
    tmp2=tmp+10**s
    tmp3=tmp+2*10**s
    if func(tmp2) > func(tmp3):
        s+=1
    else:
        print(tmp)
        tmp = tmp2
        bfr=func(tmp)
        ans+=1

Submission status: Accepted

Solution code:
k = int(input())
#n = int(input())

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

def T(x):
	return x / S(x)

n = 1
snuke = [1]
x = 1

while n < k:
	x += 1
	cand = x
	T_min = T(x)
	for d in range(len(str(x))-1):
		if T((x // (10**(d+1)) + 1) * (10**(d+1)) - 1) < T_min:
			T_min = T((x // (10**(d+1)) + 1) * (10**(d+1)) - 1)
			cand = (x // (10**(d+1)) + 1) * (10**(d+1)) - 1
	x = cand
	snuke.append(x)
	n += 1

print(*snuke, sep="\n")

Submission status: Accepted

Solution code:
K = int(open(0).read())

def f(n):
    n += 1
    d = 1
    c = sum(map(int, str(n)))
    p = n; q = c
    while d < n:
        b = (n // d) % 10
        n += (9 - b) * d
        c += 9 - b
        if p*c > n*q:
            p = n
            q = c
        d *= 10
    return p

ans = []
n = 0
for i in range(K):
    n = f(n)
    ans.append("%d\n" % n)
open(1, 'w').writelines(ans)

Submission status: Accepted

Solution code:
K = int(open(0).readline())

def f(n):
    k = n
    n += 1
    d = 1
    c = sum(map(int, str(n)))
    p = n; q = c
    while d < n:
        b = (n // d) % 10
        n += (9 - b) * d
        c += 9 - b
        if p*c > n*q:
            p = n
            q = c
        d *= 10
    return p

ans = []
n = 0
for i in range(K):
    n = f(n)
    ans.append("%d\n" % n)
open(1, 'w').writelines(ans)

Submission status: Accepted

Solution code:
f=lambda x:sum(map(int,str(x)))
ans=[]

def check(x):
    y=f(x)
    while ans:
        p=ans[-1]
        if p*y>x*f(p):ans.pop(-1)
        else:break
    ans.append(x)

k=int(input())
for i in range(1,100):
    check(i)
a,b=0,1
while a<1e12:
    for i in range(100,1000):
        check(i*b+a)
    a=a*10+9
    b*=10

for i in range(k):
    print(ans[i])

Submission status: Accepted

Solution code:
def ss(n):
    return n / s(n)
def s(n):
    return sum([int(a) for a in str(n)])

K = int(input())
n = 0
d = 1
while K > 0:
    t1=ss(n+d)
    t2=ss(n+10*d)
    if t1 > t2:
        d *= 10
    n += d
    print(n)
    K -= 1

Submission status: Accepted

Solution code:
import sys


def df(N: int) -> int:
    y = 0
    while N > 0:
        y += N % 10
        N //= 10
    return y


def func(N: int) -> int:
    min_val, min_t = N / df(N), N
    d = 0
    while N > 0:
        N //= 10
        d = d * 10 + 9
        NN = N * (d + 1) + d
        val = NN / df(NN)
        if min_val > val:
            min_val = val
            min_t = NN
    return min_t


N = int(sys.stdin.readline())
z = 0
for _ in range(N):
    z = func(z + 1)
    print(z)

Submission status: Accepted

Solution code:
def R(x):
    return x / sum(map(int, str(x)))
K = int(input())
D = 0
l = 0
for i in range(K):
    D += 10**l
    print(D)
    if 10**l < R(D+10**l):
        l += 1

Submission status: Accepted

Solution code:
# time complexity: O((lgN)^4)
# space complexity: O((lgN)^2)

def digit_sum(num):
    ds = 0
    while num > 0:
        ds += num % 10
        num //= 10
    return ds


K = int(input())
candidates = []
digit_sums = []
for i in range(15):
    base = 10**i
    for j in range(1, 150):
        candidate = j * base + (base - 1)
        candidates.append(candidate)

candidates = sorted(list(set(candidates)))
digit_sums = [digit_sum(candidate) for candidate in candidates]

snuke_nums = []
smaller_as_snuke = lambda n, m, ds_n, ds_m: True if n * ds_m <= m * ds_n else False
for i, candidate in enumerate(candidates):
    ds_cand = digit_sums[i]
    for j in range(i + 1, len(candidates)):
        other_num = candidates[j]
        ds_other = digit_sums[j]
        if not smaller_as_snuke(candidate, other_num, ds_cand, ds_other):
            break
    else:
        snuke_nums.append(candidate)

for snuke_num in snuke_nums[:K]:
    print(snuke_num)

Submission status: Accepted

Solution code:
def digit_sum(num):
    ds = 0
    while num > 0:
        ds += num % 10
        num //= 10
    return ds


K = int(input())
candidates = []
digit_sums = []
for i in range(15):
    base = 10**i
    for j in range(1, 150):
        candidate = j * base + (base - 1)
        candidates.append(candidate)

candidates = sorted(list(set(candidates)))
digit_sums = [digit_sum(candidate) for candidate in candidates]

snuke_nums = []
smaller_as_snuke = lambda n, m, ds_n, ds_m: True if n * ds_m <= m * ds_n else False
for i, candidate in enumerate(candidates):
    ds_cand = digit_sums[i]
    for j in range(i + 1, len(candidates)):
        other_num = candidates[j]
        ds_other = digit_sums[j]
        if not smaller_as_snuke(candidate, other_num, ds_cand, ds_other):
            break
    else:
        snuke_nums.append(candidate)

for snuke_num in snuke_nums[:K]:
    print(snuke_num)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def digit_sum(num:int, base:int) -> int:
    if num < base:
        return num
    else:
        return digit_sum(int(num/base), base) + (num % base)

def snuke(num: int):
    return num / digit_sum(num, 10)

k = ni()

snuke_nums = [i for i in range(1,10)]
res = 9
cur = 9

if k <= res:
    for s in snuke_nums[:k]:
        print(s)

else:
    while res != k:
        cur += 1
        
        cands = []
        for i in range(len(str(cur))):
            cands.append(int(str(cur)[:-i-1] + "9"*(i+1)))
            
        mi = float("inf")
        for c in cands:
            if snuke(c) < mi:
                cur = c
                mi = snuke(c)
                
        snuke_nums.append(cur)
        res += 1
        
    for s in snuke_nums:
        print(s)

Submission status: Accepted

Solution code:
K = int(input())
al = []

def sums(i):
    s = 0
    old = i
    while i>0:
        s += i%10
        i = i//10
    return (s,old)

for i in range(1,1000):
    al.append(sums(i))
for j in range(4,16):
    for k in range(100,1000):
        al.append(sums(k*(10**(j-3))+10**(j-3)-1))
anslist = []
al.reverse()
maxs,maxi = sums(10**15)
for j in al:
    if maxs*j[1] <= maxi*j[0]:
        anslist.append(j[1])
        maxs = j[0]
        maxi = j[1]
anslist.reverse()

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

Submission status: Accepted

Solution code:


f = lambda x: sum(map(int, str(x)))

a, b = 1, 1
for i in range(int(input())):
	print(a)
	a += 1
	b = a
	for j in range(0, len(str(a)) + 1):
		t = a % 10 ** j
		t = a - t + 10 ** j - 1
		if b * f(t) > t * f(b):
			b = t
	a = b

Submission status: Accepted

Solution code:
def s(n):
    if n < 10:
        return n
    else:
        return n % 10 + s(n // 10)
n = 0
for _ in range(int(input())):
    n += 1
    minn = n
    d = 1
    while n >= d:
        d *= 10
        m = (n // d + 1) * d - 1
        if minn * s(m) > m * s(minn):
            # minn / s(minn) > m / s(m)
            minn = m
    n = minn
    print(n)

Submission status: Accepted

Solution code:
def digitsum(x):
	s = 0
	while x > 0:
		s,x = s+x%10,x//10
	return s
l = list(range(1,10))
for i in range(10,100000):
	while digitsum(i)*l[-1] > digitsum(l[-1])*i:
		l.pop()
	l.append(i)
for length in range(6,20):
	for j in range(1000,10000):
		i = j*10**(length-4)+10**(length-4)-1
		while digitsum(i)*l[-1] > digitsum(l[-1])*i:
			l.pop()
		l.append(i)
k = int(input())
for i in range(0,k):
	print(l[i])

Submission status: Accepted

Solution code:
def s(n):
    if n<10:
        return n
    else:
        return n%10+s(n//10)
n=0
for _ in [0]*int(input()):
    n +=1    
    minn = n
    d = 1
    while n>=d:
        d *= 10    
        m = (n//d+1)*d-1
        if minn*s(m)>m*s(minn):
            minn = m
    n = minn
    print(n)

Submission status: Accepted

Solution code:
k=int(input())
n=1
t=1
l=0
for i in range(k):
	print(n)
	if int(n/t)%10==9:
		if n+t<=(9*l+int((n+t)/(t*10))%10+int((n+t)/(t*100))%100+int((n+t)/(t*1000))%1000)*t:
			pass
		else:
			t *= 10
			l += 1
	n += t

Submission status: Accepted

Solution code:
k = int(input())
def ispf(n,m):
    return (((9 * n) - 1)*pow(10, n) + 1) + pow(10, n) * (sum([int(l) for l in str(m)]) - 10*m)
result = []
for n in range(100):
    for i in range(100000):
        if ispf(n,i)<0:
            break
        for j in range(10):
            result.append(int(str(i) + str(j) + '9'*n))
for item in sorted(list(set(result[1:])))[:k]:
    print(item)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import fractions
s = lambda n: sum(map(int, str(n)))

cands = []
for a in range(1000):
    for b in range(20):
        cands += [ a * 10 ** b + (10 ** b - 1) ]

snukes = []
min_f = float('inf')
for n in reversed(sorted(cands)):
    if n == 0 or (snukes and snukes[-1] == n):
        continue
    f = fractions.Fraction(n, s(n))
    if f <= min_f:
        min_f = f
        snukes += [ n ]
snukes.reverse()

k = int(input())
for n in snukes[: k]:
    print(n)