問題一覧 > 通常問題

No.362 門松ナンバー

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

問題文

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

  • A1,A2,A3 は全て異なる
  • 3 つの要素の中で A2 が最も大きい、または、A2 が最も小さい

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

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

正整数K(1≤K≤1010) が与えられるので、 K番目の門松ナンバーを求めてください。

入力

1行目にはテストケース数Tが与えられます。(1≤T≤10) 
T
以降T行に、各テストケースのK (1≤K≤1010) が与えられます。
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もしくは右上の雲マークをクリックしてアカウントを作成してください。