## COCI '22 Contest 2 #5 Kruhologija

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

You're an ant, and not just a regular ant, you're an ant obsessed with kruhology! While most other ants are busy watching the Cup, you're currently on a slice of bread magically floating in the air...

The slice of bread can be imagined as a collection of unit cubes whose upper faces are all in the same plane. Let the total number of faces of the slice of bread be . All unit cubes are connected. In other words, by moving along the faces of the cubes, one can go from any face to any other face. For any two cubes sharing just one edge, there is another cube which shares a face with both of those cubes.

On the left is the first example.
On the right is a forbidden configuration.

Currently, you are on some face of some cube and oriented in an unknown way. You don't know anything about the global structure of the slice. You conveniently carry around a marker you stole from high school with which you can leave a tiny mark on each face. You can erase the mark as well! You can repeat any of the following operations times:

• K - make a step in your current direction
• L - rotate to the left
• D - rotate to the right
• X - if the current face has no mark, make one, else remove it

Notice that you can be directed to the edge of the slice and still make a step forwards. In that case, you will end up on a lateral face of a cube. If you make another step, you will end up on the other side of the slice of bread! Because of this, in each moment, you can do any of the four operations.

Example of moving over an edge.

A hole on a slice of bread is defined as a part of space fully surrounded by cubes. The drawn figure has exactly one hole in the middle. Notice that a hole can contain more than one connected "empty" cube and can be of any shape.

You like holes, so you are really interested in the number of holes in the slice of bread you are on! Try and find out!

#### Interaction

This is an interactive task. Your task is to make a solution which will calculate the number of holes in a slice of bread. In every moment, you can do one of the four given operations. The grader will output either the number 0 or 1 after you make a step forward. The number 1 means that the face you have just stepped on is already marked, and 0 means the face is unmarked. After outputting an operation and before inputting the grader's response, you should flush the output.

If you do more than operations, your solution will be considered incorrect. After at most operations you should output the answer in the following format ! g where should be the number of holes in the slice of bread.

#### Constraints

, , there is at most one hole in the slice
,

Please note that the data may not necessarily be the same as the original contest.

#### Sample Interaction 1

>>> denotes your output. Do not print this out.

>>> X
>>> K
0
>>> L
>>> L
>>> K
1
>>> X
>>> D
>>> D
>>> K
0
>>> ! 1

#### Explanation for Sample Interaction 1

In the first example, you are somewhere on the slice of bread drawn in the statement. The slice has exactly one hole, and the correct answer is .

#### Sample Interaction 2

>>> denotes your output. Do not print this out.

>>> X
>>> K
0
>>> K
0
>>> K
0
>>> K
1
>>> ! 0

#### Explanation for Sample Interaction 2

In the second example, you are located on a single-unit cube. It has no holes, and therefore the answer is .