No.3347 Guess The Array
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : / 解いたユーザー数 25
作問者 :
ponjuice
/ テスター :
tassei903
Nzt3
jupiter_68
noya2
りすりす/TwoSquirrels
タグ : / 解いたユーザー数 25
作問者 :
noya2
問題文最終更新日: 2025-11-13 16:24:28
コンテストの他の問題:
問題文
この問題はインタラクティブな問題です。
最初にあなたは整数 $N$ が与えられます。ジャッジは長さ $N$ の数列 $A$ を隠し持っています。
あなたはジャッジに対して、以下の質問を繰り返し行うことができます。
- 好きな長さの数列 $B$ を一つ作成し、ジャッジに対して $B$ を送る。ただし、$1\le |B| \le N$ かつ、$B$ の全ての要素は $1$ 以上 $N$ 以下の整数でなければならない。
- ジャッジは $B$ が $A$ の(連続とは限らない)部分列であるかどうかを判定し、その結果をあなたに教える。
$5000$ 回以下の質問で数列 $A$ を特定してください。
なお、数列 $A$ は対話の開始前に決定されており、あなたの質問によって変化することはありません。
制約
- $N$ は整数
- $1 \leq N \leq 500$
- 数列 $A$ の各要素は $1$ 以上 $N$ 以下の整数
入出力
この問題はインタラクティブな問題(あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題)です。
最初に数列の長さ $N$ が与えられます。
$N$
その後、あなたのプログラムは以下の形式で質問を行うことができます。ただし、$k=|B|$ です。
$?$ $k$ $B_1$ $B_2$ $\cdots$ $B_k$
質問を送ると、ジャッジからの返答が以下の形式で与えられます。
$S$
ここで、$S$ は Yes または No であり、
- $S$ が
Yesのときは $B$ が $A$ の(連続とは限らない)部分列であることを表します。 - $S$ が
Noのときは $B$ が $A$ の(連続とは限らない)部分列でないことを表します。
答えを出力する場合、以下の形式で出力してください。出力した後、プログラムを終了してください。
$!$ $A_1$ $A_2$ $\cdots$ $A_N$
注意点
- 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。
- 質問の形式が間違っている場合、および、質問回数を超過した場合のジャッジの応答は不定です。
- 余計な改行は不正なフォーマットの出力とみなされることに注意してください。
- 解答をする出力は質問回数に含まれません。
サンプル
| プログラム側の出力 | ジャッジ側の出力 | 説明 |
|---|---|---|
5 | まず初めに $N$ が渡されます。ジャッジは $A=(1,2,3,4,5)$ を隠し持っています。 | |
? 3 1 2 4 | 質問として $B = (1, 2, 4)$ をジャッジに送りました。 | |
Yes | $B$ は $A$ の部分列として含まれるので Yes が渡されます。 | |
? 3 3 2 1 | 質問として $B = (3, 2, 1)$ をジャッジに送りました。 | |
No | $B$ は $A$ の部分列として含まれないので No が渡されます。 | |
! 1 2 3 4 5 | 答えとして $(1,2,3,4,5)$ を出力しました。これは $A$ と一致するので正解となります。 |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。