Connection Status:
Competition Arena > FoxAndNecklace

FoxAndNecklace

TCO17 New 3B · 2017-03-31 · by cgy4ever

TCO17 New 3B · 2017-03-31 · by cgy4ever · Brute Force
Class Name: FoxAndNecklace
Return Type: String
Method Name: possible
Arg Types: (vector<int>, int, int, long long)
Problem Statement

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.

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
0)
{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)
{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}.

2)
{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}.

3)
{1,10,100,1000,10000,100000,1000000}
5
1010101
168
Returns: "Possible"

There are exactly 168 different necklaces we can make.

4)
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
10
100
22054032001
Returns: "Impossible"

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

Coding Area

Language: C++17 · define a public class FoxAndNecklace with a public method string possible(vector<int> value, int k, int minimalSum, long long d) · 280 test cases · 2 s / 256 MB per case

Submitting as anonymous