No.334 門松ゲーム
問題文
門松列とは3つの整数が左からA、B、Cと並んでいる時に、
全ての値が異なりA、B、Cのうち2番目に大きな整数がAかCである場合をいう。
D君とE君はこの門松列を使った門松ゲームをする。
最初にN個の正の整数が横に1列に並んでいる。
まず、N個の整数のうち左からa番目の整数X、b番目の整数Y、c番目の整数Zを選ぶ $(a \lt b \lt c)$。
このX、Y、Zが門松列であればD君はこの3つの整数を消すことができる。
このとき消した3つの整数は以降使うことができない。
この操作を先手がD君でE君、D君、・・・の順に交互に同じように繰り返す。
門松ゲームでは門松列を作れずに整数を消せなかったほうが負けとなる。
D君とE君は共に勝つために最善な選択をする。
先手のD君が必ず勝つために選ぶべき1手目の選択方法は何か?
左から何番目と何番目と何番目かで答えよ(0-index)。
答えが複数ある場合はそのうち辞書順で最も早いものを答えよ。
また、D君が勝てないようであれば-1を出力せよ。
入力
$N$ $K_0\ K_1\ \dots\ K_{N-1}$
Nは正の整数の個数。$3\le N \le 12$。
$K_i$は左からi番目の正の整数の値。$1\le K_i \le 20$。
出力
D君が勝つための辞書順で最も早い最初の1手が左からa番目、b番目、c番目$(a< b < c)$であるとき、
答えを「a b c」のように数値と数値の間に半角を入れて1行で出力せよ。
D君がどうやっても勝てない場合には「-1」を1行で出力せよ。
ただし、最後に改行を忘れずに、
サンプル
サンプル1
入力
6 2 3 5 7 4 1
出力
0 4 5
D君がまず左から0番目、4番目、5番目の整数「2、4、1」を選ぶ。
「2、4、1」は門松列であるのでこの3つの整数を消す。
残った配列は3、5、7であるがE君はここから門松列を作れない。
「0 4 5」の他に「1 4 5」、「2 3 5」でもA君が勝てるが辞書順で最も早いのは「0 4 5」である。
サンプル2
入力
5 1 2 3 4 5
出力
-1
最初にD君がどのようにしても門松列を作れず整数を消せません。
よって、D君は勝つ選び方ができないので-1を出力します。
サンプル3
入力
12 5 1 13 10 12 12 12 3 9 13 17 18
出力
-1
D君は勝てません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。