問題一覧 > 通常問題

No.1313 Don't Say N Game (4)

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 96
作問者 : trineutron / テスター : platinum
お気に入りにしたユーザー ProblemId : 3402 / 自分の提出
問題文最終更新日: 2022-04-26 02:07:23
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2020 (順位表) の他の問題:

Problem Statement

You and Grant have played many times a game that extends the so-called "Don't Say $21$ Game" (also known in some places as the stick-taking game) using positive integers $N,K$. The rules are as follows.

1. First, the first player is given $0$.
2. From there, while avoiding declaring a number that is $N$ or greater (declaring one means losing), the player declares the given number plus any integer from $1〜K$ and passes it to the opponent.
3. The players alternate repeating step 2. until the game is decided.

Since you have learned how to win this game, Grant has become unable to win it.
So Grant decided to challenge you with the following rule added.

4. Some "dangerous numbers" between $1$ and $N-1$, inclusive, are specified. Declaring a "dangerous number" means losing.

You start the game as the first player.
Here, assuming that both players move so as not to lose, and given natural numbers $N,K$,
if you can win, output all the numbers you can declare first in order to win, separated by newlines. If you cannot win, output $0$.

Input

$N\ K$
$S$

$N, K$ are integers
$1 \le K < N \le 2\times 10^5$
$S$ is a string of length $N-1$ consisting of o or x
If the $i$-th character of $S$ is x, then $i$ is a "dangerous number"

Output

If you can win, output all the numbers you can declare first in order to win, separated by newlines. If you cannot win, output $0$ followed by a newline.

Sample

Sample 1
Input
21 3
oooooooooooooooooooo
Output
0

This is the ordinary Don't Say 21 Game.
If the second player chooses numbers well,
the first player always loses.

Sample 2
Input
21 3
oooxoooxoooxoooxooox
Output
3

The "dangerous numbers" are 4, 8, 12, 16, 20.
You can win by declaring 3 first. Declaring 1 or 2 does not allow you to win, so the answer is 3.

Sample 3
Input
50 5
ooxoooxxoxoooxooooxxxoxxooxoxoxooooxxooxooooxoooo
Output
2

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