TopCoder problem "CompilingDecksWithJokers" used in SRM 380 (Division I Level Two , Division II Level Three)



Problem Statement

    

You are given a int[] cards, the i-th element of which is the number of cards you have of type i, and an int jokers, the number of jokers you have. You want to construct decks using these cards. There are two types of valid decks:

  1. A deck containing exactly 1 card of each type, and no jokers.
  2. A deck containing exactly 1 card of each type except one, and exactly 1 joker.
For example, if there are 3 types of cards, the following four decks would be valid: {1, 2, 3}, {J, 2, 3}, {1, J, 3}, {1, 2, J}. Return the maximum possible number of valid decks you can construct with the given cards. Each card can only be a member of a single deck.

 

Definition

    
Class:CompilingDecksWithJokers
Method:maxCompleteDecks
Parameters:int[], int
Returns:int
Method signature:int maxCompleteDecks(int[] cards, int jokers)
(be sure your method is public)
    
 

Notes

-The total number of types of cards is equal to the total number of elements in cards.
 

Constraints

-cards will contain between 1 and 50 elements, inclusive.
-Each element of cards will be between 0 and 500,000,000, inclusive.
-jokers will be between 0 and 500,000,000, inclusive.
 

Examples

0)
    
{10, 15}
3
Returns: 13
10 full decks without jokers and 3 decks with jokers instead of cards of the first type can be compiled.
1)
    
{1, 2, 3}
4
Returns: 3
Three decks with one joker each can be compiled: one with the card of the second type changed to joker and two with the card of the first type replaced by joker.
2)
    
{1}
5
Returns: 6
Note that a deck can be composed of 1 sole joker if there is only 1 type of card.
3)
    
{2, 3, 4, 5, 6}
4
Returns: 4

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8228

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10802&pm=8228

Writer:

gevak

Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Problem categories:

Greedy, Search