No.362 門松ナンバー
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 :
koyumeishi
/ テスター :
🐬hec
タグ : / 解いたユーザー数 46
作問者 :
koyumeishi
/ テスター :
🐬hec
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。