GroupTheNumbers | Topcoder Archive

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.

Definition

Class:: GroupTheNumbers
Method:: calculate
Parameters:: int[]
Returns:: String
Method signature:: String calculate(int[] a)
(be sure your method is public)

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"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.