Going Home
InterviewTime limit2sMemory limit1024 MB
Given buttons that OR-combine with the current universe number, find at most 100 presses that turn universe A into B, or report -1 if impossible.
- Level
Medium4 of 10
- Topics
- Greedy, Bit manipulation
- Solved
- No attempts yet
Problem
After the collider exploded, Spider-Man Miles Morales ended up in a parallel universe. Realizing he needed help, he quickly found Peter Parker, the Spider-Man of this universe, and told him his story. After analyzing the collider blueprints Miles had accidentally taken with him and many other parameters, they found that Miles is in universe number and his own universe is number . After several months, they built a device for traveling between universes that can take Miles home. The device has buttons with numbers . Pressing the button moves you from the current universe to universe ( is bitwise OR). However, their resources were limited, so the device has enough charge for only moves. Miles and Peter are trying to work out the order in which to press the buttons to send Miles home. Help them!
Input
The first line contains three integers , , and : the number of buttons, the universe where Miles is now, and the universe where he needs to return (, ). The second line contains integers , the numbers written on the buttons ().
Output
If Miles cannot get home, print on a single line. Otherwise, print the number of button presses on the first line (), and on the second line print the button numbers separated by spaces, in the order they should be pressed. If there are several answers, print any of them.
Hint
In the first example, press button 1 first to move from universe 2 to universe . Then press button 4 to move from universe 3 to universe .