GroupTheNumbers

TCO19 SRM 737 · 2018-09-18 · by Blue.Mary

TCO19 SRM 737 · 2018-09-18 · by Blue.Mary · Math

Show categories

Class Name: GroupTheNumbers

Return Type: String

Method Name: calculate

Arg Types: (vector<int>)

Problem Statement

You have a collection of cards. Each card contains one integer. You are given a int[] a. The elements of a are the numbers written on the cards.

Your are going to divide the cards into one or more groups. Each card must belong to exactly one of the groups. You get to choose the number of groups.

The value of a group of cards is equal to the product of the numbers on them. The value of a way to divide the cards into groups is equal to the sum of the values of all groups. Your task is to divide the cards into groups in such a way that the total value of the division is maximized.

Let S be the string that contains the decimal representation of the maximum total value. (For example, S = "373737", S = "0", or S = "-3737". Note that S should not contain unnecessary leading zeros.) If the length of S is 203 or less, return S. Otherwise, return a string of the following form: (the first 100 characters of S) + "..." + (the last 100 characters of S). See Example 3.

Constraints

a will contain between 1 and 373 elements, inclusive.
Each element of a will be between -737,373,737 and 737,373,737, inclusive.

Examples

{737}
Returns: "737"

{-3,-7,-37}
Returns: "256"

The best solution is to create two groups: {-3} and {-7,-37}.

{0,1,-1,2,-2,3,-3,4,-4}
Returns: "577"

{305802003, 136316694, 621448948, -175990184, 52551547, -566608000, 141205973, -137352529, 226239209, 73136038,
 345723809, 420451378, 455689639, -228162827, 593253055, 280556479, -470339174, -606141985, 594940027, -71768243,
 -475458047, 145718435, 441912314, -622312734, -701346268, 514619489, -280198616, -499528618, 545548925, 
 -219590088, 607143343, 481228395, -208750264, 212639054, 59098345, 177587003, 456261200}
Returns: "9552708453136043699764519962574992589764841282194475522705022369294739910524918614928401864033984307...4376758929349063867091932531272019128627221634558094207678674023362344641051055230025728000000000000"

{0}
Returns: "0"

95)

{0,0,0}
Returns: "0"

The only possible total value in this test case is zero. Note that you should return "0", not "".

96)

{-373}
Returns: "-373"

The correct return value may sometimes begin with the '-' character.

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

Coding Area

Language: C++17 · define a public class GroupTheNumbers with a public method string calculate(vector<int> a) · 125 test cases · 2 s / 256 MB per case