問題一覧 > 通常問題

No.2165 Let's Play Nim!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 45
作問者 : nullnull / テスター : 遭難者遭難者
1 ProblemId : 8188 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-16 00:11:38

問題

ジャッジと Nim をして勝利してください。

問題文

この問題はリアクティブ問題です。

整数 $n$ と長さ $n$ の整数列 $a$ が与えられます。

ゲームはジャッジとあなたの二人でプレイされます。先攻と後攻はあなたが選ぶことができ、先攻が最初に行動し、その後後攻が行動し、その後も交互に行動します。一回の行動は次に示す一連の操作です。

  1. $1 \le i \le n$ かつ $a_i \neq 0$ を満たす整数 $i$ を $1$ つ選ぶ。ただし、そのような $i$ が存在しない場合、負けとなりゲームが終了する。
  2. $1 \le k \le a_i$ を満たす整数 $k$ を選び、$a_i$ を $a_i -k$ で置き換える。

ゲームは有限回の操作で終了するので、行動を繰り返すことで必ず負けたプレイヤーが発生し、負けていないプレイヤーが勝ちとなります。

ゲームに勝利してください。

evil ケースについて

本問題では、リアクティブジャッジの速度の都合上制約を小さくしておりますが、 高速な解法との区別のため evil ケース(こちら 「正解判定のポリシー」を参照してください)を導入しております。

このケースでは高速な解法でも言語、実装によっては AC を保証できない可能性があります。(ジャッジ結果には影響しません。)

制約

  • $1 \le n \le 10^4$
  • $1 \le a_i \le 10^4$
  • $\sum_{i=1}^{n} a_i \le 10^4$
  • 入出力はすべて整数。

evil ケースの制約

  • $1 \le n \le 7.5 \times 10^4$
  • $1 \le a_i \le 7.5 \times 10^4$
  • $\sum_{i=1}^{n} a_i \le 7.5 \times 10^4$
  • 入出力はすべて整数。

入出力

まず、整数 $n$ が与えられます。

$n$

その後、$n$ 個の整数が与えられます。

$a_1\ a_2\ \dots\ a_n$

次に、あなたは先攻と後攻どちらかを選択します。

$t$

ここで、先攻を選択するのなら $t=1$、後攻を選択するのであれば $t=0$ である必要があります。その後、ゲームが終了するまで行動を繰り返します。

あなたの行動の時、あなたは整数 $i, k(1 \le i \le n, 1 \le k \le a_i)$ を選び、出力しなければいけません。

$i\ k$

これは、あなたが $a_i$ を $a_i - k$ で置き換える行動を行ったことを表します。

その後、整数 $ret$ が与えられます。

$ret$

ここで、$ret=0$ ならゲームは続行、$ret = -1$ なら、プログラムを直ちに終了させてください。

ジャッジの行動の時、あなたは整数 $i, k(1 \le i \le n, 1 \le k \le a_i)$ を与えられます。

$i\ k$

これは、ジャッジが $a_i$ を $a_i - k$ で置き換える行動を行ったことを表します。

その後、整数 $ret$ が与えられます。

$ret$

ここで、$ret=0$ ならゲームは続行、$ret = -1$ なら、プログラムを直ちに終了させてください。

注意

  • ジャッジが最適に行動すると仮定したときジャッジの勝利が確定した段階で、ゲームが終了していなくてもジャッジからプログラムの終了 ($ret=-1$) を渡す場合があります。
  • 各出力のたびに末尾改行と flush をしてください。
  • 不正な出力や動作に対するジャッジは不定である可能性があります。

サンプル

入力出力説明
3$n=3$
2 1 3$a_1=2, a_2=1, a_3=3$
0$t=0$ で後手選択。
2 1ジャッジが $a_2=1$ を $1-1=0$ で置き換えた。
0ゲームは続行する。
3 2あなたが $a_3=3$ を $3-2=1$ で置き換えた。
0ゲームは続行する。
3 1ジャッジが $a_3=1$ を $1-1=0$ で置き換えた。
0ゲームは続行する。
1 2あなたが $a_1=2$ を $2-2=0$ で置き換えた。
-1あなたの勝ちである。やり取りを終了させる。
(0:11 修正)

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