루미 알고리즘

#1517다이아Meeting Place

PO 2021 훈련 캠프코딩출제 Joakim Blikstad영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

N friends live on each vertex in a tree with N vertices, where N is an odd number. A tree is a connected graph with exactly N-1 edges.

The friends want to meet at one vertex in the tree. They have agreed that the best meeting place is the vertex that minimizes the sum of distances to the friends, and have asked you to help them find this optimal meeting place. The distance dist(a,b) between two vertices a and b in the tree is the number of edges on the path between a and b. So formally, the goal is to find the vertex x that minimizes ∑_{i=1}^n dist(x,i).

You think this is an easy problem, and start writing a solution right away. But there is a twist! The friends have bad memory and don't remember what the tree looks like. However, they do remember the following: given three different friends a,b,c, they can tell you the vertex where those three usually meet, which is the vertex x that minimizes dist(x,a) +dist(x,b) +dist(x,c). Note that x is not necessarily one of the vertices a, b or c.

In this problem you will not read the graph from the input, instead you can ask Q-1 questions on the form: Where do the friends a,b,c usually meet? Your task is to find the optimal meeting place by using these questions.

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

Figure 1: The tree in the sample. Vertex 2 is the optimal meeting place.

Interaction

The first line of input contains two integers N and Q, the number of vertices in the tree, and the number of queries you can make. It is guaranteed that N is odd and that Q = 500000 in all test cases.

Then you can make the following queries:

  • Output one line with “? a b c” where 1 ≤ a,b,c ≤ N are 3 different friends. After that, the judge will respond with one integer x that you should read from input (1 ≤ x ≤ N), the vertex that minimizes dist(x,a) +dist(x,b) +dist(x,c).
  • Output one line with “! x” where 1 ≤ x ≤ N is the optimal meeting place. After you have printed this query your program should terminate without outputting anything more. If x is the vertex that minimizes ∑_{i=1}^n dist(x,i) you will get Accepted on the test case, otherwise you will get Wrong Answer.

If you make more than Q queries (including the last on the form “! x”) your program will be terminated and you will get Wrong Answer.

Make sure to flush the output after each query, otherwise you may get Time Limit Exceeded. In C++ this can be done for example with 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 case groups. To get points for a group, you must pass all test cases in the group.

GroupPointsConstraints
1103 ≤ N ≤ 99 and all vertices have degree at most 2 (the tree is a line)
2123 ≤ N ≤ 999 and all vertices have degree at most 2 (the tree is a line)
3213 ≤ N ≤ 24999 and all vertices have degree at most 2 (the tree is a line)
4143 ≤ N ≤ 99
5153 ≤ N ≤ 999
6283 ≤ N ≤ 24999

출처 표기

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