FoxAndSouvenirTheNext | Topcoder Archive

Problem Statement

Fox Ciel just returned home from her trip to New Fox City. She has brought a bunch of souvenirs. You are given their values in a int[] value.

Now she wants to give each souvenir either to her mother or to her father. She would like to divide the souvenirs in a fair way. More precisely:

The total number of souvenirs given to her mother must be the same as the total number of souvenirs given to her father.
At the same time, the total value of souvenirs given to her mother must be the same as the total value of souvenirs given to her father.

Return "Possible" if she can reach her goal, and "Impossible" otherwise.

Definition

Class:: FoxAndSouvenirTheNext
Method:: ableToSplit
Parameters:: int[]
Returns:: String
Method signature:: String ableToSplit(int[] value)
(be sure your method is public)

Constraints

value will contain between 1 and 50 elements, inclusive.
Each element in value will be between 1 and 50, inclusive.

Examples

```
{1,2,3,4}
```
```
Returns: "Possible"
```
One valid solution is to give the souvenirs with values 1 and 4 to her mother and the other two to her father. Each parent receives two souvenirs, and as 1+4 = 2+3, the total value is also the same for both parents.
```
{1,1,1,3}
```
```
Returns: "Impossible"
```
There is no valid solution. Note that {1,1,1} and {3} is not a valid way to split the souvenirs: even though the total value is the same, the number of souvenirs is not.
```
{1,1,2,3,5,8}
```
```
Returns: "Possible"
```
We have 1+1+8 = 2+3+5.
```
{2,3,5,7,11,13}
```
```
Returns: "Impossible"
```
The sum of values is an odd number, so it is impossible.

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48}

Returns: "Possible"

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

Returns: "Impossible"

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.