Hide and Seek 4
Time limit2sMemory limit512 MB
Find the shortest time from N to K using moves -1, +1, and 2X, then output the lexicographically smallest shortest path.
- Level
Medium6 of 10
- Topics
- BFS, Graph, Shortest path
- Solved
- No attempts yet
Problem
Subin plays hide and seek with his younger sibling. Subin is at point and the sibling is at point . Subin can walk or teleport. If Subin is at and walks, one second later he is at or . If he teleports, one second later he is at . Subin's position is never negative. The sibling never moves.
Given both positions, find the shortest time in which Subin reaches his sibling, together with the positions he passes through.
Several routes can take that shortest time. In that case pick the one whose sequence of visited positions is smallest in lexicographic order. All shortest routes have the same length, so compare two sequences from the front: the one with the smaller number at the first position where they differ comes first.
Input
The first line contains Subin's position and the sibling's position , separated by a space. (, )
Output
On the first line, print the shortest time in seconds.
On the second line, print the positions Subin passes through in order, from to , separated by single spaces. If several routes take the shortest time, print only the sequence that is smallest in lexicographic order.