루미 알고리즘

#1583다이아KATT:s and Rats

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

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

Problem

A special type of mutated giant rats have taken over the sewers of Gothenburg, and the city management has asked for your help in solving the problem.

The sewer consists of N manholes numbered from 1 to N, with N-1 pipes connecting the manholes. Each pipe connects two manholes, and the sewer is designed so that it is possible to travel between each pair of manholes by going through a sequence of pipes. To reduce costs, all sewer developers in Gothenburg have been fired, leaving the sewer system completely undocumented. This means that there is no one left who knows between which pairs of manholes there are pipes.

There are a total of K mutated giant rats, located in different manholes. As the rats are extremely large and aggressive, there can never be two rats in the same manhole. You have already placed out K KATT:s (Kinetically Activated Tripping Trap) in different manholes. These can be activated with a single button press, and you now want to try to get the rats to go to the manholes with the KATT:s. But the rats are very intelligent, and if not all KATT:s are activated simultaneously, they will learn to use the KATT:s against you.

To get the rats to move, you have a large number of OWL:s (Omnidirectional Wave Launchers), which play songs and make noises that are especially irritating to this type of mutated giant rats. You can, in several rounds, choose a subset of the manholes, and place an OWL in each manhole in the subset. In every round, you will place some OWL:s, and some rats might go through a pipe in order to escape the annoying sounds. More specifically, each rat will get the opportunity to flee, and due to the laws of physics, the rats will do this in the order of the number of the manhole they are in right now. That is, if there are rats in manholes number 1 and 2, the rat in manhole 1 will try to flee first. When this rat has finished fleeing, the rat in manhole 2 will perform its escape. The rats want to maximize the distance to the nearest OWL. A rat will consider moving to all manholes, free from other rats, within one pipe's distance from where it is right now. If none of these manholes have a strictly larger distance to the nearest OWL, the rat will stay where it is now. Otherwise, it will move to the adjacent manhole with the greatest distance to the nearest OWL. If there are multiple such manholes, the rat will choose the manhole with the lowest number amongst them. The distance between two manholes is the minimum number of pipes you must go through to travel between them.

You have received a large number of OWL:s from the city of Gothenburg, but you can only make 25000 rounds of placements of OWL:s before the mating season of giant mutated rats begins (which would have disastrous consequences!).

Interaction

First, your program should read the numbers N (2 ≤ N ≤ 100) and K (1 ≤ K < N), which are written on a line. Then follows a line with K different numbers 1 ≤ r_1 < ... < r_K ≤ N, describing the numbers of the manholes where the rats are initially located. After that, a line with K different numbers 1 ≤ t_1 < ... < t_K ≤ N is given, describing the numbers of the manholes where there are KATT:s.

When you want to make a placement of OWL:s, you should first write out a number M, the number of OWL:s you are placing out. Then you should, on the same line, write out the numbers 1 ≤ s_1 < ... < s_M ≤ N, the manholes where you want to place OWL:s. OWL:s can be placed in a manhole regardless of whether there is a rat there or not. Then your program should read a line with K numbers, 1 ≤ r_1 < ... < r_K ≤ N, the manholes where there are rats after all rats have tried to flee from the sound.

When you have managed to get all rats to manholes with KATT:s, you should write out “activate!” on a line. Your program should then terminate.

Make sure to flush the output after each query, otherwise you may get a Time Limit Exceeded. In C++, this can be done for example with cout << flush; or fflush(stdout);, in Python with sys.stdout.flush() and in Java with System.out.flush();. The sewer is not necessarily randomly generated. However, it is guaranteed that rats start at and KATT:s are placed in manholes uniformly at random. The judge is not adaptive, which means it is predetermined what the sewer looks like.

To facilitate the testing of your solution, we provide a simple tool that you can download. See “attachments” at the bottom of the Kattis problem page. Refer to 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 case groups. To get points for a group, you must pass all the test cases in the group.

GroupPoint valueConstraints
15N = 2
25N ≤ 3
39N ≤ 10
420K = 1
515There is a pipe between manhole i and manhole i+1 for all 1 ≤ i < N.
621N ≤ 50
725No additional constraints.

Explanation of sample case 2

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

Figure 1: The layout of the sewer in sample 2. Note that your program will not know the layout of the pipes.

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

Figure 2: When you place OWL:s in manholes 4 and 5, the rats will be very disturbed. Firstly, the rat in manhole 4 will try to escape, since 4 < 5. This rat will go to manhole 3. After this, the rat in manhole 5 tries to escape, but has no available manhole to go to.

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

Figure 3: When you place a single OWL in manhole 5, first the rat in manhole 3 flees to manhole 2, and then the rat in manhole 5 flees to manhole 3.

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

Figure 4: When you once again place a single OWL in manhole 5, first the rat in manhole 2 flees to manhole 1, and then the rat in manhole 3 flees to manhole 2.

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

Figure 5: Now all rats are in manholes with KATT:s, and you can thus activate the KATT:s.

출처 표기

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