Connection Status:
Competition Arena > MatchNumbersEasy

MatchNumbersEasy

SRM 311 · 2006-07-12 · by gevak

SRM 311 · 2006-07-12 · by gevak · Dynamic Programming, Greedy
Class Name: MatchNumbersEasy
Return Type: String
Method Name: maxNumber
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

Each digit can be represented using a certain number of matches. Your goal is to create the largest possible number using the matches that you have. For example, if you need 6 matches for zero, 7 matches for one, and 8 matches for two, and you have 21 matches, the largest number you can create is 210 (8 + 7 + 6 = 21 matches).

You are given a int[] matches and an int n. The ith element (zero-indexed) of matches is the number of matches needed to represent the digit i. n is the number of matches you have. Return the largest possible number you can create without extra leading zeros.

Notes

  • It is not necessary to use all given matches. Some matches may be left unused.

Constraints

  • matches will contain between 1 and 10 elements, inclusive.
  • Each element of matches will be between 1 and 50, inclusive.
  • n will be between 1 and 50, inclusive.
  • n matches will be enough to construct at least 1 digit.
Examples
0)
{6,7,8}
21
Returns: "210"

Example from the problem statement.

1)
{5,23,24}
30
Returns: "20"

24 matches for two and 5 matches for zero. 1 match is left unused.

2)
{1,5,3,2}
1
Returns: "0"

This is the only number that can be created.

3)
{1,1,1,1,1,1,1,1,1,1}
50
Returns: "99999999999999999999999999999999999999999999999999"
4)
{2,20,30}
19
Returns: "0"

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

Coding Area

Language: C++17 · define a public class MatchNumbersEasy with a public method string maxNumber(vector<int> matches, int n) · 76 test cases · 2 s / 256 MB per case

Submitting as anonymous