루미 알고리즘

#1650플래티넘Secret Walk

PO 2026 온라인 예선코딩출제 Harry Zhang영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

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

cc by-sa

In the exotic and warm city of Mänhettan live Harry and his absent-minded friend Tobias. The city is an N × N grid with coordinates (x,y) where 0 ≤ x,y < N. There is a house on every cell where both x and y are odd. The top-left cell is (0,0), the bottom-left cell is (N-1,0), and the bottom-right cell is (N-1,N-1).

Tobias lives in one of these houses, and his school is in another. They are not on the same row or column, because Harry has visited Tobias and could not see the school through the window.

Tobias may move between two cells that share a side; each such move takes exactly one minute. Every day he walks along a shortest path to school and sends messages like “On my way now!” and “Just arrived!”, which means Harry knows exactly how long it takes Tobias to go from his house to the school.

Although Harry has visited Tobias and knows whether a cell is a house, he has forgotten both where Tobias lives and where the school is located.

To figure this out, each day Harry may magically create walls on any cells that do not contain houses. That day it takes t minutes for Tobias to travel from his house to the school, or t=-1 if he gets completely stuck. After the day ends, all walls Harry created disappear.

Your task is to help Harry determine which house Tobias lives in and which house the school is in, using as few days as possible. Harry may use up to 365 days, but you get more points the fewer days you use.

Interaction

This is an interactive problem.

• Your program must first read one line containing an integer N (5 ≤ N ≤ 75, N is odd), the height and width of the grid. Then it reads N lines, each with N characters describing the grid. The character H means that cell is occupied by a house, while . means it is empty.

• Then your program interacts with the grader. To learn the number of minutes t Tobias needs when taking a shortest path, you can issue a query by placing walls. Do this by printing a line containing a question mark ?. On the following N lines print an N × N grid that is a copy of the input grid with any subset of empty cells . replaced by # (walls).

Then read an integer t (-1 ≤ t ≤ N^2), the minimum number of minutes Tobias needs to travel from his house to the school if he may pass through houses (H) and empty cells (.), but not walls (#).

• When you want to output your final answer, print a line starting with an exclamation mark ! followed by four integers x_1 y_1 x_2 y_2 where (x_1,y_1) and (x_2,y_2) are the coordinates of Tobias's house and the school in any order. The format must be ! x1 y1 x2 y2. For your answer to be accepted, either Tobias's house is (x_1,y_1) and the school is (x_2,y_2), or vice versa.

After this your program should terminate.

The grader is non-adaptive: the positions of Tobias's house and the school are fixed before interaction starts.

Make sure to flush your output after every query, otherwise you may get Time Limit Exceeded. In Python this happens automatically as long as you use input() to read lines. In C++ cout << endl; flushes, but you can also use cout << flush; or fflush(stdout);, and in Java System.out.flush();.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
15N = 5
29N ≤ 9
311Tobias's house is cell (1,1) (the top-left house).
4up to 75No additional constraints.

In the last test group your score depends on the number of days used according to:

score = 75, if Q ≤ 5, 63, if 5 < Q ≤ 6, 55 · (10/55)^((Q-10)/85), if 6 < Q ≤ 10, 53 · (8/53)^((Q-10)/64), if 10 < Q ≤ 75, 4 · (1/4)^((Q-160)/205), if 75 < Q ≤ 365, 0, if Q > 365.

Here Q is the maximum number of days used on any test case. The score is rounded to the nearest integer.

To get full points in this group, Harry must solve every test case in at most 5 days.

Below is a table of scores for selected Q values:

QPoints
575
663
1055
1151
3029
758
1604
3002
3651
3660

Further down the page there is a file points.txt containing the score for every possible Q. There is also a testing_tool.py you can use to test your solution locally.

출처 표기

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