시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB41720017550.872%

문제

QuentoQ42에서 만든 게임이다. 이 게임의 게임판은 항상 3×3 크기이며, 오른쪽 그림과 같이 검정색 칸에는 숫자, 흰색 칸에는 +또는 -가 적혀져 있다.

게임판의 상단에는 만들어야하는 숫자 N과 사용해야 하는 숫자의 개수 M이 주어진다. 이제 숫자에서 스와이프를 시작해 +/-로 이동한 다음, 다시 숫자로 스와이프를 하고, 이런식으로 숫자를 M개 지났을 때, 결과가 N이 되어야 한다. 이미 방문한 칸은 재방문 할 수 없으며, 다시 지나가는 것도 불가능하다.

예를 들어, 7을 숫자 2개를 이용해서 만들려면, 4+3, 9-2는 가능하다. 하지만, 5+3-1은 숫자 3개를 이용했기 때문에 불가능하다.

N과 M, 그리고 게임판에 쓰여 있는 숫자와 +/-가 주어진다. 이때, 숫자 M개를 이용해서 N을 만드는 방법을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 45, 2 ≤ M ≤ 5) 둘째 줄부터 3개의 줄에 걸쳐 게임판에 써잇는 숫자와 +/-가 주어진다. 숫자는 항상 한자리 숫자이고, 0이 아니다.

출력

M개의 숫자를 이용해서 N을 만들 수 있으면, 첫째 줄에 1을 출력하고, 없는 경우에는 0을 출력한다. 그 다음, 숫자를 만들 수 있는 경우에는 방문한 칸을 총 2*M-1개 줄에 걸쳐서 출력한다. 가장 왼쪽 윗칸의 좌표는 (0, 0), 왼쪽 아랫칸의 좌표는 (2, 0), 오른쪽 윗칸의 좌표는 (0, 2), 오른쪽 아랫칸의 좌표는 (2, 2)이다.

가능한 방법이 여러 가지인 경우 아무거나 하나만 출력한다.

예제 입력 1

11 2
6+5
-3-
8+4

예제 출력 1

1
0 0
0 1
0 2

예제 입력 2

1 3
6+5
-3-
8+4

예제 출력 2

1
2 2
2 1
1 1
1 0
0 0

예제 입력 3

15 3
6+5
-3-
8+4

예제 출력 3

0

힌트

이 게임은 다운받아서 직접해 볼 수 있다.

http://quento.com/

출처