問題一覧 > 通常問題

No.334 門松ゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 178
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
15 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君は勝てません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。