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:
from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque


def read():
    return int(input())


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


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


def S(n):
    ret = 0

    while n:
        ret += n % 10
        n = n // 10

    return ret



# minimum = 9999999999999999
# for n in reversed(range(1, 100000000)):
#     if n / S(n) <= minimum:
#         minimum = n / S(n)
#         # print(n, minimum)
#         print(n)


# ans_list = []
# n = 999999999999999
# MIN = 999999999999999
# while n >= 100000000:
#     l = len(str(n))
#     if n / S(n) <= MIN:
#         print(n)
#         MIN = n / S(n)
#     n -= 10 ** (l - 3)

# lis = []
# while True:
#     n = read()
#     if n == 0:
#         break
#     lis.append(n)
#
# print(",".join(list(map(str, lis))))

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

K = read()
for i in range(K):
    print(ans_list[i])

Submission status: Accepted

Solution code:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

nums=[]

num=0
pow10=1

# add a few possible answers
for i in range(16):
    t="9"*i
    if t!="": nums.append(int(t))
    for j in range(1,1000):
        t=str(j)+"9"*i
        if len(t)>15: continue
        nums.append(int(t))

def dsum(x):
    t=0
    while x:
        t+=x%10
        x//=10
    return t

# remove some bad numbers
out=[]
rat=[]
for i in sorted(set(nums)):
    j=i/dsum(i)
    while rat and rat[-1]>j:
        out.pop(-1)
        rat.pop(-1)
    out.append(i)
    rat.append(j)

#print(len(out))

#for i in range(len(out)): print(i,out[i],rat[i])

#for i in range(len(nums)):
#    print(i,dsum(nums[i]),nums[i]/dsum(nums[i]))

k=int(input())
for i in range(k):
    print(out[i])

Submission status: Accepted

Solution code:
K = int(input())
d = 0
n = 1
while K > 0:
  if ((n+1)*10**d-1)*(sum(map(int,str(n+1)))+9*d) <= ((n+2)*10**d-1)*(sum(map(int,str(n)))+9*d):
    print(n,'9'*d, sep='')
    K -= 1
    n += 1
  else:
    d += 1
    n = (n+1)//10

Submission status: Accepted

Solution code:
def ii():
    return int(input())


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


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


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


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


def main():
    K = ii()
    snuke_list = list(range(1, 10))

    for n in range(1, 17):
        c = 1
        while True:
            if snuke(10 ** n * c - 1) < snuke(10 ** n * (c+1) - 1):
                if not 10 ** n * c - 1 in snuke_list:
                    snuke_list.append(10 ** n * c - 1)
                c += 1
            else:
                break

    snuke_list = sorted(snuke_list)
    for i in range(K):
        print(snuke_list[i])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import Fraction
L = []
for i in range(1, 18):
    for j in range(1, 9*i+1):
        if (j-1)//9 >= i-1:
            temp = str(9-(-j%9)) + "9"*(i-1)
        else:
            temp = "1"
            t = j-1
            for rest in range(i-1, 0, -1):
                if t <= 9*(rest-1):
                    temp += "0"
                else:
                    temp += str(t-9*(rest-1))
                    t = 9*(rest-1)
        L.append((int(temp), j))
L.sort(reverse=True)
A = []
m = float("inf")
for l, k in L:
    if Fraction(l, k) <= m:
        A.append(l)
        m = Fraction(l, k)
k = int(input())
for i in range(k):
    print(A.pop())

Submission status: Runtime Error

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

k = int(input())

now = 1
step = 1


def sunuke(n):
    r = 0
    while n:
        r += n % 10
        n //= 10
    return r


def ok(a, b):
    return a * s(b) <= b*s(a)


while k:
    if ok(now, now+step):
        print(now)
        k -= 1
        now += step
    else:
        nstep = step*10
        while now % nstep != nstep-1:
            now += step
        step = nstep

Submission status: Runtime Error

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

k = int(input())

keta = 3

ans_c = []
sunuke = []
for i in range(1, 10**keta):  # 1~999
    a = i
    b = sum([int(j) for j in str(i)])
    tmp_sunuke = a/b
    ans_c.append(a)
    sunuke.append(tmp_sunuke)

base = 10
nines = 9
while(len(ans_c) <= 100000):
    for i in range(10**(keta-1), 10**keta):  # 1000~999
        a = i*base+nines
        b = sum([int(j) for j in str(i)])
        tmp_sunuke = a/b
        ans_c.append(a)
        sunuke.append(tmp_sunuke)
    base *= 10
    nines = nines*10 + 9
    # print(len(ans_c))

# print(ans_c)

tmp = 10**10
ans = []
for i in reversed(range(len(ans_c))):
    if sunuke[i] <= tmp:
        tmp = sunuke[i]
        ans.append(ans_c[i])
# print(ans)


for i in range(0, k):
    print(ans[-1-i])

Submission status: Runtime Error

Solution code:
K=int(input())
a=[]
x=0
plus=1
while(x<10**16+1):
    for i in range(9):
        a.append(x)
        x+=plus
    plus=plus*10
    
