창고

면접 대비

시간 제한1초메모리 제한128 MB

요약

트럭 화물 요청 순서와 B개의 베이가 주어질 때, 어떤 베이에 어떤 화물 종류를 둘지 정해 화물 적재 횟수를 최소화하는 문제다. 요청 순서를 미리 아는 상황에서 최적해를 구한다. 총 적재 횟수를 출력한다. 한 번도 안 쓴 종류는 세지 않는다. 정확히는 하루 동안 베이에 화물을 올리는 LOAD 동작의 최소 횟수다. 요청 시퀀스 길이는 N이다. 최적 오프라인 전략이 필요하다. 각 종류는 베이 하나에만 동시에 존재할 수 있다. 베이 수 B가 주어진다. 종류 수 G가 주어진다. 남은 화물은 마지막에 세지 않는다. 최소 LOAD 횟수를 구하라. 그리고 Case 번호를 붙여 출력하라. 이것이 문제의 전부다. 베이 수가 충분하면 모든 종류를 유지할 수 있다. 부족하면 쫓아내야 한다. 가장 늦게 다시 쓰일 종류를 쫓아내는 것이 최적이다. 이 규칙이 정답을 준다.이 문제는 다음과 같이 요약된다. 요청 순서와 베이 수가 주어지고, 어떤 베이에 어떤 화물을 둘지 결정한다. 화물 적재 횟수를 최소화한다. 요청 순서를 미리 안다. 베이 수 B가 한정된다. 종류 G가 주어진다. N개의 요청이 순서대로 들어온다. 매 순간 베이에는 한 종류만 둘 수 있다. 요청이 오면 그 종류가 어느}

난이도: 보통10점 중 5점
유형: 그리디, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

Advanced Cargo Movement, Ltd.는 다양한 종류의 물품을 보관하는 큰 창고를 운영한다. 이 창고에는 화물을 실을 수 있는 적재구역(bay)이 제한된 개수만큼 있다. 매일 트럭들이 적재구역으로 와서 화물을 싣고(각 트럭은 정확히 한 종류의 물품만 싣는다) 상점으로 떠난다. 적재를 빠르게 하기 위해 창고 관리인은 미리 물품을 적재구역으로 옮겨 둔다. 실제로 실릴 화물의 양을 미리 정확히 알 수 없으므로, 관리인은 필요한 양보다 많은 물품을 준비하고 남은 물품은 나중에 창고로 되돌린다. 따라서 어떤 적재구역에 다음으로 오는 트럭이 이전 트럭과 같은 종류의 물품을 싣는다면, 불필요하게 화물을 옮기지 않아도 되어 유리하다. 트럭의 적재 용량은 적재구역의 용량보다 훨씬 작으므로, 같은 종류의 물품을 원하는 트럭이라면 몇 대가 오더라도 하나의 적재구역에서 다시 채우지 않고 처리할 수 있다.

여러분의 임무는 어떤 종류의 물품을 어떤 적재구역에 준비할지를 정하여, 관리인이 물품을 창고로 되돌리는 횟수를 최대한 적게 만드는 것이다. 매일 시작 시점에는 어떤 적재구역에도 물품이 준비되어 있지 않다. 하루가 끝났을 때 적재구역에 남아 있는 물품은 이동 횟수에 포함하지 않는다.

입력

입력의 첫 줄에는 풀어야 할 테스트 케이스의 수가 주어진다.

각 테스트 케이스는 공백 하나로 구분된 세 정수 $B$ , $G$ , $N$ ( $1 \le B \le 1000$ , $1 \le G \le 1000000$ , $1 \le N \le 1000000$ )이 있는 줄로 시작한다. $B$ 는 창고의 적재구역 수, $G$ 는 보관되는 물품 종류의 수, $N$ 은 창고로 오는 트럭의 수이다. 이어서 $N$ 개의 줄이 주어지며, $i$ 번째 줄에는 $i$ 번째 트럭이 싣고자 하는 물품의 종류 $t_i$ ( $1 \le t_i \le G$ )가 도착 순서대로 주어진다.

출력

어떤 트럭이 도착했을 때 그 트럭이 원하는 종류의 물품이 어떤 적재구역에도 준비되어 있지 않다면, 트럭을 처리하기 전에 그 종류의 물품을 어떤 적재구역으로 옮겨야 한다. 이 작업을 LOAD 동작 한 번으로 세며, 이때 그 적재구역에 원래 있던 물품은 창고로 되돌려진다. 원하는 종류가 이미 어떤 적재구역에 준비되어 있다면 아무 작업도 필요 없다. 트럭은 도착 순서대로 한 번에 한 대씩 처리한다.

각 테스트 케이스마다 다음 형식의 한 줄을 출력한다.

Case X: M

여기서 X는 테스트 케이스 번호(1부터 시작)이고, M은 해당 테스트 케이스의 모든 트럭을 처리하는 데 필요한 LOAD 동작의 최소 횟수이다.

예제6

예제 1

입력

예상 출력

Case 1: 3
Case 2: 3

예제 2
입력
```
1
1 1 5
1
1
1
1
1
```
예상 출력
```
Case 1: 1
```
예제 3
입력
```
1
1 2 6
1
2
1
2
1
2
```
예상 출력
```
Case 1: 6
```
예제 4
입력
```
1
5 5 5
1
2
3
4
5
```
예상 출력
```
Case 1: 5
```
예제 5
입력
```
1
2 3 6
1
2
3
1
2
3
```
예상 출력
```
Case 1: 4
```

예제 6

입력

예상 출력

Case 1: 1
Case 2: 2
Case 3: 2