初項の決定

例えば \(c_0\neq 0, c_1\neq 0\) ならば，\(1\) 桁の整数 \(c_0\) を初項とすることができます．巨大な公差を考えれば条件を満たす等差数列が作れるからです．

例えば 12358 ならば，初項 \(1\) かつ第 2 項が \(2358000\) であるような等差数列があります．

それ以外の場合にも同様に，巨大な第 2 項という選択肢を考えることで，初項を決めることができます．具体的には以下の通り計算できます．

• \(c_0\) が \(0\) ならば，\(c\) の先頭に \(1\) を補うことで，以降 \(c_0\) は \(0\) でないとして考える．
• \(c_0\) の次に \(0\) でない項が \(c_k\) であるとする．そのような \(k\) が存在しない場合 \(k=N\) とする．
• 初項は \(c_0c_1\cdots c_{k-1} = c_0 0\cdots 0\) である．

最小の公差の決定

初項 \(a\) を固定したとき，公差の最小化は，第 2 項の最小化と等価です．第 2 項の桁数を決め打って考えます．

第 \(2\) 項の桁数を \(n\) とするとき，第 \(2\) 項が列 \(c\) のどの部分であるかを考えます．\(n\) が十分小さいうちは，第 2 項は \(c\) の一部として確定します．

\(n\) が大きくなって第 2 項が列 \(c\) をはみ出すようになると，第 2 項は次のように作ることが求められます：

• \(n\) が \(a+1\) の桁数よりも小さいならば，適切な第 2 項を定めることは不可能です．
• \(n\) が \(a+1\) の桁数よりも大きいならば，作れる \(n\) 桁の正整数のうちで最小のものを作ることになります．
  • 基本的には \(c\) からはみ出た部分は 0 で埋めることになります．ただし，先頭の桁が 0 にならないように注意します．
• \(n\) が初項の桁数と一致する場合，第 \(2\) 項の prefix がいくつか決まっていて，それを延長して \(a+1\) 以上の正整数を作ることが目標です．
  • prefix 部分が \(a+1\) の prefix よりも小さいならば不可能です．
  • prefix 部分が \(a+1\) の prefix と一致するならば，\(a+1\) が最小の第 \(2\) 項です．
  • prefix 部分が \(a+1\) の prefix よりも大きいならば，はみ出た部分は（先頭の桁を除き） 0 で埋めてしまってよいです．

結局，第 2 項の桁数を決めると，答の候補が高々 1 つに限定できます．初項と第 2 項を決めてしまえば等差数列は一意に決まるので，あとは実際にこの等差数列を計算して条件を満たしているかを確認すればよいです．

桁数を決めるとごとに \(O(N)\) 時間の計算量．桁数の候補が \(O(N)\) 通りあるため，全体として \(O(N^2)\) 時間で解くことができます．

競技プログラミングでは珍しく，巨大な桁数の整数を扱うことになります．適切な言語やライブラリを使ってもよいですし，本問で必要なものは加減算のみなので\(10\) 進法表記をそのまま配列で表して実装しても簡単です．