루미 알고리즘

#1558플래티넘The Sawmill

PO 2023 결선코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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:

  1. Create the list L = [x_1, x_2, …, x_N, v].
  2. Sort L.
  3. Create the list D, where D_i = L_{i+1}-L_i for all i = 1, 2, …, N.
  4. 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.

GroupPointsConstraints
115N = 1
215N = 2
311x_i ≤ N+1
437N ≤ 100, x_i ≤ 10^4, you may send at most N+1 planks.
522No additional constraints.

출처 표기

출처: Programmeringsolympiaden 2023년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.