A16139. Michael and Hotel
编程题
普及/提高-
知识点
题目描述
Michael and Brian are stuck in a hotel with $n$ rooms, numbered from $1$ to $n$ , and need to find each other. But this hotel's doors are all locked and the only way of getting around is by using the teleporters in each room. Room $i$ has a teleporter that will take you to room $a_i$ (it might be that $a_i = i$ ). But they don't know the values of $a_1,a_2, \dots, a_n$ .
Instead, they can call up the front desk to ask queries. In one query, they give a room $u$ , a positive integer $k$ , and a set of rooms $S$ . The hotel concierge answers whether a person starting in room $u$ , and using the teleporters $k$ times, ends up in a room in $S$ .
Brian is in room $1$ . Michael wants to know the set $A$ of rooms so that if he starts in one of those rooms they can use the teleporters to meet up. He can ask at most $2000$ queries.
The values $a_1, a_2, \dots, a_n$ are fixed before the start of the interaction and do not depend on your queries. In other words, the interactor is not adaptive.
Instead, they can call up the front desk to ask queries. In one query, they give a room $u$ , a positive integer $k$ , and a set of rooms $S$ . The hotel concierge answers whether a person starting in room $u$ , and using the teleporters $k$ times, ends up in a room in $S$ .
Brian is in room $1$ . Michael wants to know the set $A$ of rooms so that if he starts in one of those rooms they can use the teleporters to meet up. He can ask at most $2000$ queries.
The values $a_1, a_2, \dots, a_n$ are fixed before the start of the interaction and do not depend on your queries. In other words, the interactor is not adaptive.
输入格式
The input contains a single integer $n$ ( $2 \leq n \leq 500$ ).
输出格式
To ask a query, print a line in the format "? u k |S| S\_1 S\_2 ... S\_|S|" with $1 \leq u, S_1, \ldots, S_{|S|} \leq n$ , all the $S_i$ distinct, and $1 \leq k \leq 10^9$ .
As a response to the query you will get "1" if the answer is yes, and "0" if the answer is no.
To output an answer, you should print "! |A| A\_1 A\_2 ... A\_|A|" with $1 \leq A_1, \ldots, A_{|A|} \leq n$ all distinct. Printing the answer doesn't count as a query.
See the interaction example for more clarity.
If you ask too many queries or you ask a malformed query, you will get Wrong answer.
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Hack format
For the hacks use the following format.
The first line should contain $n$ — the number of rooms.
The second line should contains $n$ integers $a_1, a_2, \dots, a_n$ — the teleporter in room $i$ leads to room $a_i$ .
As a response to the query you will get "1" if the answer is yes, and "0" if the answer is no.
To output an answer, you should print "! |A| A\_1 A\_2 ... A\_|A|" with $1 \leq A_1, \ldots, A_{|A|} \leq n$ all distinct. Printing the answer doesn't count as a query.
See the interaction example for more clarity.
If you ask too many queries or you ask a malformed query, you will get Wrong answer.
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Hack format
For the hacks use the following format.
The first line should contain $n$ — the number of rooms.
The second line should contains $n$ integers $a_1, a_2, \dots, a_n$ — the teleporter in room $i$ leads to room $a_i$ .
输入输出样例
输入 #1
5 0 1
输出 #1
? 3 5 2 2 3 ? 2 5 2 2 3 ! 3 1 3 4
说明/提示
In the sample test, there are $n=5$ rooms and the (hidden) array describing the behavior of the teleporters is $[1, 2, 1, 3, 2]$ .
- The first query asks whether starting from room number $a=3$ , and using the teleporters $5$ times, one ends up in one of the two rooms $S=\{2, 3\}$ . This action results in ending up in the room $1$ , so the answer is $0$ .
- The second query asks whether starting from room number $a=2$ , and using the teleporters $5$ times, one ends up in one of the two rooms $S=\{2, 3\}$ . This action results in ending up in the room $2$ , so the answer is $1$ .
- The first query asks whether starting from room number $a=3$ , and using the teleporters $5$ times, one ends up in one of the two rooms $S=\{2, 3\}$ . This action results in ending up in the room $1$ , so the answer is $0$ .
- The second query asks whether starting from room number $a=2$ , and using the teleporters $5$ times, one ends up in one of the two rooms $S=\{2, 3\}$ . This action results in ending up in the room $2$ , so the answer is $1$ .