D - NPCA Network
Editorial
/
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
この問題はインタラクティブな問題です。
KoD 君は N 頂点の単純無向グラフを持っており、頂点には 1 から N の番号が付けられています。このグラフは連結とは限りません。
あなたの目標は、KoD 君が持っているグラフに閉路が存在するかどうか判定することです。そのために、以下の質問を行うことができます。
- 頂点集合を指定し、両端がその集合に属するような辺が何本あるかを聞く。
4500 回以下の質問回数で判定してください。
制約
- 2 \leq N \leq 250
- N は整数
- KoD 君が持っているグラフには自己ループや多重辺が存在しない。
入出力
最初に、グラフの頂点数 N を標準入力から受け取ってください。
N
次に、グラフに閉路が存在するかどうか判定できるまで質問を繰り返してください。質問は、以下の形式で標準出力に出力してください。
? n a_1 \ldots a_n
これは、頂点集合として \{ a_1, \dots, a_n \} を指定することを表します。このとき、n > 0 でなければならず、a_1, \dots, a_n は相異なる 1 以上 N 以下の整数でなければなりません。
質問に対する応答は、次の形式で標準入力から与えられます。
M
- 無効な質問を行った場合(質問回数が 4500 回を超えた場合を含む)、M = -1 です。この場合、プログラムをただちに終了させてください。
- 有効な質問を行った場合、M は指定した頂点集合に両端が含まれるような辺の本数を表します。
グラフに閉路が存在するかどうか判定できたら、解答を以下の形式で標準出力に出力してください。
! S
S はあなたの解答を表す文字列であり、閉路が存在するなら Yes
、存在しないなら No
でなければなりません。
注意
- 出力のたびに改行し、標準出力をflushしてください。そうしない場合、ジャッジ結果が TLE となる可能性があります。
- 解答を出力した後、あなたのプログラムは直ちに終了しなければなりません。そうしない場合、ジャッジ結果が AC とならない可能性があります。
- 途中で不正な出力を行った場合は不正解となりますが、そのときのジャッジ結果は不定です。WA になるとは限りません。
入出力例
入力 | 出力 |
---|---|
3 |
|
? 2 1 2 |
|
1 |
|
? 3 1 3 2 |
|
3 |
|
! Yes |