영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Alma has a lot of planks that she wants to saw into pieces. Therefore, she has gone to a state-of-the-art sawmill that automatically cuts and sorts the planks. Each plank can be represented by an infinitely long x-axis, and the sawmill will cut the plank at the N+1 positions
x_1, x_2, …, x_N, v
where v is a number chosen by the user. Then, all finitely long pieces are sorted and output by the sawmill. Alma wants to know the numbers x_1, x_2, …, x_N, but it seems that no one knows what the inside of the sawmill looks like. So instead, she plans to figure out the numbers by feeding in some planks with well-chosen values of v.
There are N secret integers x_1 < x_2 < … < x_N between 1 and 10^9. Note that all these numbers are different. Your goal is to find these numbers. You can send planks to the sawmill. The sawmill takes an integer v as input (1 ≤ v ≤ 10^9), and does the following:
- Create the list L = [x_1, x_2, …, x_N, v].
- Sort L.
- Create the list D, where D_i = L_{i+1}-L_i for all i = 1, 2, …, N.
- Sort D, and return the N integers in D.
You may send at most N planks, except for subtask 4, where you can send N+1 planks.
Interaction
Your program should first read two integers N and T (1 ≤ N ≤ 1000, 1 ≤ T ≤ 5). N is the number of secret numbers you need to find, and T is the test group number. The reason T is given as input is to make it easier to earn partial points.
Then, you can start sending planks. Print a line with “? v” to send a plank with the number v to the sawmill. The number v must satisfy 1 ≤ v ≤ 10^9. Then, your program should read N integers on one line, the numbers D_1, D_2, …, D_N. Note that D_1 can be zero if v was equal to one of the numbers x_i.
When you have found the numbers x_1, x_2, …, x_N, you should print a line in the form
! x_1 x_2 x_3 … x_N
Then, your program should terminate and not print anything more.
Make sure to flush the output after each query, otherwise, you may get Time Limit Exceeded. In C++, this can be done with, for example, cout << flush or fflush(stdout); in Python with stdout.flush(); and in Java with System.out.flush().
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 15 | N = 1 |
| 2 | 15 | N = 2 |
| 3 | 11 | x_i ≤ N+1 |
| 4 | 37 | N ≤ 100, x_i ≤ 10^4, you may send at most N+1 planks. |
| 5 | 22 | No additional constraints. |