200991: [AtCoder]ARC099 D - Snuke Numbers

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

> 定义函数 $\rm S(x)$ 表示 $x$ 各个位上数字之和。求前 $k$ 个这样的 $n$: > $$ > \forall m>n,\frac{n}{\mathrm{S}(n)}\leq \frac{m}{\mathrm{S}(m)} > $$ > $k\geq 1$。

加入题单

上一题 下一题 算法标签: