問題一覧 > 通常問題

No.3636 Find Supersuperfibonacci Number

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 15
作問者 : kazuppa / テスター : 👑 loop0919
お気に入りにしたユーザー ProblemId : 13859 / 自分の提出
問題文最終更新日: 2026-08-21 23:15:16
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

Introduction

This problem is based on Problem D "Find Superfibonacci Number" of yukicoder contest 509, which was published last week.

For that reason, this problem was scheduled to be published right after that contest ended, but due to the writer's carelessness, the submission date was off by one week. We apologize.

Problem Statement

You are given a positive integer $K$. Find the smallest positive integer $n$ that satisfies all of the following conditions. If no such integer exists, output -1.

  • The digit sum of $n$ is $K$.
  • Let $x$ be the unique integer satisfying $10^x\leq n< 10^{x+1}$, and let $n_i$ be the digit in the $10^i$ place of $n$ when interpreted in decimal. Then $n_{i+2} \gt n_{i+1} + n_i$ holds for every non-negative integer $i$ satisfying $0\leq i\leq x-2$.

Note that the second condition is always satisfied when $n< 100$.

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

$T$
$Test_1$
$Test_2$
$\vdots$
$Test_T$
Each test case is given in the following format. 
$K$

Output

Output $T$ lines.

On the $i$-th line, output the answer to the $i$-th test case.

Sample

Sample 1
Input
2
16
9231
Output
79
-1

For the first test case, $n=952,8521,97$ and others satisfy the conditions in the problem statement. The smallest positive integer satisfying the conditions is $79$, so output $79$.

For the second test case, no $n$ satisfying the conditions exists, so output -1.

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