루미 알고리즘

#1562다이아Maple Tree

PO 2023 훈련 캠프코딩출제 David Wärn영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

As a cryptoarborist, you study secret trees. Today, you have been out in the forest and encountered an exciting specimen with N nodes and N-1 edges of varying lengths, all with positive lengths. Additionally, it is known that each node has at most 3 edges.

It is not easy to determine the structure of the tree – which nodes are connected to each other – but you have obtained a device that you believe can help you. The device compares distances in the tree. Let d(x, y) denote the sum of the edge lengths on the path between nodes x and y. With one use of the device, given three nodes A, B, C (where A ≠ B), you can compare whether d(A, C) is less than or greater than d(B, C).

Using the device at most 20,000 times, can you find which edges exist in the tree? You do not need to find the length of the edges.

Interaction

Your program should first read an integer N (3 ≤ N ≤ 1000), the number of nodes in the tree.

Then you can start performing measurements with your device, up to 20,000 times. For each measurement, you should print a line in the format ? A B C (1 ≤ A, B, C ≤ N, A ≠ B), and then read a line which will contain either the character A (if d(A, C) < d(B, C)) or B (if d(A, C) > d(B, C)). It is guaranteed that d(A, C) ≠ d(B, C) for all A ≠ B.

Finally, you should print a line with the character !, followed by N-1 lines, each containing the edges of the tree. Each line should contain two integers a, b (1 ≤ a, b ≤ N), the names of the nodes the edge connects.

It is guaranteed that the tree in each test case is predetermined and does not change adaptively in response to your measurements.

To simplify testing of your program, we provide a tool that you can download at the bottom of this page. See the comment at the top of the file for a description of how it can be used.

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
110N ≤ 30
215N ≤ 175
340N ≤ 350
410The tree is a line.
525No additional constraints.

Explanation of sample

In the example interaction, a maple tree with 5 nodes is studied. Using the measuring device, it is determined that the length of the path between node 1 and 3 is shorter than that between 2 and 3, and that the length of the path between 1 and 5 is longer than that between 4 and 5. Based on that information, the guess is made that the tree has the four edges (1, 3), (2, 3), (4, 3), and (4, 5). In reality, more measurements would need to be performed to determine the structure of the tree with certainty.

출처 표기

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