問題一覧 > 通常問題

No.1149 色塗りゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 177
作問者 : 👑 Kiri8128Kiri8128 / テスター : neterukunneterukun
17 ProblemId : 4650 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-08 16:02:05

問題文

この問題はインタラクティブな問題です。

色塗りゲームをしましょう! 色塗りゲームは、1列に並んだ $N$ マスに順に色を塗っていくゲームです。 マスには $1$ から $N$ の番号が付いています。
ゲームの進行とルールは次のとおりです。

  • 最初、どのマスにも色は塗られていません。
  • あなたから始めて、交互にマスに色を塗ります。
  • 1回のターンでは、1マスまたは 隣り合う2マス を選んで塗ります。 ただし、すでに色が塗られたマスを選ぶことはできません。 なお $1\le i\le N-1$ についてマス $i$ とマス $i+1$ は隣り合っています。 これ以外の組は隣り合っていません。
  • 自分のターンに塗るマスがなくなった方が負けです。相手の勝ちになります。
相手のきり君に勝ってください!

入出力

最初に整数 $N$ が1行で与えられます。
$N$

$N$ は整数であり、 $1\le N \le 100$ を満たすことが保証されます。


あなたの順番では、色を塗るマスの数 $k$ と、そのうち最も小さい番号 $x$ を空白区切りで出力してください。
$k\ x$
$k$ と $x$ は整数で、下記を満たす必要があります。
  • $k=1$ または $k=2$
  • $1\le x \le N+1-k$

きり君の順番では、まず状態を表す $t$ が与えられます。
$t$
$t$ は0以上3以下の整数です。それぞれの意味は下記の通りです。
  • $t=0$ のとき、きり君には塗るマスが残っていなくて、あなたが勝ったことを示します。
  • $t=1$ のとき、直前のあなたの入力が無効であることを示します。具体的には、制約を満たしていない、または既に塗ってあるマスを塗ろうとしています。
  • $t=2$ のとき、直後のきり君の手であなたが負けになることを示します。
  • $t=3$ のとき、直後のきり君のターンの後もゲームが継続することを示します。
$t=0$ または $t=1$ のときはこれ以上入力は与えられません。 ただちにプログラムを終了させてください。

$t=2$ または $t=3$ のときは、続いてきり君が色を塗るマスの数 $k$ と、そのうち最も小さい番号 $x$ が空白区切りで与えられます。
$k\ x$
これは有効な塗り方であることが保証されます。
$t=2$ の場合はこれを受け取った後、ただちにプログラムを終了させてください。
$t=3$ の場合は、あなたの順番に戻ります。

(補足)
$t=0$ を受け取り、正しくプログラムを終了した場合に限りACが得られます。
AC解法では $t=1$ および $t=2$ を受け取ることはありません。 なので $t=0$ または $t=3$ しか受け取らない前提でもACを得ることはできます。 ACでない場合にも正しいジャッジを受け取りたい場合には $t=1$ および $t=2$ の場合も考慮する必要があります。


なおこの問題の制約下では、必ず勝つ方法が存在することが示せます。

注意点

  • 出力のたびに標準出力を Flush させてください。
  • ゲームが終了した場合は、その時点でプログラムを終了させる必要があることに注意してください。
  • 上記が守られない場合のジャッジは不定です( TLE や RE になることがあります)。

サンプル

以下は説明用の例です。実際のテストケースにこれと同じ挙動をするケースがあることは保証されません。

「入力」欄と「出力」欄は時系列順に並んでいます。 $i=1,\ 2,\ \cdots$ の順に、入力欄と出力欄の $i$ 行目のどちらか(空行でない方)が実行されます。 (各 $i$ について、 $i$ 行目には「入力」欄と「出力」欄のどちらかが空行になっています。 空行は行番号を合わせるためのもので、実際に空行の入力が与えられたり空行の出力を求められたりするものではありません。)

サンプル1
入力
7

3
2 3

3
1 7

0
出力

2 5


1 1


1 2

最初に $N=7$ が与えられます(「入力」の1行目)。 マスの状況は □□□□□□□です(左から $i$ 番目が■のときマス $i$ が塗られていることを、□のとき塗られていないことを表します)。
あなたは "2 5" と出力しました(「出力」の2行目)。これはマス5から2マスを塗る(つまりマス5とマス6を塗る)ことを表します。 マスの状況は□□□□■■□になりました。
続いて "3" および "2 3" を受け取ります(「入力」の3行目および4行目)。 きり君がマス3とマス4を塗って、ゲームが継続していることを示します。マスの状況は□□■■■■□です。
次にあなたは "1 1" と出力しました(「出力」の5行目)。マス1を塗ることを表します。マスの状況は■□■■■■□です。
続いて "3" および "1 7" を受け取ります(「入力」の6行目および7行目)。 きり君がマス7を塗って、ゲームが継続していることを示します。マスの状況は■□■■■■■です。
次にあなたは "1 2" と出力しました(「出力」の8行目)。マス2を塗ることを表します。マスの状況は■■■■■■■です。
続いて "0" を受け取ります(「入力」の9行目)。これは、きり君には塗るマスがなく、あなたがゲームに勝ったことを表します。
この時点でプログラムを終了させてください。

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