AT_joig2026final_f 動物園 (Zoo)

あなたは動物園で $ N $ 匹のビーバーを飼育している．ビーバーには $ 0 $ から $ N-1 $ までの番号が付けられている． この動物園のビーバーはリンゴを食べる．それぞれのビーバーにはリンゴの好みがあり，ビーバー $ i $ ( $ 0 \leqq i \leqq N-1 $ ) は 重さ $ L_i $ グラム以上 $ R_i $ グラム以下のリンゴを好む．ただし，あなたはそれぞれの $ L_i $ と $ R_i $ の具体的な値を知らない． あなたは今から $ N $ 匹のビーバーの中から $ K $ 匹を選び展示ゾーンに入れようと考えている．ただし，次の条件を満たすような ビーバー $ i $ とビーバー $ j $ ( $ 0 \leqq i < j \leqq N-1 $ ) が同時に展示ゾーンに入ると，この $ 2 $ 匹はけんかを始めてしまう． - ビーバー $ i $ とビーバー $ j $ が両方とも好む重さのリンゴが存在する．つまり， $ L_i \leqq x \leqq R_i $ かつ $ L_j \leqq x \leqq R_j $ を 満たす実数 $ x $ が存在する． あなたは以前の経験からこのような $ (i, j) $ の組が存在しないように $ K $ 匹のビーバーを選ぶことができることを覚えていたが， 肝心のビーバーの選び方を忘れてしまった． あなたは以下の形式の質問を $ 1\,000 $ 回まで行うことができる． - $ 0 $ 以上 $ N $ 以下の整数 $ m $ および， $ 0 $ 以上 $ N-1 $ 以下の互いに異なる $ m $ 個の整数 $ t_0, t_1, \ldots, t_{m-1} $ を指定する． $ m $ 匹のビーバー $ t_0, t_1, \ldots, t_{m-1} $ のみから展示ゾーンに入れるビーバーを選ぶとき，最大で何匹のビーバーをけんかが起きないように展示ゾーンに 入れることができるかを尋ねる． あなたは質問を行うことで，具体的にビーバーを $ K $ 匹選んで展示ゾーンに入れる方法を一つ見つけたい．さらに，質問の回数はなるべく少なくしたい． ビーバーの数 $ N $ と展示ゾーンに入れるビーバーの数 $ K $ が与えられたとき， $ 1\,000 $ 回以下の質問で， ビーバーを $ K $ 匹選んで展示ゾーンに入れる方法を一つ見つけるプログラムを作成せよ． ### Input & Output Format この問題は**インタラクティブ問題**（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）である． 最初に，ビーバーの数 $ N $ と展示ゾーンに入れるビーバーの数 $ K $ が以下の形式で標準入力から与えられる． > $ N $ $ K $ あなたのプログラムはこれを受け取った後，採点プログラムとやり取りを行わなければならない． $ 1 $ 回の質問を行うには，以下の形式で採点プログラムとやり取りせよ． - まず，以下の形式で標準出力に出力せよ． > ? $ m $ $ t_0 $ $ t_1 $ $ \ldots $ $ t_{m-1} $ - $ m $ は $ 0 $ 以上 $ N $ 以下の整数である．これが満たされていない場合，**不正解\[1\]** と判定される． - その後に続く $ m $ 個の整数 $ t_0, t_1, \ldots, t_{m-1} $ は $ 0 $ 以上 $ N-1 $ 以下の互いに異なる整数である． これが満たされていない場合，**不正解\[2\]** と判定される． - その後，質問の回答を表す整数 $ r $ が以下の形式で標準入力から与えられる． > $ r $ ここで $ r $ は $ -1 $ 以上 $ N $ 以下の整数である． $ r = -1 $ であるとき，採点プログラムがあなたのプログラムを不正解であると判定したことを表す． **この場合，ただちにあなたのプログラムを終了せよ．** $ 0 \leqq r \leqq N $ であるとき， $ m $ 匹のビーバー $ t_0, t_1, \ldots, t_{m-1} $ のみから展示ゾーンに入れるビーバーを選ぶとき， 最大で $ r $ 匹のビーバーをけんかが起きないように展示ゾーンに入れることができることを表す． $ r > K $ である場合もあることに注意せよ． 質問は $ 1\,000 $ 回を超えて行ってはならない． $ 1\,000 $ 回を超えて行った場合，**不正解\[3\]** と判定される． ビーバーを $ K $ 匹選んで展示ゾーンに入れる方法を一つ回答するには，以下の形式で標準出力に出力せよ． > ! $ s_0 $ $ s_1 $ $ \ldots $ $ s_{K-1} $ - $ K $ 個の整数 $ s_0, s_1, \ldots, s_{K-1} $ は， $ K $ 匹のビーバー $ s_0, s_1, \ldots, s_{K-1} $ を展示ゾーンに入れることを表す． - $ s_0, s_1, \ldots, s_{K-1} $ は $ 0 $ 以上 $ N - 1 $ 以下の互いに異なる整数でなければならない． これが満たされていない場合，**不正解\[4\]** と判定される． - ビーバー $ s_0, s_1, \ldots, s_{K-1} $ を展示ゾーンに入れるとけんかが起きる場合，**不正解\[5\]** と判定される． - 回答は丁度 $ 1 $ 回行わなければならない． $ 2 $ 回以上回答した場合，**不正解\[6\]** と判定される． あなたのプログラムの終了時に回答が $ 1 $ 回も行われていなかった場合，**不正解\[7\]** と判定される． 上にあげたいずれでもない形式で標準出力に出力した場合，**不正解\[8\]** と判定される． #### 重要な注意 - 各出力の最後には，必ず標準出力を flush せよ．flush しない場合，実行時間制限超過と判定される可能性がある． - C++ のプログラムを提出する場合，`cout

