Canadian Computing Olympiad: 2021 Day 1, Problem 3
There is a maze that is formed by connecting rooms via corridors. The rooms are numbered to and each room has the shape of a circle. The corridors have the following constraints:
- Each corridor forms a connection between two distinct rooms.
- Every pair of rooms is connected by exactly one path of connected corridors.
One difficulty in navigating through this maze is that the lights are all out, so you cannot see where you are. To help with navigation, each room contains a laser pointer that initially points to a corridor. Consider the following strategy:
- Rotate the room's laser pointer clockwise until it points to another corridor.
- Follow the room's laser pointer and traverse the corridor.
- Repeat the previous two steps indefinitely.
You created queries to investigate this strategy. For each query, you are given an integer and you start at room 1. Determine the final room after traversing exactly corridors. All laser pointers will reset to their original orientation after each query.
The first line contains the integers and .
The next lines describe the layout of the maze, with the th of these lines describing room . Specifically, it contains an integer , the number of corridors connecting to room , followed by integers, , indicating the rooms that these corridors lead to, in clockwise order. Lastly, room 's laser pointer initially points to the corridor leading to room .
The final lines describe a query, with each line containing an integer .
For 4 of the 25 available marks, the th corridor forms a connection between room and room .
For an additional 4 of the 25 available marks, and .
For an additional 12 of the 25 available marks, .
Output lines answering the queries in order.
5 6 1 2 3 3 1 4 1 2 2 5 2 1 4 1 2 3 4 5 6
2 1 2 4 2 3
Explanation for Sample Output
This is the initial state of the maze.
The strategy will visit these rooms in order: