Pick Your Own Nim
Time limit2sMemory limit512 MB
Bob picks one heap from each of his boxes so that he wins for every nonempty subset Alice can choose from her heaps, or the task reports that he cannot.
- Level
Hard8 of 10
- Topics
- Bit manipulation, Math, Implementation
- Solved
- No attempts yet
Statement
Alice and Bob love playing Nim. If the heaps are , the first player wins if and only if is nonzero. Some online games let players pick their characters before the match, so they made a new version. Each of them has several boxes of heaps. In the first phase, each player picks exactly one heap from each of their boxes. In the second phase, Alice chooses a nonempty subset of the heaps she picked, and regular Nim starts on the chosen heaps with Bob to move first. Bob already knows which heaps Alice picked. Help him choose his heaps so that he wins no matter which subset Alice chooses.
Input
The first line contains the number of heaps picked by Alice (). If , the next line contains the heap sizes. If , that line is omitted. The next line contains the number of Bob's boxes (). Each of the next lines describes one box. It starts with (), the number of heaps in the box, followed by the heap sizes. Each heap size is between and , inclusive. The total number of heaps in Bob's boxes is at most 5000.
Output
If Bob cannot win, meaning that no matter which heaps he picks, Alice can choose a subset that leaves the resulting Nim position losing, print . Otherwise, print integers: the sizes of the heaps Bob should pick from his boxes, in the same order as the boxes are given in the input.
Hint
In Nim, several heaps of stones are on the table. On each turn, a player selects any heap and takes a positive number of stones from it. The player who takes the last stone wins.