d1000000 Solution Qualification Round 2022 - Code Jam 2022
Problem
While the most typical type of dice have sides, each of which shows a different integer through , there are many games that use other types. In particular, a is a die with sides, each of which shows a different integer through . A is a typical die, a has four sides, and a has one million sides.
In this problem, we start with a collection of dice. The -th die is a , that is, it has sides showing integers through . A straight of length starting at is the list of integers . 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, . test cases follow. Each test case is described in two lines. The first line of a test case contains a single integer , the number of dice in the game. The second line contains integers , each representing the number of sides of a different die.
Output
For each test case, output one line containing Case #:
, where is the test case number (starting from 1) and is the maximum number of input dice that can be put in a straight.
Limits
Memory limit: 1 GB.
.
Test Set 1 (Visible Verdict)
Time limit: 5 seconds.
.
, for all .
Test Set 2 (Visible Verdict)
Time limit: 15 seconds.
.
, for all .
Sample
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
In Sample Case #1, there are multiple ways to form a straight using all 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 , there is no way to have a straight with more than dice. There are multiple ways to form a straight with exactly dice. For example, pick the integers and for both 's and then integers and for three of the 's to form .
In Sample Case #3, it is possible to form the straight by discarding one and using the 's, , and to get through ; the 's to get through ; and the 's to get and . There is no way to form a straight of length , so this is the best that can be done.
In Sample Case #4, we can only form a straight of length , but we can do so by picking any integer for the we are given.
Join Now for Solution:-
No comments:
Post a Comment