問題一覧 > 通常問題

No.249 N言っちゃダメゲーム (2)

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 64 MB / 通常問題
タグ : / 解いたユーザー数 385
作問者 : LayCurseLayCurse
11 ProblemId : 692 / 出題時の順位表
問題文最終更新日: 2017-06-25 01:08:32

問題文

あなたとGrantは、いわゆる「$21$言っちゃダメゲーム(棒取りゲームというところも)」をしている。

このゲームを何度やっても負けてばかりなので、ルールを拡張して正整数 $N$ と $K$ を使って以下のゲームを考える。

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

このゲームは、$N$と$K$が決まったら、先手・後手、どちらが勝つかわかることが知られています。

このとき、$N,K$ を変えて、$1000$ 回ゲームを行うことにする。
まず最初のゲームはあなたが先攻としてゲームを開始します。
$2$ 回目以降のゲームでは、その前のゲームで負けたプレイヤーが自由に先攻か後攻かを選べます。
あなたもGrantもできるだけ勝つ回数が多くなるようにプレーするとしたとき、あなたが勝つ回数を求めてください。

あらかじめすべてのゲームの$N,K$は分かっているものとする。

入力

$N_1$ $K_1$
$N_2$ $K_2$
$\vdots$
$N_{1000}$ $K_{1000}$

$N_i, K_i$ は $i$ 回目のゲームにおける $N,K$ の値です。
$N_i \geq 2$
$K_i \geq 2$
入力ファイルは4MBを超えない。

出力

あなたが勝つ回数を1行で出力してください。

サンプル

入力が $1000$ 行と大きいため、この問題にはサンプル入出力は用意されていません。
もしかしたら、No.8 N言っちゃダメゲームが参考になるかもしれません。

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