카트라이더 보드게임

NYPC 2023 · Round 1 연습문제

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

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

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

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

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

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

입력 형식

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

출력 형식

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

이어지는 NN 개의 줄 각각에는 주사위를 던져서 움직인 정보를 출력한다. 구체적으로, 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)

채점 방식

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

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

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

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

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

#NNXXSSα\alpha
11441313202099
2277343420201313
331010414120202222
442020434320204949
553939494920209797
66838313132020222222
7715715755552020420420
8821021018182020561561
995165166464202013881\,388
101010001\,0001919202026892\,689

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

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

미션 1
미션 2
미션 3
미션 4
미션 5
미션 6
미션 7
미션 8
미션 9
미션 10

노트

만약, aa번 칸에서 bb번 칸으로 주사위 숫자 11에 이동할 수 있으면, 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

해설