¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#10423

d1000000 5s 1024MB

Problemas

가장 흔한 주사위는 각 면에 서로 다른 정수 1부터 6까지가 적힌 6면체이지만, 다른 종류의 주사위를 사용하는 게임도 많다. 특히 dk는 k개의 면을 가진 주사위로, 각 면에는 서로 다른 정수 1부터 k까지가 적혀 있다. 따라서 d6는 일반적인 주사위이고, d4는 4면체이며, d1000000는 백만 면을 가진 주사위이다.

Dice from sample case 1

이 문제에서는 \mathbf{N}개의 주사위로 이루어진 컬렉션이 주어진다. i번째 주사위는 d\mathbf{S_i}, 즉 면이 \mathbf{S_i}개이고 각 면에 1부터 \mathbf{S_i}까지가 적혀 있다. 길이가 \ell이고 시작값이 x인 스트레이트(straight)란 정수 리스트 x, x + 1, \dots, x + (\ell - 1)을 뜻한다. 우리는 몇 개의 주사위(전부일 수도 있음)를 선택한 뒤, 각 주사위에서 숫자 하나씩을 골라 스트레이트를 만들고 싶다. 이렇게 해서 만들 수 있는 스트레이트의 최대 길이는 얼마인가?


Entrada

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 2줄로 설명된다. 첫 줄에는 정수 \mathbf{N}이 주어지며, 이는 게임에 있는 주사위의 개수이다. 둘째 줄에는 \mathbf{N}개의 정수 \mathbf{S_1}, \mathbf{S_2}, \dots, \mathbf{S_N}이 주어진다. 각 값은 서로 다른 주사위 하나의 면의 개수를 나타낸다.


Salida

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 입력으로 주어진 주사위들 중 스트레이트에 포함시킬 수 있는 주사위의 최대 개수(즉 만들 수 있는 최대 길이)이다.


Ejemplo 

4
4
6 10 12 8
6
5 4 5 4 4 4
10
10 10 7 6 7 4 4 5 7 4
1
10
Case #1: 4
Case #2: 5
Case #3: 9
Case #4: 1
샘플 케이스 #1에서는 4개의 주사위를 모두 사용해 스트레이트를 만드는 방법이 여러 가지이며, 그중 하나가 위 그림에 나와 있다. 샘플 케이스 #2에서는 어떤 주사위도 5보다 큰 수를 낼 수 없으므로 5개를 넘는 길이의 스트레이트는 만들 수 없다. 길이가 정확히 5인 스트레이트는 여러 가지 방법으로 만들 수 있다. 예를 들어 d5 두 개는 4와 5를 고르고, d4 세 개는 1, 2, 3을 골라 1,2,3,4,5를 만들 수 있다. 샘플 케이스 #3에서는 d4 하나를 버리고 d4, d5, d6로 1부터 4까지, d7로 5부터 7까지, d10로 8과 9를 만들어 1,2,3,4,5,6,7,8,9 스트레이트를 만들 수 있다. 길이 10의 스트레이트는 만들 수 없으므로 이것이 최선이다. 샘플 케이스 #4에서는 길이 1의 스트레이트만 만들 수 있지만, 주어진 d10에서 어떤 숫자를 고르든 길이 1 스트레이트를 만들 수 있다.

Fuente

GCJ 2022qr C

Debes iniciar sesión para escribir código.