Forced Choice
InterviewTime limit1sMemory limit1024 MB
Given a fixed sequence of card subsets chosen by the princess, decide for each step whether Puff must keep or remove those cards so that a named prediction card survives to the end.
- Level
Medium4 of 10
- Topics
- Implementation, Greedy, Simulation, Array
- Solved
- No attempts yet
Problem
Puff the Magic Dinosaur is a famous magician. Because of the pandemic, he can only perform for his princess using modern video conferencing tools. As a result, he cannot perform many of his usual in-person routines, and he has to come up with a new trick.
Puff has decided to perform the following mentalist trick for the princess. First, Puff lays out cards on the table. Each of these cards has a unique label . Before the show starts, Puff writes down a prediction, which is the label of one of the cards, puts it into a sealed envelope, and mails it to the princess.
During the show, Puff asks the princess to choose some of the remaining cards. Puff takes care to remind the princess to choose at least one but not all of the remaining cards. After the princess tells Puff which cards she chose, Puff says either "you chose to keep those cards" or "you chose to remove those cards". In the first case, the chosen cards are kept and all other cards are removed from the table. In the second case, the chosen cards are removed and the remaining cards are kept. This repeats until only one card is left. At that point Puff asks the princess to open the envelope, and the prediction matches the card left on the table.
Determine what response Puff should give at each step.
Input
The first line of input contains three integers (), the number of cards, (), the secret prediction, and (), the number of steps.
The next lines describe the choices of the princess at each step. Each of these lines starts with the integer (), the number of cards chosen, followed by distinct integers indicating the labels of the cards chosen. It is guaranteed that if Puff has carried out the previous steps correctly, the princess will only choose cards still on the table. Furthermore, the princess will always choose at least one but not all of the remaining cards.
It is guaranteed that there will be one card left after steps if Puff has carried out all steps correctly.
Output
For each step, display on a line either KEEP or REMOVE if Puff should keep the chosen cards or remove the chosen cards, respectively.