問題一覧 > 通常問題

No.3625 Find Superfibonacci Number

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 46
作問者 : 👑 loop0919 / テスター : ぽえ yuusaan kazuppa
お気に入りにしたユーザー ProblemId : 13600 / 自分の提出
問題文最終更新日: 2026-08-17 21:45:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 509 (順位表) の他の問題:

Problem Statement

You are given a positive integer $K$. Find the smallest positive integer $n$ that satisfies all of the following conditions.

  • The digit sum of $n$ is $K$.
  • Let $n_i$ denote the value of the $10^i$ place of $n$ when interpreted as a decimal number. Then there exists a non-negative integer $i$ such that $n_{i+2} \gt n_{i+1} + n_i$.

You are given $T$ test cases; answer each of them.

Constraints

  • All input values are integers.
  • $1 \leq T \leq 1000$
  • $1 \leq K \leq 10^6$
  • The sum of $K$ over all test cases is at most $10^6$.

Input

The input is given from Standard Input in the following format.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$K$

Output

Print the answers to the test cases in order, separated by newlines.

Sample

Sample 1
Input
3
4
1
18
Output
301
100
1908

For the $1$st test case, the digit sum of $301$ is $4$, and $3 > 0 + 1$ holds for $i = 0$.
Thus, $301$ satisfies the conditions. No positive integer less than or equal to $300$ satisfies the conditions, so the answer is $301$.

For the $3$rd test case, when $n = 1908$, $n_{i + 2} > n_{i + 1} + n_i$ does not hold for $i = 1$, but it holds for $i = 0$.
The digit sum is $18$, so this satisfies the conditions.

Note that the answer may be $2^{64}$ or greater.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。