for i in range(1,K+1):
    print(a[i])

Submission status: Runtime Error

Solution code:
K=int(input())
a=[]
x=0
plus=1
while(x<10**15+1):
    for i in range(9):
        a.append(x)
        x+=plus
    plus=plus*10
    
for i in range(1,K+1):
    print(a[i])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
ll sum(ll x){
    ll ans=0;
    while(x>0) ans+=x%10,x/=10;
    return ans;
}
vec ans;
int search(ll x){
    if(x>pow(10,15)) return 0;
    ll y=x,k=0,a;
    while(y>0){
        if(y%10!=9){
            a=y%10;
            break;
        }
        k++;
        y/=10;
    }
    if(k==ll(log10(x))+1) ans.push_back(x),search(x+1);
    else{
        if(x<=sum(x)*ll(pow(10,k))) ans.push_back(x),search(x+pow(10,k));
        else search(x+(9-a)*pow(10,k));
    }
}
int main(){
    ll k;
    cin>>k;
    search(1);
    sort(all(ans));
    rep(i,k) cout<<ans[i]<<"\n";
}

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())

if (n - 1) % (k - 1) == 0:
    print((n - 1) // (k - 1))
else:
    print((n - 1) // (k - 1) + 1)

Submission status: Runtime Error

Solution code:
K = int(input())
ans = [10**15]
c = 10**15-1
s = 10**15

for i in range(11,0,-1):
    c = 10**i - 1
    for j in range(999,99,-1):
        C = j * (10**i) + c
        S = C/sum(list(map(int, str(C))))
        if S <= s:
            ans.append(C)
            s = S
for i in range(1,10):
    ans += [i,i*10+9,i*100+99]
ans.sort()    
for i in range(K):
    print(ans[i])

Submission status: Runtime Error

Solution code:
k=int(input())
ans=[2,3,4,5,6,7,8,9,]
for i in range(1,18):
    for j in range(1,10):
        ans.append(10**i*j)
for ii in range(k):
    print(ans[ii]-1)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
a = a[0]

b = [1,2,3,4,5,6,7,8,9,19,199,1999,19999,199999,1999999,19999999,199999999,1999999999,19999999999,199999999999,1999999999999,19999999999999,199999999999999]
for i in range(a):
    print(b[i])

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
a = a[0]

b = {1,2,3,4,5,6,7,8,9,19,199,1999,19999,199999,1999999,19999999,199999999,1999999999,
     19999999999,199999999999,1999999999999,19999999999999,199999999999999}
for i in range(a):
  print(b[i])

Submission status: Runtime Error

Solution code:
K = int(input())

numbers = []
for i in range(20):
    s = '9' * i
    for j in range(1, 10):
        t = str(j) + s
        numbers.append(int(t))

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

Submission status: Runtime Error

Solution code:
K = int(input())

numbers = []
for i in range(16):
    s = '9' * i
    for j in range(1, 10):
        t = str(j) + s
        numbers.append(int(t))

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

Submission status: Runtime Error

Solution code:
K = int(input())

numbers = []
for i in range(15):
    s = '9' * i
    for j in range(1, 10):
        t = str(j) + s
        numbers.append(int(t))

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

Submission status: Runtime Error

Solution code:
################################################################
##............................................................##
##........................######..............................##
##.........................#######............................##
##........................#######.............................##
##.......................#####..####..........................##
##.....................#####......#####.......................##
##....................#####.........#####.....................##
##..................#############....######...................##
##................#####....########....######.................##
##..............#####........####........#######..............##
##............#####................######..#########..........##
##..........#####............##############.#############.....##
##........####.....##############...#######...###############.##
##.....##............##########....######.......################
##..........................#####..#####......................##
##..........................####..#####.......................##
##..........................####.#####........................##
##..........................####.#####........................##
##.........................#####..............................##
##..........................###...............................##
##............................................................##
##............................................................##
##..................#########.................................##
##..............##############................................##
##...........############.....................................##
##....................####....................................##
##.....................########..................##...........##
##................##############...........############.......##
##.........################...#####...#####...##########......##
##..#######################....#######.........########.......##
##....########.....###########..######.........#######........##
##........#......#####.#######...######.......#######.........##
##.............######..####.......####################........##
##...........#####.....###........###################.........##
##........###..........###.........##.........................##
##....................####....................................##
##....................####....................................##
##.....................###....................................##
################################################################

if int(input()) != 10:
    exit(1)

Submission status: Runtime Error

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


def solve(K: int):
    count = 0
    for i in range(17):
        for j in range(1, 10):
            if count >= K:
                return
            tmp = (j + 1) * (10 ** i) - 1
            print(tmp)
            count += 1
    print(ret)
    return


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: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
K = int(input())
maxnum = 10**20
al = []

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

for i in range(1,100):
    al.append(sunuke(i))
for j in range(3,16):
    for k in range(10,100):
        al.append(sunuke(k*(10**(j-2))+10**(j-2)-1))
anslist = []
al.reverse()
for j in al:
    if j[0]<=maxnum:
        anslist.append(j[1])
        maxnum = j[0]
anslist.reverse()

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