問題一覧 > 通常問題

No.257 Don't Say N Game (3)

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : （AC するまで非表示） / 解いたユーザー数 210
作問者 : yuki2006
お気に入りにしたユーザー ProblemId : 708 / 自分の提出
問題文最終更新日: 2019-06-08 15:38:50
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
yukicoder 1周年記念 復習コンテスト R2 (順位表) の他の問題:

Note

2019/06/08 The judge was not correctly detecting cases that should be WA. The judge has been fixed and a rejudge has been performed.

Problem Statement

You and Grant have decided to play the so-called "Don't Say $21$ Game" (also known in some places as the stick-taking game).

Extending the rules, consider the following game using positive integers $N$ and $K$.

1. First, the first player is given $0$.
2. From there, the player declares the given integer plus some integer from $1$ to $K$ and passes it to the opponent, trying not to declare a number that is $N$ or greater (declaring such a number means losing).
3. The players take turns repeating step 2. until the game is decided.

Actually play against Grant and win.

First, $N$,$K$ are given, and
you may freely choose to go first or second.

For reasons of time, the opponent gives up if it judges that it has had no prospect of winning for 5 consecutive turns.
When the opponent gives up, a number that is $N$ or greater (at most $N+K$) is declared regardless of the state of the game. Interpret this as the opponent giving up, treat it as your win, and terminate your program.

Input and Output

Reading the first line gives you the values of $N$,$K$ for the game. 
$N$ $K$

$N$,$K$ are given as integers.
$1\le N \le 10^{8}$
$1\le K \le 10^{8}$

Next, only if you choose to go second, output 
0
.
If you go first, you do not need to do anything.

On your turn, output one integer to declare. 
A
If you use any other format or declare an integer that violates the rules of the game, the result is undefined.

On the opponent's turn, read the integer declared by the opponent from standard input. The format is a single integer. An integer value that is possible under the rules of the game is passed. 
B
After reading the input, it becomes your turn, and the above is repeated.
At this point, when you read an input that is $N$ or greater, terminate your program immediately.

End each output with a newline.
Flush the output after each output.
If you do not flush, the responding program may be unable to process the input and the time limit may be exceeded, which may result in an incorrect verdict.
Terminate your program immediately after the game ends. Otherwise, the judge's time limit may be exceeded, which may result in an incorrect verdict.
If you defeat the opponent, your answer is judged correct.

Notes

  • The judge's time limit includes the reaction time of the responding program.
  • Output to standard error is not regarded as invalid output.
  • Note that if the judge's code terminates first and you read input afterwards, this may result in TLE, a runtime error, or the like.

Sample

It is not guaranteed that the program behaves exactly according to this input and output.
A sample of the input is as follows.　 
21 3
2
5
8
12
17
19
22
A sample of the output is as follows. 
0
4
7
10
14
18
20
The first line of the input passes $N=21$,$K=3$.
Since the first line of the output is 0, you have chosen to go second.
Since the second line of the input is 2, the opponent has declared 2.
Since the second line of the output is 4, you have declared 4.
....
The eighth line of the input is 22, a number that is 21 or greater, so the opponent loses.
Terminate your program when the opponent outputs an integer that is $N$ or greater.

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