루미 알고리즘

#1576플래티넘The Dark Chambers of Chalmers

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

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

Problem

You are on your way to the final competition of the Swedish Olympiad in Informatics, which is hosted at Chalmers Technical University. However, you have gotten lost in the university basement. Your sense of direction is not great, and what makes matters worse is the very strange design of the basement.

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

Figure 1: The Dark Chambers of Chalmers...

The basement consists of 2 ≤ N ≤ 1000 floors. At the ground level, there is just one large room. For all other rooms, there is some room directly above. When you go down one floor, the rooms are half as big. Beneath every room i, there are up to two rooms l_i and r_i, each exactly half as big as room i. It is possible that only one of l_i and r_i exists, or that both or neither of them exist. You can move between two rooms through a door if they are directly next to each other, or through a staircase if one room is directly above the other. You are currently in some room in the basement, and you know that the final is also hosted somewhere in the basement.

A path is a sequence of steps to adjacent rooms. For some path v from the room you are currently in to the room where the final is hosted, let A_v be the number of times you go through a door, and B_v be the number of times you go up or down a staircase. The length of a path is defined as the sum L_v = A_v + B_v. You now want to get to the final competition. To aid you, you have downloaded the app Campus Maps. Campus Maps is programmed to find the length of the path to your destination, where the number of staircases you need to go up or down is minimized. Of all possible paths v to the room where the final is hosted the app will find all those that minimize the value of B_v. Out of these paths, it will choose the one that minimizes the value of L_v. It will then give you the value of L_v, the length of this path.

Since the app is quite slow, you only have time to check it at most 500 times. You also do not have time to go to another room more than 5000 times.

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

Figure 2: The basement in sample cases 1 and 2. The blue circle is your starting position, and the green circle shows which room the final is hosted in. In both images, the path that Campus Maps finds is illustrated in purple. In sample case 1, this path passes through three staircases and one door. In sample case 2, this path passes through zero staircases and six doors.

Interaction

First, you get information about the room you are currently in. This will be given as a binary string of length five, where every character is “1” if you can go in a certain direction, and “0” otherwise. In order, the characters tell you if you can go up, right, down to the right, down to the left, and left. So the string 01001 means that you can go to the right and to the left, but in no other directions.

Then, you choose either to go to an adjacent room, or to use Campus Maps. To go to an adjacent room you write any of the strings “up”, “right”, “downright”, “downleft” or “left”. Then you get information about the new room you are in, according to the same format as above.

To use the app you write “app”. The app will then calculate the length of the shortest path from where you are to the goal that uses as few staircases as possible. Since the app is very sensitive to Integer Overflows, it will crash if this length exceeds 10^9. In that case, the app will write -1. Otherwise, the length of the path to the goal is written.

When you reach your destination, you should print out “here”, and your program should be terminated.

Make sure to flush the output after each query, otherwise you can get Time Limit Exceeded. In C++ this can be done using 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
15N = 2
210N ≤ 10
310N ≤ 250
416Every room that is not on the lowest floor has two rooms directly below it.
513N ≤ 500
621N ≤ 950
725N ≤ 1000

출처 표기

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