No.1313 Don't Say N Game (4)
タグ : / 解いたユーザー数 96
作問者 :
trineutron
/ テスター :
platinum
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もしくは右上の雲マークをクリックしてアカウントを作成してください。