Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
整数 n に対して,n を十進法で表したときの各桁の和を S(n) で表すことにします. たとえば,S(123) = 1 + 2 + 3 = 6 です.
正の整数 n であって,m > n であるような任意の正の整数 m に対して \frac{n}{S(n)} \leq \frac{m}{S(m)} が成り立つようなものを, すぬけ数 と呼ぶことにします.
整数 K が与えられたとき,すぬけ数を小さいほうから K 個列挙してください.
制約
- 1 \leq K
- K 番目のすぬけ数は 10^{15} 以下
入力
入力は以下の形式で標準入力から与えられる.
K
出力
K 行出力せよ.i 行目には,i 番目に小さいすぬけ数を出力せよ.
入力例 1
10
出力例 1
1 2 3 4 5 6 7 8 9 19
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