숨바꼭질 4

이동 -1, +1, 2X를 써서 N에서 K까지 가는 최단 시간을 구하고, 사전순으로 가장 작은 최단 경로를 출력합니다.

보통6BFS그래프최단 경로아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

수빈이는 동생과 숨바꼭질을 한다. 수빈이는 점 NN에, 동생은 점 KK에 있다. 수빈이는 걷거나 순간이동을 한다. 수빈이의 위치가 XX일 때 걸으면 1초 뒤에 X1X-1 또는 X+1X+1로 이동하고, 순간이동하면 1초 뒤에 2X2X로 이동한다. 수빈이의 위치는 항상 0 이상이다. 동생은 움직이지 않는다.

두 사람의 위치가 주어질 때, 수빈이가 동생을 찾는 가장 빠른 시간과 그동안 지나간 위치를 구한다.

가장 빠른 시간이 걸리는 이동 방법이 여러 가지일 수 있다. 이때는 지나간 위치를 순서대로 늘어놓은 수열이 사전순으로 가장 앞서는 방법 하나를 고른다. 가장 빠른 방법은 모두 길이가 같으므로, 두 수열을 앞에서부터 비교해 처음으로 달라지는 자리의 수가 더 작은 쪽이 사전순으로 앞선다.

입력

첫째 줄에 수빈이의 위치 NN과 동생의 위치 KK가 공백으로 구분되어 주어진다. (0N1000000 \le N \le 100000, 0K1000000 \le K \le 100000)

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 초 단위로 출력한다.

둘째 줄에 수빈이가 지나간 위치를 NN부터 KK까지 순서대로 공백으로 구분해 출력한다. 조건을 만족하는 방법이 여러 가지면 사전순으로 가장 앞서는 수열 하나만 출력한다.