Connection Status:
Competition Arena > MatchNumbersHard

MatchNumbersHard

SRM 311 · 2006-07-12 · by gevak

SRM 311 · 2006-07-12 · by gevak · Greedy
Class Name: MatchNumbersHard
Return Type: String[]
Method Name: maxNumber
Arg Types: (vector<string>, string)
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 String[] matches and a String 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 a String[] such that the first element is the number of digits of x (where x is the largest number that can be created), the second element contains the first 50 digits of x, and the third element contains the last 50 digits of x. If x has fewer than 50 digits, the second and third elements should each be all of x. No extra leading zeros should be added to any returned value. If n is too small to create any number, return a single zero as the number of digits and empty strings ("") as the second and third elements.

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 an integer between 1 and 10 ^ 18 (fits in a long), inclusive, with no leading zeros.
  • n will be an integer between 0 and 10 ^ 18 (fits in a long), inclusive, with no extra leading zeros.
Examples
0)
{"6","7","8"}
"21"
Returns: {"3", "210", "210" }

Example from the problem statement.

1)
{"1","7","8"}
"21"
Returns: {"15", "100000000000000", "100000000000000" }
2)
{"1","1","1","1","1","1","1","1","1","1"}
"923372036854775807"
Returns: {"923372036854775807", "99999999999999999999999999999999999999999999999999", "99999999999999999999999999999999999999999999999999" }

A lot of nines.

3)
{"1","923372036854775807"}
"923372036854775807"
Returns: {"1", "1", "1" }
4)
{"1","923372036854775806"}
"923372036854775807"
Returns: {"2", "10", "10" }
6)
{"1","923372036854775807"}
"923372036854775806"
Returns: {"1", "0", "0" }

Zero is the only digit that can be created. Note that no extra leading zeros should be added to any returned value.

9)
{"1", "10"}
"1000000"
Returns: {"999991", "10000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000" }

There are 999990 zeros in the created number, so its last 50 digits are all zeros.

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

Coding Area

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

Submitting as anonymous