| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 23 | 1 | 1 | 100.000% |
육각형 타일로 이루어진 칸들이 무한하게 놓여 있고, 재현이는 이 중 "시작 칸"이라고 부르는 칸 위에 서 있다. 두 칸은 모서리를 공유하면 이웃하고 있다고 하자. 재현이는 매번 다음 그림과 같이, 1부터 6까지 번호가 붙은 방향 을 따라서 이웃한 칸 중 하나로 이동할 수 있다.
재현이가 총 $N$번 움직였을 때 만드는 칸들로 이루어지는 경로는 영역을 형성한다. $i$번째 움직일 때는 $D[i]$ 방향으로 $L[i]$ 칸을 이동한다. 이 경로는 다음과 같은 특징이 있다.
다음은 재현이가 갈 수 있는 경로 중 하나의 예이다.
형성된 영역은 경로에 포함되거나, 내부에 있는 모든 칸들로 이루어진다. 영역 안의 칸 $c$의 거리는 영역 안의 칸들 만 방문해서 시작 칸부터 칸 $c$에 도착할 때까지 필요한 움직임의 최소값이다. 영역 안의 칸에 대한 점수는 $A + d \times B$인데, $A$와 $B$ 는 재현이가 미리 정한 상수값이며, $d$는 이 칸의 거리이다. 다음은 위 예제의 경로에 의 해 형성된 영역 안의 각 칸들의 거리를 보여준다.
재현이가 $N$번 움직일 때 만드는 칸들로 이루어진 경로에 의해 형성된 영역의 모든 칸의 점수의 총합을 구하는 프로그램을 작성하시오. 점수의 총합은 매우 큰 값일 수 있으므로, 이 값을 $10^9 + 7$으로 나눈 나머지를 구하시오.
다음 함수를 구현해야 한다.
int draw_territory(int N, int A, int B, int[] D, int[] L)
다음 호출을 생각해보자.
draw_territory(17, 2, 3,
[1, 2, 3, 4, 5, 4, 3, 2, 1, 6, 2, 3, 4, 5, 6, 6, 1],
[1, 2, 2, 1, 1, 1, 1, 2, 3, 2, 3, 1, 6, 3, 3, 2, 1])
이는 위 예제에서 설명한 것과 동일하다. 다음 표는 영역에서 가능한 거리마다 각 칸의 점수를 보여준다.
| 거리 | 칸 수 | 각 칸의 점수 | 총 점수 |
|---|---|---|---|
| $0$ | $1$ | $2 + 0 \times 3 = 2$ | $1 \times 2 = 2$ |
| $1$ | $4$ | $2 + 1 \times 3 = 5$ | $4 \times 5 = 20$ |
| $2$ | $5$ | $2 + 2 \times 3 = 8$ | $5 \times 8 = 40$ |
| $3$ | $6$ | $2 + 3 \times 3 = 11$ | $6 \times 11 = 66$ |
| $4$ | $4$ | $2 + 4 \times 3 = 14$ | $4 \times 14 = 56$ |
| $5$ | $3$ | $2 + 5 \times 3 = 17$ | $3 \times 17 = 51$ |
| $6$ | $4$ | $2 + 6 \times 3 = 20$ | $4 \times 20 = 80$ |
| $7$ | $4$ | $2 + 7 \times 3 = 23$ | $4 \times 23 = 92$ |
| $8$ | $5$ | $2 + 8 \times 3 = 26$ | $5 \times 26 = 130$ |
| $9$ | $3$ | $2 + 9 \times 3 = 29$ | $3 \times 29 = 87$ |
| $10$ | $4$ | $2 + 10 \times 3 = 32$ | $4 \times 32 = 128$ |
| $11$ | $5$ | $2 + 11 \times 3 = 35$ | $5 \times 35 = 175$ |
| $12$ | $2$ | $2 + 12 \times 3 = 38$ | $2 \times 38 = 76$ |
점수의 총합은 $2 + 20 + 40 + 66 + 56 + 51 + 80 + 92 + 130 + 87 + 128 + 175 + 76 = 1003$이다. 따라서, draw_territory 함수의 리턴값은 $1003$이어야 한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $N = 3$, $B = 0$ |
| 2 | 6 | $N = 3$ |
| 3 | 11 | $L$의 모든 원소의 합은 2000을 넘지 않는다. |
| 4 | 12 | $B = 0$이고 $L$의 모든 원소의 합은 200 000을 넘지 않는다. |
| 5 | 15 | $B = 0$ |
| 6 | 19 | $L$의 모든 원소의 합은 200 000을 넘지 않는다. |
| 7 | 18 | $L[i] = L[i + 1]$ (모든 $0 \le i \le N - 2$) |
| 8 | 16 | 추가적인 제약 조건이 없다. |
샘플 그레이더는 다음 양식으로 입력을 읽는다.
샘플 그레이더는 다음 양식으로 답을 출력한다.
draw_territory의 리턴값C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)