Connection Status:
Competition Arena > CompilingDecksWithJokers

CompilingDecksWithJokers

SRM 380 · 2007-12-04 · by gevak

SRM 380 · 2007-12-04 · by gevak · Greedy, Search
Class Name: CompilingDecksWithJokers
Return Type: int
Method Name: maxCompleteDecks
Arg Types: (vector<int>, int)
Problem Statement

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.

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
4)
{123, 76, 117, 59}
89
Returns: 112

Submissions are judged against all 257 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CompilingDecksWithJokers with a public method int maxCompleteDecks(vector<int> cards, int jokers) · 257 test cases · 2 s / 256 MB per case

Submitting as anonymous