No.334 門松ゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 136
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
8 ProblemId : 930 / 出題時の順位表
問題文最終更新日: 2016-05-24 14:45:29

問題文

門松列とは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君は勝てません。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。