페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10386

공평한 간식 10s 1024MB

문제

아로하(Aroha)는 동물을 무척 좋아해서, 여가 시간에 사랑하는 사람들의 반려동물들을 돌보곤 한다. 아로하는 간식을 주는 것을 좋아하지만, 편파 없이 공정하게 주고 싶다.

아로하는 같은 크기의 동물은 같은 양의 간식을 받아야 하고, 더 큰 동물은 더 작은 동물보다 반드시 더 많은 간식을 받아야 한다고 생각했다. 예를 들어 크기가 10, 20, 10, 25인 반려동물 4마리가 있다면, 크기 10인 각 동물에게 간식을 2개씩, 크기 20인 동물에게 3개, 크기 25인 동물에게 5개를 줄 수 있다. 이 경우 총 2+3+2+5=12개의 간식을 사야 한다. 하지만 아로하는 규칙을 지키면서도, 크기 10인 동물들에게 각각 1개, 크기 20인 동물에게 2개, 크기 25인 동물에게 3개를 주면 총 7개만으로도 4마리 모두에게 간식을 줄 수 있다.

아로하가 다음 "반려동물의 날"을 계획할 수 있도록 도와주자. 함께할 모든 반려동물의 크기가 주어질 때, 모든 반려동물에게 최소 한 개 이상의 간식을 주면서 아로하의 공정성 규칙을 만족하기 위해 아로하가 사야 하는 간식의 최소 개수를 구하라.


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 2줄로 이루어진다. 첫 줄에는 정수 \mathbf{N}이 주어지며, 이는 아로하의 다음 반려동물의 날에 함께할 반려동물의 수이다. 둘째 줄에는 \mathbf{N}개의 정수 \mathbf{S_1}, \mathbf{S_2}, \dots, \mathbf{S_N}이 주어지며, 각 반려동물의 크기를 나타낸다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 모든 반려동물에게 최소 한 개 이상의 간식을 주면서 아로하의 공정성 규칙을 만족하기 위해 필요한 간식의 최소 개수이다.


예제 

3
4
10 20 10 25
5
7 7 7 7 7
2
100 1
Case #1: 7
Case #2: 5
Case #3: 3
샘플 케이스 #1은 위에서 설명한 경우이다. 샘플 케이스 #2에서는 모든 반려동물의 크기가 같으므로 Aroha는 모두에게 같은 수의 간식을 주어야 한다. 각 반려동물에게 간식 1개씩 주는 것이 총합의 최소가 된다. 샘플 케이스 #3에서는 두 반려동물의 크기가 서로 다르므로 서로 다른 수의 간식을 받아야 한다. 간식을 2개보다 적게 사면 둘 다에게 줄 수 없다. 간식을 2개 사고 둘 다에게 주려면 서로 같은 양을 줘야 하는데, 이는 크기가 다른 요구에 맞지 않는다. 간식을 3개 사면 작은 동물에게 1개, 큰 동물에게 2개를 주어 모든 규칙을 만족할 수 있다.

출처

GCJ 2021iow A

로그인해야 코드를 작성할 수 있어요.