問題一覧 > 通常問題

No.362 門松ナンバー

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : koyumeishikoyumeishi / テスター : 🐬hec🐬hec
5 ProblemId : 1010 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:31:44

問題文

門松列 とは $3$ 個の要素からなる数列 $A_1, A_2, A_3$ で以下の 2 つの条件を満たすものです。

  • $A_1, A_2, A_3$ は全て異なる
  • $3$ つの要素の中で $A_2$ が最も大きい、または、$A_2$ が最も小さい

$N$桁 ($3 \leq N$) の 正整数$X$ の上から $i$桁目 の数を $X_i$ とします。
数列 $X_i$, $X_{i+1}$, $X_{i+2}$ ($1 \leq i \leq N-2$ ) が全て門松列になるとき、$X$は門松ナンバーです。
例えば、 4514 や 893 は門松ナンバーですが、 114514 や 89 は門松ナンバーではありません。

$X$ が門松ナンバーであり、$X$ より小さい門松ナンバーが $K$個 存在するとき、$X$ は $K+1$番目 の門松ナンバーであるといいます。
1番目の門松ナンバーは102、404番目の門松ナンバーは893、1000番目の門松ナンバーは3296です。

正整数$K$($1 \leq K \leq 10^{10}$) が与えられるので、 $K$番目の門松ナンバーを求めてください。

入力

1行目にはテストケース数$T$が与えられます。($1 \leq T \leq 10$)
$T$
以降$T$行に、各テストケースの$K$ ($1 \leq K \leq 10^{10}$) が与えられます。
$K$

入力は全て整数です。

出力

各テストケース毎1行に、$K$番目の門松ナンバーを出力してください。

サンプル

サンプル1
入力
5
1
2
3
4
5
出力
102
103
104
105
106

1桁、2桁の門松ナンバーは存在しないことに注意してください。

サンプル2
入力
4
114
215
404
1000
出力
328
514
893
3296

サンプル3
入力
1
10000000000
出力
37294859064823

最大のケースです。 10^10 は 32bit整数型に収まりません。 計算時だけでなく入出力時のオーバーフローにも注意しましょう。
ちなみにこのケースはテストの最後の方に置いてあるので、 このケースでTLEノックアウトされることはありません。

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