| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 47 | 13 | 8 | 25.806% |
Albert는 취미로 벌집과 꿀벌에 대해 연구한다. 잘 알려져 있듯 벌집의 각 칸은 6각형 모양으로 생겼는데, 편의상 Albert가 연구하는 벌집의 크기는 $R$행 $C$열의 6각형 격자 모양이라 하자. 아래 그림은 $R = 5,ドル $C = 8$인 경우를 나타낸다.
Albert는 이 벌집의 빈칸 중 일부에 초소형 장치를 설치하여 꿀벌들의 행동을 관찰하고 싶어 한다. 하나의 장치는 6각형 벌집 한 칸을 차지하며, 한 칸에는 최대 한 개의 장치만 넣을 수 있다. 다만, 장치가 너무 가까이 있으면 서로 간섭현상이 일어날 수 있어 주의해야 한다. 구체적으로, 어떤 칸에 초소형 장치를 설치하면 인접한 (최대) 여섯 칸의 다른 칸 중 같은 열에 위치한 (최대) 두 개의 칸과는 간섭현상이 발생하지 않지만 다른 열에 위치한 (최대) 네 개의 칸과는 간섭현상이 발생한다.
예를 들어 위 그림처럼 (1, 2), (2, 7), 그리고 (5, 6) 칸에 초소형 장치를 설치했다 하자.
다른 제약은 없고 간섭 현상만 피해서 장치를 최대한 많이 설치하려면 홀수 번째 열에만 (1열, 3열, ...) 장치를 설치하면 된다 -- 당연하게도 Albert는 이것이 최댓값이라는 것을 증명했다. 하지만 간섭 현상 이외에도 두 가지 고려할 문제가 있어서 Albert는 골치가 아프다.
예를 들어, 아래 좌측 그림은 $R = 3,ドル $C = 3,ドル $K = 4$ 이고 $X = [1, 3, 1, 3],ドル $Y = [1, 1, 2, 3]$인 격자판의 모습이다.
다른 예로, 아래 좌측 그림은 $R = 3,ドル $C = 4,ドル $K = 6$ 이고 $X = [2, 1, 3, 1, 3, 3],ドル $Y = [1, 2, 2, 3, 3, 4]$인 격자판의 모습이다.
입력으로 $R, C, K$ 그리고 고치들의 위치인 $X, Y$가 주어졌을 때, 위 조건들을 만족하며 초소형 장치를 최대 몇 개까지 설치할 수 있는지 구해보자.
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $R,ドル $C,ドル $K$가 공백으로 구분되어 주어진다. 만약 $K = 0$이라면 해당 테스트 케이스의 입력은 첫 줄로 끝난다. 만약 $K \gt 0$ 이라면 둘째 줄에는 $X$의 원소인 $K$개의 정수가 공백으로 구분되어 주어지고 셋째 줄에는 $Y$의 원소인 $K$개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
4 3 3 4 1 3 1 3 1 1 2 3 3 4 6 2 1 3 1 3 3 1 2 2 3 3 4 1 5 2 1 1 1 4 5 1 0
3 4 2 0
예제 1: 본문에서 다루었다.
예제 2: 본문에서 다루었다.
예제 3: 아래 그림처럼 다양한 방법으로 2개의 초소형 장치를 설치할 수 있다 (다른 방법도 존재한다).
예제 4: 신형 센서는 반드시 설치해야 하므로, 1열 어느 곳에 신형 센서를 설치해야 한다. 그 때문에 1열에 초소형 장치를 설치하지 못하므로 답은 0이다.