Problem B
KATT:s and rats
Languages
en
sv
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
There are a total of
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
You have received a large number of OWL:s from the city of
Gothenburg, but you can only make
Interaction
First, your program should read the numbers
When you want to make a placement of OWL:s, you should first
write out a number
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 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.
Group |
Point value |
Constraints |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
There is a pipe between manhole |
|
|
|
|
|
No additional constraints. |
Explanation of sample case 2
![\includegraphics[scale=0.2]{rats_graph before.png}](/problems/rats2/file/statement/en/img-0001.png)
![\includegraphics[scale=0.2]{rats_graph step1.png}](/problems/rats2/file/statement/en/img-0002.png)
![\includegraphics[scale=0.2]{rats_graph step2.png}](/problems/rats2/file/statement/en/img-0003.png)
![\includegraphics[scale=0.2]{rats_graph step3.png}](/problems/rats2/file/statement/en/img-0004.png)
![\includegraphics[scale=0.2]{rats_graph step4 activate.png}](/problems/rats2/file/statement/en/img-0005.png)
Read | Sample Interaction 1 | Write |
---|
3 1 1 3
1 1
2
1 1
3
activate!
Read | Sample Interaction 2 | Write |
---|
5 2 4 5 1 2
2 4 5
3 5
1 5
2 3
1 5
1 2
activate!