D. Michael and Hotel
binary search; interactive; trees
Michael and Brian are stuck in a hotel with \(n\) rooms, numbered from \(1\) to \(n\), and need to find each other. But this hotel's doors are all locked and the only way of getting around is by using the teleporters in each room. Room \(i\) has a teleporter that will take you to room \(a_i\) (it might be that \(a_i = i\)). But they don't know the values of \(a_1,a_2, \dots, a_n\).Instead, they can call up the front desk to ask queries. In one query, they give a room \(u\), a positive integer \(k\), and a set of rooms \(S\). The hotel concierge answers whether a person starting in room \(u\), and using the teleporters \(k\) times, ends up in a room in \(S\).Brian is in room \(1\). Michael wants to know the set \(A\) of rooms so that if he starts in one of those rooms they can use the teleporters to meet up. He can ask at most \(2000\) queries.The values \(a_1, a_2, \dots, a_n\) are fixed before the start of the interaction and do not depend on your queries. In other words, the interactor is not adaptive.
The input contains a single integer \(n\) (\(2 \leq n \leq 500\)).
In the sample test, there are \(n=5\) rooms and the (hidden) array describing the behavior of the teleporters is \([1, 2, 1, 3, 2]\). The first query asks whether starting from room number \(a=3\), and using the teleporters \(5\) times, one ends up in one of the two rooms \(S=\{2, 3\}\). This action results in ending up in the room \(1\), so the answer is \(0\). The second query asks whether starting from room number \(a=2\), and using the teleporters \(5\) times, one ends up in one of the two rooms \(S=\{2, 3\}\). This action results in ending up in the room \(2\), so the answer is \(1\).