No.1313 N言っちゃダメゲーム (4)
タグ : / 解いたユーザー数 95
作問者 : trineutron / テスター : platinum
問題文
あなたとGrantは、いわゆる「言っちゃダメゲーム(棒取りゲームというところも)」を正の整数を使って拡張したゲームを何度もしてきた。ルールは以下のとおりである。
1. まず先攻のプレイヤーはが与えられる。
2. そこから以上を宣言しないように(宣言したら負けになる)、与えられた数字にのどれかの整数を加算したものを宣言し相手プレイヤーに渡す。
3. 勝負がつくまで代わり代わりに 2. を繰り返す。
あなたがこのゲームの勝ち方を知ったため、Grantはこのゲームに勝てなくなっていた。
そこで、Grantは以下のルールを追加してあなたと勝負することにした。
4. 以上以下の「危険な数字」がいくつか指定される。「危険な数字」を宣言してしまうと負けになる。
まずあなたが先攻となりゲームを始める。
この時、どちらも負けないように動くと考え、自然数が与えられた時、
あなたが勝つことが出来る場合は、最初に宣言して勝てる数字を全て改行区切りで出力せよ。勝つことが出来ない場合はを出力せよ。
入力
は整数
はo
またはx
からなる長さの文字列
の文字目がx
のときは「危険な数字」
出力
あなたが勝つことが出来る場合は、最初に宣言して勝てる数字を全て改行区切りで出力せよ。勝つことが出来ない場合はを改行付きで出力せよ。
サンプル
サンプル1
入力
21 3 oooooooooooooooooooo
出力
0
ふつうの21言っちゃダメゲームです。
後攻のプレイヤーがうまく数字を選べば、
先攻のプレイヤーは必ず負けます。
サンプル2
入力
21 3 oooxoooxoooxoooxooox
出力
3
「危険な数字」は4, 8, 12, 16, 20です。
最初に3を宣言すれば勝てます。1または2を宣言すると勝つことが出来ないため、3が答えになります。
サンプル3
入力
50 5 ooxoooxxoxoooxooooxxxoxxooxoxoxooooxxooxooooxoooo
出力
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。