루미 알고리즘

#1605골드Quack

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

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

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Harry loves his small yellow ducks from Kodsport and has recently acquired a large collection.

But unfortunately, some of them have disappeared! The ducks are hiding in tall grass along a line, and the grass is so high that Harry cannot see where they are located.

There are N ducks hiding at integer positions within the range [0, 10^9], where each position can contain at most one duck. The problem is that Harry doesn't know how many ducks have disappeared.

However, Harry is able to perform the following action up to Q times:

• Quack from a position: Harry can stand at an integer position on the line [-10^9, 2 · 10^9] and begin quacking.

  • The duck closest to Harry will then quack back, allowing Harry to determine the position of that particular duck.
  • If there are multiple ducks with the same distance to Harry, the duck with the lower position will quack back first. This implies that Harry can only determine the position of the duck with lower position.
  • Note that the ducks do not move or disappear after Harry finds them; they stay at their positions until all ducks have been identified.

Your task is to help Harry find all the ducks by determining the number of ducks hiding and providing the exact positions of these ducks.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: The secret placement of the hidden ducks in example case 2.

Interaction

This is an interactive problem where you can place Harry at an integer position within the range [-10^9, 2 · 10^9] up to Q times. Note that both N and Q are secret numbers.

Your program starts by reading an integer T (1 ≤ T ≤ 6), where T is the number of the test group. The reason for providing T in the input is to make it easier to receive partial points.

After that, you can start placing Harry at any integer position x_h within the range [-10^9, 2 · 10^9]. You make the query by printing

? x_h

Your program will then read an integer x_a, which is the position of the closest duck.

If your program does not exit, you may receive incorrect assessments like Run-Time Error.

You can place Harry up to Q times. But once you have found all N duck positions x_1 x_2 x_3 … x_N, you should print two lines. First, a line with an exclamation mark and the number N, the number of hidden ducks:

! N

Then, print a new line with N integers, the positions of the N ducks in any order:

x_1 x_2 x_3 … x_N

After that, your program should terminate, and no further output should be printed.

It is guaranteed that the number of lost ducks N and their positions in each test case are predetermined and do not change adaptively in response to your outputs.

Make sure to flush the output after every print statement, otherwise you may get Time Limit Exceeded. In C++, this can be done for example with cout << flush; or fflush(stdout);, in Python this is done automatically when you use input(), but otherwise you need to use sys.stdout.flush(), and in Java with System.out.flush();.

Note also that if your program prints an invalid number or incorrect answer, it will be marked as Wrong Answer, unless something else happens before it affects your assessment.

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
15N = 2, Q = 3
216Ducks are located at s, s+1, s+2, …, s+N-1 for some integer 0 ≤ s ≤ 10^9, 2 ≤ N ≤ 2 · 10^4, Q = 2N-1.
3142 ≤ N ≤ 100, Q = N^2+ N
4192 ≤ N ≤ 100, Q = 33N
5272 ≤ N ≤ 10^3, Q = 2N-1
6192 ≤ N ≤ 2 · 10^4, Q = 2N-1

Explanation of Sample 2

According to the interaction, the program first places Harry at position 1 and quacks. The program then receives information that the nearest duck to position 1 is at position 0.

(그림은 원문 저장소에서 볼 수 있습니다)

Then the program places Harry at position 4 and quacks. The program learns that the nearest duck to position 4 is a duck at position 4.

(그림은 원문 저장소에서 볼 수 있습니다)

Next, the program places Harry at position 9 and quacks. The program receives information that the nearest duck to position 9 is at position 10.

(그림은 원문 저장소에서 볼 수 있습니다)

Then the program tries placing Harry at position 2 and quacks. Note that there are two different ducks at the same distance from Harry in this case. However, the program will only know about the duck with the lower coordinate-position, in this case, the duck at position 0.

(그림은 원문 저장소에서 볼 수 있습니다)

Finally, the program assumes that all ducks are found and prints the answer.

출처 표기

출처: Programmeringsolympiaden 2025년 결선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.