問題一覧 > 通常問題

No.1313 N言っちゃダメゲーム (4)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 95
作問者 : trineutrontrineutron / テスター : platinumplatinum
6 ProblemId : 3402 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 02:07:23

問題文

あなたとGrantは、いわゆる「2121言っちゃダメゲーム(棒取りゲームというところも)」を正の整数N,KN,Kを使って拡張したゲームを何度もしてきた。ルールは以下のとおりである。

1. まず先攻のプレイヤーは00が与えられる。
2. そこからNN以上を宣言しないように(宣言したら負けになる)、与えられた数字に1K1〜Kのどれかの整数を加算したものを宣言し相手プレイヤーに渡す。
3. 勝負がつくまで代わり代わりに 2. を繰り返す。

あなたがこのゲームの勝ち方を知ったため、Grantはこのゲームに勝てなくなっていた。
そこで、Grantは以下のルールを追加してあなたと勝負することにした。

4. 11以上N1N-1以下の「危険な数字」がいくつか指定される。「危険な数字」を宣言してしまうと負けになる。

まずあなたが先攻となりゲームを始める。
この時、どちらも負けないように動くと考え、自然数N,KN,Kが与えられた時、
あなたが勝つことが出来る場合は、最初に宣言して勝てる数字を全て改行区切りで出力せよ。勝つことが出来ない場合は00を出力せよ。

入力

N KN\ K
SS

N,KN, Kは整数
1K<N2×1051 \le K < N \le 2\times 10^5
SSoまたはxからなる長さN1N-1の文字列
SSii文字目がxのときiiは「危険な数字」

出力

あなたが勝つことが出来る場合は、最初に宣言して勝てる数字を全て改行区切りで出力せよ。勝つことが出来ない場合は00を改行付きで出力せよ。

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。