푸앙이와 러닝머신

면접 대비

시간 제한1초메모리 제한1024 MB

요약

정수 초에 속력을 0, 1, 4, 8m/s 중 하나로 바꿀 수 있을 때, 정확히 T초 동안 X미터를 달리기 위한 최소 버튼 조작 횟수와 그 시각을 구한다.

문제

푸앙이는 러닝머신을 즐겨 탄다. 러닝머신에는 다음과 같은 속력을 조작할 수 있는 네 가지 버튼이 있다.

초당 $D$ 미터로 속력을 조작할 수 있는 버튼은 $D$ 라고 부른다.

푸앙이는 효과적인 운동을 위해 거리 $X$ 미터를 정확히 시간 $T$ 초에 완주하는 목표를 세웠다. 그런데 푸앙이는 버튼을 조작하는 것이 귀찮아 최소한의 횟수로 버튼을 누르려고 한다.

푸앙이를 도와 언제, 무슨 버튼을 눌러야 하는지 알려주는 프로그램을 작성하자.

운동 시각은 $0$ 초부터이며, $0$ 초일 때 러닝머신은 정지해있다. 버튼은 정수 초에만 누를 수 있고, $1$ 초에 최대 한 번만 누를 수 있다.

첫 번째 줄에 정수 $X$ 와 $T$ 가 공백으로 구분되어 주어진다. $(1 \le X, T \le 10^9)$

주어진 시간동안 정확히 목표 거리를 이동하는 것이 가능하다면, 첫 번째 줄에 버튼을 눌러야 하는 최소 횟수 $N$ 을 출력하고, 다음 $N$ 개의 줄에 걸쳐 버튼을 누르는 시각과 버튼의 종류를 공백으로 구분하여 시간 순서대로 출력한다.

가능한 방법이 여러가지라면 그 중 하나를 출력한다.

만약 주어진 시간동안 정확히 목표 거리를 이동하는 것이 불가능하다면 $-1$ 을 출력한다.