d1000000 Solution Qualification Round 2022 - Code Jam 2022

d1000000 Solution Qualification Round 2022 - Code Jam 2022

Problem

While the most typical type of dice have 6$6$ sides, each of which shows a different integer 1$1$ through 6$6$, there are many games that use other types. In particular, a dk$dk$ is a die with k$k$ sides, each of which shows a different integer 1$1$ through k$k$. A d6$d6$ is a typical die, a d4$d4$ has four sides, and a d1000000$d1000000$ has one million sides.

In this problem, we start with a collection of N$N$ dice. The i$i$-th die is a dSi$d{\mathbf{S}}_{\mathbf{i}}$, that is, it has Si${\mathbf{S}}_{\mathbf{i}}$ sides showing integers 1$1$ through Si${\mathbf{S}}_{\mathbf{i}}$. A straight of length ℓ$\ell$ starting at x$x$ is the list of integers x,x+1,…,x+(ℓ−1)$x,x+1,\dots ,x+(\ell -1)$. We want to choose some of the dice (possibly all) and pick one number from each to form a straight. What is the longest straight we can form in this way?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow. Each test case is described in two lines. The first line of a test case contains a single integer N$N$, the number of dice in the game. The second line contains N$N$ integers S1,S2,…,SN${\mathbf{S}}_{\mathbf{1}},{\mathbf{S}}_{\mathbf{2}},\dots ,{\mathbf{S}}_{\mathbf{N}}$, each representing the number of sides of a different die.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the maximum number of input dice that can be put in a straight.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.

Test Set 1 (Visible Verdict)

Time limit: 5 seconds.
1≤N≤10$1\le \mathbf{N}\le 10$.
4≤Si≤20$4\le {\mathbf{S}}_{\mathbf{i}}\le 20$, for all i$i$.

Test Set 2 (Visible Verdict)

Time limit: 15 seconds.
1≤N≤105$1\le \mathbf{N}\le {10}^5$.
4≤Si≤106$4\le {\mathbf{S}}_{\mathbf{i}}\le {10}^6$, for all i$i$.

Sample

Sample Input

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

Sample Output

Case #1: 4
Case #2: 5
Case #3: 9
Case #4: 1

In Sample Case #1, there are multiple ways to form a straight using all 4$4$ dice. One possible way is shown in the image above.

In Sample Case #2, since none of the dice can show an integer greater than 5$5$, there is no way to have a straight with more than 5$5$ dice. There are multiple ways to form a straight with exactly 5$5$ dice. For example, pick the integers 4$4$ and 5$5$ for both d5$d5$⁠'s and then integers 1,2,$1,2,$ and 3$3$ for three of the d4$d4$⁠'s to form 1,2,3,4,5$1,2,3,4,5$.

In Sample Case #3, it is possible to form the straight 1,2,3,4,5,6,7,8,9$1,2,3,4,5,6,7,8,9$ by discarding one d4$d4$ and using the d4$d4$⁠'s, d5$d5$, and d6$d6$ to get 1$1$ through 4$4$; the d7$d7$⁠'s to get 5$5$ through 7$7$; and the d10$d10$⁠'s to get 8$8$ and 9$9$. There is no way to form a straight of length 10$10$, so this is the best that can be done.

In Sample Case #4, we can only form a straight of length 1$1$, but we can do so by picking any integer for the d10$d10$ we are given.

Join Now for Solution:- 

 3D Printing Solution Qualification Round 2022 - Code Jam 2022