| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 87 | 34 | 31 | 50.820% |
시간이 흐르며, 사람들은 어느 순간부터 소용돌이 문양에 관심을 가졌다. 빛의 흐름에서, 돌 무늬에서, 구조물의 바닥에서, 그들은 소용돌이 문양을 찾아냈다.
처음에는 작은 징후처럼 보였지만, 곧 소용돌이는 섬 곳곳에 나타나기 시작했다.
남겨진 소용돌이의 흔적을 따라가고, 그들이 마주한 형상을 복원하여라.
광장의 바닥에는 $N\times M$ 크기의 격자가 새겨져 있다. 이때 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$로 표기한다.
최근 이 격자 위에서 총 $K$개의 소용돌이 문양이 관측되었다.
소용돌이 문양은 특정 위치를 중심으로 하여 다양한 반지름을 가진다. 아래 그림은 반지름이 각각 0ドル,ドル 2ドル,ドル 4ドル$인 소용돌이 문양의 예시이다.
(격자선은 이해를 돕기 위해 그려졌으며, 색칠된 칸이 실제 소용돌이 문양을 나타낸다.)
격자의 각 칸이 몇 개의 소용돌이 문양에 포함되었는지 알아내보자.
첫 줄에 격자의 크기를 나타내는 두 정수 $N,ドル $M$과 소용돌이 문양의 개수 $K$가 주어진다.
둘째 줄에는 정수 $p,ドル $q$가 주어진다.
이후 $K$개의 줄에 걸쳐, 각 줄에는 각각 세 정수 $r_i,ドル $c_i,ドル $d_i$가 주어진다. 이는 $i$번째로 관측된 소용돌이 문양이 칸 $(r_i,c_i)$를 중심으로 한 반지름이 $d_i$인 소용돌이 문양임을 의미한다.
1ドル\le r\le N,1\le c\le M$인 모든 $(r,c)$에 대해, $A_{rc}$를 칸 $(r,c)$가 포함되는 소용돌이 문양의 수라고 정의하자. $A_{rc}$의 모든 값을 출력하려면 많은 시간이 소요되므로, 다음 값을 대신 출력한다.
\[\sum_{r=1}^N\sum_{c=1}^M\left( (r\times p)\oplus(c\times q)\oplus A_{rc} \right)\]
단, $\oplus$는 이진 XOR 연산을 의미한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 2 | $d_i = 0$ $(1 \le i \le K)$ |
| 2 | 7 | $K = 1$ |
| 3 | 4 | $p = q = 0$ |
| 4 | 6 | $N \le 100, M \le 100, K \le 100$ |
| 5 | 27 | $K \le 2000$ |
| 6 | 16 | 2ドルd_i + 1 = M$ $(1 \le i \le K)$ |
| 7 | 38 | 추가 제한 조건이 없다. |
11 9 3 1 2 5 6 2 7 5 4 1 1 0
1063
37 28 1 79 1101 14 11 8
16529317
소용돌이 문양의 엄밀한 정의는 다음과 같다.
반지름이 0ドル$인 소용돌이 문양은 1ドル\times 1$ 크기의 격자 한 칸으로 정의된다.
2ドル$ 이상의 모든 짝수 $d$에 대해, 반지름이 $d$인 소용돌이 문양은 다음과 같은 방식으로 만들 수 있다.
위와 같은 방식으로 $d=4$인 소용돌이 문양을 만들면 아래와 같다.
Contest > BOJ User Contest > BCF > BCF 2025 VI번