N/A

N/A

### 採点に関する注意 実際の採点プログラムは適応的 (adaptive) ではなく，やりとりの初めから固定された答えを持つ． ### テストツール 作成したプログラムをテストするためのテストツール `testing_tool.py` が，コンテストサイトからダウンロードできるアーカイブの中に含まれている． このツールを必ずしも使う必要はなく，また変更することも許される． 実際の採点プログラムはテストツールとは異なることに注意すること． あなたが C++ で作成したプログラムをテストするには，以下のような手順に従えばよい． - あなたのプログラムをコンパイルして実行ファイルを生成せよ． 例えば，あなたのプログラムが `zoo.cpp` という名前の場合，以下のようなコマンドを実行すれば `zoo` という実行ファイルが生成される． ``` g++ -std=gnu++20 -O2 -o zoo zoo.cpp ``` - 次に，以下のコマンドを実行せよ． ``` python3 testing_tool.py ./zoo ``` あなたのプログラムが Python で実装されている場合，例えば，あなたのプログラムが `zoo.py` という名前なら，以下のコマンドを実行せよ． ``` python3 testing_tool.py python3 zoo.py ``` #### テストツールの入力 テストツールは標準入力から以下の形式で入力を読み込む． > $ N $ $ K $ $ L_0 $ $ R_0 $ $ L_1 $ $ R_1 $ $ \vdots $ $ L_{N-1} $ $ R_{N-1} $ #### テストツールの出力 プログラムの実行が正常に終了した場合，テストツールは標準出力へ以下の情報を出力する (引用符は実際には出力されない)． - 正解の場合，質問の回数が "`Accepted: 22`" のように出力される． - 不正解の場合，不正解の種類が"`Wrong Answer [2]`"のように出力される． 実行するプログラムが複数の不正解の条件を満たした場合，表示される不正解の種類はそれらのうち $ 1 $ つのみである． --- ### 小課題 1. ( $ 6 $ 点) $ N \leqq 8 $ ． 2. ( $ 7 $ 点) $ N \leqq 12 $ ． 3. ( $ 14 $ 点) $ N \leqq 20 $ ． 4. ( $ 21 $ 点) $ N \leqq 50 $ ． 5. ( $ 16 $ 点) $ N \leqq 90 $ ． 6. ( $ 36 $ 点) 追加の制約はない．この小課題では，以下に従い得点が決定される． - 小課題 $ 6 $ に対応するテストケースに対して， $ 1 $ つでも不正解があった場合，この小課題の得点は $ 0 $ 点となる． - そうでない場合，この小課題のすべてのテストケースにおける，質問の回数の最大値を $ T $ とする． このとき，小課題の得点は以下のように決定される． - $ 100 < T \leqq 1\,000 $ の場合， $ 13 $ 点． - $ T \leqq 100 $ の場合， $ 36 $ 点． 小課題 $ 1,2,3,4,5 $ の得点は質問の回数によらない ( $ 1\,000 $ 回以下であればよい) が， $ 100 $ 回より多い場合は コンテストサイトにおいて「出力は部分的に正しい」と表記されることがある． ### やりとりの例 テストツールが読み込む入力の例と，それに対応するやり取りの例を以下に示す． ### Sample Explanation 1  $ 1 $ 回目の質問では，ビーバー $ 0 $ とビーバー $ 2 $ のみから展示ゾーンに入れるビーバーを選ぶとき，最大で何匹のビーバーを展示ゾーンに入れることができるかを質問する． ビーバー $ 0 $ を選ぶと $ 1 $ 匹のビーバーを展示ゾーンに入れることができ，これが最大である．したがって， $ 1 $ が標準入力から与えられる． $ 2 $ 回目の質問では，ビーバー $ 1 $ のみから展示ゾーンに入れるビーバーを選ぶとき，最大で何匹のビーバーを展示ゾーンに入れることができるかを質問する． ビーバー $ 1 $ を選ぶと $ 1 $ 匹のビーバーを展示ゾーンに入れることができ，これが最大である．したがって， $ 1 $ が標準入力から与えられる． $ 3 $ 回目の質問では，ビーバー $ 1 $ とビーバー $ 2 $ とビーバー $ 3 $ のみから展示ゾーンに入れるビーバーを選ぶとき，最大で何匹のビーバーを展示ゾーンに入れることができるかを質問する． ビーバー $ 1 $ とビーバー $ 3 $ を選ぶと $ 2 $ 匹のビーバーを展示ゾーンに入れることができ，これが最大である．したがって， $ 2 $ が標準入力から与えられる． 最後に，ビーバー $ 1 $ とビーバー $ 3 $ を展示ゾーンに入れる $ 2 $ 匹として回答している． なお，このやりとりはあくまで一例であり，これらの質問から正しい回答を得るために必要な情報が得られているとは限らない． この入力例はすべての小課題の制約を満たす． ### Constraints すべての入力データは以下の条件を満たす． - $ 1 \leqq N \leqq 1\,000 $ ． - $ 1 \leqq K \leqq \min(10, N) $ ． - $ 1 \leqq L_i \leqq R_i \leqq 10\,000 $ ( $ 0 \leqq i \leqq N-1 $ )． - けんかが起きないように $ K $ 匹のビーバーを選ぶ方法が一つ以上存在する． - 入力される値はすべて整数である．