FoxAndNecklace | Topcoder Archive

Problem Statement

Fox Ciel has a collection of marbles. Different marbles may have different values. You are given the values of Ciel's marbles in the int[] value. Each marble has a different color. Thus, we can distinguish between any two marbles, even if they have the same value.

Ciel can build a necklace using some marbles from her collection. While doing so, she has to follow these rules:

A necklace must contain exactly k marbles.
The total value of marbles on the necklace must be at least minimalSum (otherwise the necklace looks too cheap).

Ciel is now going on a vacation. The vacation lasts for d days. On each of those d days Ciel wants to wear a different necklace. Two necklaces are considered the same if and only if one of them can be rotated and possibly flipped to match the other. For example, if we have four different marbles labeled 0, 1, 2, and 3, then {0,1,2,3}, {2,3,0,1} and {3,2,1,0} are three versions of the same necklace, but {1,3,2,0} is a different necklace.

You are given the int[] value, the ints k and minimalSum, and the long d. Return "Possible" if Ciel can wear a different necklace each day, and "Impossible" otherwise.

Definition

Class:: FoxAndNecklace
Method:: possible
Parameters:: int[], int, int, long
Returns:: String
Method signature:: String possible(int[] value, int k, int minimalSum, long d)
(be sure your method is public)

Constraints

value will contain between 3 and 80 elements, inclusive.
k will be between 3 and |value|, inclusive.
Each element in value will be between 1 and 10,000,000, inclusive.
minimalSum will be between 1 and 1,000,000,000, inclusive.
d will be between 1 and 1,000,000,000,000 (10^12), inclusive.

Examples

```
{1,100,100,100}	
```
```
3
```
```
250
```
```
2
```
```
Returns: "Impossible"
```
Each day Ciel has to wear a necklace with 3 marbles such that their total value is at least 250. There is only one set of three marbles with this property: marbles 1, 2, and 3. These three marbles can only be used to form one valid necklace: {1,2,3}. (Note that all other permutations of these three marbles correspond to the same necklace.)
```
{1,100,100,100}	
```
```
3
```
```
201
```
```
4
```
```
Returns: "Possible"
```
This time we can use any three marbles to make a necklace. Thus, there are 4 valid necklaces: {0,1,2}, {0,1,3}, {0,2,3}, and {1,2,3}.
```
{1,1,1,1}
```
```
4
```
```
1
```
```
2
```
```
Returns: "Possible"
```
In each necklace we must use all four marbles. However, we can put them into different orders. There are three distinct necklaces: {0,1,2,3}, {0,1,3,2}, and {0,2,1,3}.

{1,10,100,1000,10000,100000,1000000}

Returns: "Possible"

There are exactly 168 different necklaces we can make.

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

22054032001

Returns: "Impossible"

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

22054032000

Returns: "Possible"

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.