No.3625 Find Superfibonacci Number
loop0919
ぽえ
yuusaan
kazuppa
問題文最終更新日: 2026-08-14 21:41:18
yukicoder contest 509の他の問題:
問題文
正整数 $K$ が与えられます。 以下の条件をすべて満たす最小の正整数 $n$ を求めてください。
- $n$ の桁和は $K$ である。
- $n$ を十進数として解釈したときの $10^i$ の位の値を $n_i$ と定義したとき、 $n_{i+2} \gt n_{i+1} + n_i$ を満たす非負整数 $i$ が存在する。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- 入力される値はすべて整数
- $1 \leq T \leq 1000$
- $1 \leq K \leq 10^6$
- すべてのテストケースにわたる $K$ の総和は $10^6$ 以下
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$K$
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
サンプル
サンプル1
入力
3 4 1 18
出力
301 100 1908
$1$ 番目のテストケースについて、 $301$ の桁和は $4$ であり、かつ $i = 0$ に対して $3 > 0 + 1$ を満たします。
よって $301$ は条件を満たします。 $300$ 以下で条件を満たす正整数は存在しないため、 $301$ が答えです。
$3$ 番目のテストケースについて、 $n = 1908$ のとき $i = 1$ に対しては $n_{i + 2} > n_{i + 1} + n_i$ を満たしませんが、 $i = 0$ の場合満たします。
桁和が $18$ であり、これは条件を満たしています。
答えが $2^{64}$ 以上になる場合があることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。