시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB220736835.417%

문제

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

  • 정지(초당 $0$미터)
  • 초당 $1$미터
  • 초당 $4$미터
  • 초당 $8$미터

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

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

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

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

입력

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

출력

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

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

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

예제 입력 1

10 3

예제 출력 1

2
0 8
1 1

예제 입력 2

10 2

예제 출력 2

-1

예제 입력 3

20 50

예제 출력 3

1
45 4

예제 입력 4

20 3

예제 출력 4

2
0 8
2 4

출처

University > 중앙대학교 > 2022 중앙대학교 프로그래밍 경진대회(CPC) > Division 2 G번