카트라이더 보드게임

카트라이더 보드게임을 처음 접한 다오는 기존 보드게임의 규칙이 너무 복잡하여, 게임을 단순하게 만들어서 연습하고 있다. 게임 내에 있는 모든 장치를 제거하고, 루찌 정보만을 남겨두었다.

편의상 각 칸에는 $1$부터 $64$까지 번호를 매겼다. 아래 그림을 참고하자. 일부 칸에는 갈림길 혹은 지름길이 있어서, 원하는 방향으로 진행할 수 있다. 즉, $12$번, $32$번, $39$번, $49$번 칸에서 화살표 방향으로 이어진 칸 중 하나를 선택하여 이동할 수 있다. 연결된 길에 대한 자세한 정보는 아래 노트에서 텍스트로 제공된다.

다오는 $1$번 칸에서 시작하여, 주사위를 정확히 $N$ 번 굴리려고 한다. 주사위를 한 번 굴려 나올 수 있는 수는 $1$부터 $6$까지의 정수이다. 다오는 주사위를 굴려 항상 자신이 원하는 수가 나오도록 할 수 있다.

디지니는 다오에게 주사위를 정확히 $N$ 번 굴려 $X$번 칸에 도착하면서, 동시에 루찌를 최대한 많이 얻도록 부탁했다.

맵에서 루찌를 얻을 수 있는 칸의 정보는 다음과 같다:

• 루찌 1개를 얻을 수 있는 칸의 번호: 8, 17, 20, 31, 37, 39, 44, 49, 60, 63
• 루찌 2개를 얻을 수 있는 칸의 번호: 2, 6, 10, 19, 23, 25, 27, 43
• 루찌 3개를 얻을 수 있는 칸의 번호: 13, 33, 41, 52, 53, 54
• 루찌 5개를 얻을 수 있는 칸의 번호: 55, 64

정수 $N$과 $X$가 주어질 때, $1$번 칸에서 시작하여 주사위를 정확히 $N$ 번 굴려 $X$번 칸에 도착하는 동안 얻을 수 있는 루찌의 최대 개수를 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 주사위를 굴리는 횟수를 나타내는 정수 $N$과 도착해야 하는 칸의 번호를 나타내는 정수 $X$가 공백으로 구분되어 주어진다. ($4 \le N \le 1\,000;$ $1 \le X \le 64$)

출력 형식

첫 줄에 주사위를 정확히 $N$ 번 굴려 $X$번 칸에 도착하는 동안 얻을 수 있는 루찌의 최대 개수를 출력한다.

이어지는 $N$ 개의 줄 각각에는 주사위를 던져서 움직인 정보를 출력한다. 구체적으로, Moved from A to B (dice = C, lucci = D)와 같이 출력한다. 이는 A번 칸에서 주사위를 던져 C가 나왔고, B번 칸으로 움직인 뒤, 루찌 D개를 얻었다는 것을 의미한다.

예제

5 19

11
Moved from 1 to 2 (dice = 1, lucci = 2)
Moved from 2 to 6 (dice = 4, lucci = 2)
Moved from 6 to 10 (dice = 4, lucci = 2)
Moved from 10 to 13 (dice = 3, lucci = 3)
Moved from 13 to 19 (dice = 6, lucci = 2)

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

이 문제의 총점은 모든 미션의 점수의 합으로 계산된다. 각 미션의 점수를 계산하는 방법은 다음과 같다.

• $S$ : 미션의 만점
• $P$ : 미션에 대한 참가자의 점수
• $\alpha$ : 각 미션에서 만점을 받을 수 있는 루찌 획득량
• $L$ : 참가자의 출력에 따른 루찌 획득량

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 불가능한 움직임이 있는 등) $P = 0$이다.

1. $L \le \alpha-S$ 인 경우: $P = 0$
2. $\alpha-S < L < \alpha$ 인 경우: $P = S - (\alpha - L)$
3. $L \ge \alpha$ 인 경우: $P = S$

각 미션의 정보는 다음과 같다.

각 미션마다 만점을 받을 수 있는 출력이 존재함이 보장된다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

노트

만약, $a$번 칸에서 $b$번 칸으로 주사위 숫자 $1$에 이동할 수 있으면, a → b 형식으로 주어진다.

1 → 2
2 → 3
3 → 4
4 → 5
5 → 6
6 → 7
7 → 8
8 → 9
9 → 10
10 → 11
11 → 12
12 → 13
12 → 17
13 → 14
14 → 15
15 → 16
16 → 17
17 → 18
18 → 19
19 → 20
20 → 21
21 → 22
22 → 23
23 → 24
24 → 25
25 → 26
26 → 27
27 → 28
28 → 29
29 → 30
30 → 31
31 → 32
32 → 33
32 → 37
33 → 34
34 → 35
35 → 36
36 → 37
37 → 38
38 → 39
39 → 40
39 → 41
40 → 44
41 → 42
42 → 43
43 → 40
44 → 45
45 → 46
46 → 47
47 → 48
48 → 49
49 → 50
49 → 52
49 → 56
50 → 51
51 → 60
52 → 53
53 → 54
54 → 55
55 → 51
56 → 57
57 → 58
58 → 59
59 → 51
60 → 61
61 → 62
62 → 63
63 → 64
64 → 1

해설