시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 6789 | 3629 | 2056 | 51.749% |
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기, 블리자드 마법을 할 수 있다. 오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다.
격자에는 물고기 M마리가 있다. 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다. 이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다. 상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.
상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.
격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.
첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향은 8 이하의 자연수로 표현하고, 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 마지막 줄에는 sx, sy가 주어지며, 상어가 (sx, sy)에 있음을 의미한다.
격자 위에 있는 물고기의 수가 항상 1,000,000 이하인 입력만 주어진다.
S번의 연습을 마친 후 격자에 있는 물고기의 수를 출력한다.
5 1 4 3 5 1 3 5 2 4 2 2 1 6 3 4 4 4 2
9
격자의 초기 상태는 다음 그림과 같다. 상어가 있는 칸은 배경색이 어두운 칸, 물고기는 방향으로 표시했다.
물고기가 한 칸 이동하면 다음과 같다.
상어는 [상, 상, 상]으로 이동한다. 이때 (3, 2)에 있는 물고기가 격자에서 제외된다. 물고기의 냄새가 있는 칸은 배경의 색이 빨간색이다.
이제 복제 마법이 완료된다.
5 2 4 3 5 1 3 5 2 4 2 2 1 6 3 4 4 4 2
13
예제 1의 상태에서 연습을 한 번 더 해야 한다. 물고기가 한 칸 이동하면 다음 그림과 같다.
상어는 [우, 우, 하]로 이동한다. (2, 4)에도 상어의 냄새가 있으나 상어의 위치와 겹쳐 그림에는 표시하지 않았다.
아직 격자에서 사라질 냄새는 없다. 복제 마법이 완료되면 다음과 같다.
5 3 4 3 5 1 3 5 2 4 2 2 1 6 3 4 4 4 2
17
예제 2의 상태에서 연습을 한 번 더 해야 한다. 물고기가 한 칸 이동하면 다음과 같다.
상어는 [좌, 좌, 상]으로 이동한다. 여기서 9마리의 물고기가 격자에서 제외된다. 첫 번째 연습에서 생긴 냄새가 격자에서 사라진다. 상어가 있는 칸에는 어두운 배경 대신 상어를 표시했다.
복제 마법이 완료되면 격자의 상태는 아래 그림과 같아진다.
5 5 4 3 5 1 3 5 2 4 2 2 1 6 3 4 4 4 2
35
5 26 4 3 5 1 3 5 2 4 2 2 1 6 3 4 4 4 2
640240
1 10 1 1 1 4 4
26
8 100 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 1
8
10 25 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 2 1 1 2 1 1 2 1
574418
상어의 이동 방법 중 사전 순으로 가장 앞서는 방법을 찾으려면 먼저, 방향을 정수로 변환해야 한다. 상은 1, 좌는 2, 하는 3, 우는 4로 변환한다. 변환을 모두 마쳤으면, 수를 이어 붙여 정수로 하나 만든다. 두 방법 A와 B가 있고, 각각을 정수로 변환한 값을 a와 b라고 하자. a < b를 만족하면 A가 B보다 사전 순으로 앞선 것이다.
예를 들어, [상, 하, 좌]를 정수로 변환하면 132가 되고, [하, 우, 하]를 변환하면 343이 된다. 132 < 343이기 때문에, [상, 하, 좌]가 [하, 우, 하]보다 사전 순으로 앞선다.
총 43 = 64가지 방법을 사전 순으로 나열해보면 [상, 상, 상], [상, 상, 좌], [상, 상, 하], [상, 상, 우], [상, 좌, 상], [상, 좌, 좌], [상, 좌, 하], [상, 좌, 우], [상, 하, 상], ..., [우, 하, 하], [우, 하, 우], [우, 우, 상], [우, 우, 좌], [우, 우, 하], [우, 우, 우] 이다.