Problem Statement
A Christmas cracker is a festive table decoration that resembles an oversized sweet-wrapper. The middle part of a cracker usually contains some small gift and a terrible Christmas pun. ("What does Santa feel when going down a narrow chimney? Claus-trophobia!") It is customary that each cracker should be opened by two people. Each person takes hold of one outer chamber and they pull in opposite directions, causing the cracker to split unevenly and leaving one person holding the central chamber and the prize.
N people (numbered 0 to N-1) are attending a Christmas party. Each person would like to open at least K Christmas crackers. What is the smallest total number C of crackers they need, and how should they open them?
You are given the ints N and K. Return a int[] with 2*C elements: for each cracker, the numbers of the two people who should open it. Any valid solution will be accepted.
Definition
- Class:
- ChristmasCrackers
- Method:
- crack
- Parameters:
- int, int
- Returns:
- int[]
- Method signature:
- int[] crack(int N, int K)
- (be sure your method is public)
Constraints
- N will be between 2 and 30, inclusive.
- K will be between 1 and 30, inclusive.
Examples
2
3
Returns: {0, 1, 0, 1, 0, 1 }Two people, each of them wants to open at least three crackers. The only optimal solution is obviously to use three crackers and have both people open each cracker. There are multiple ways to report this solution. E.g., {0, 1, 1, 0, 1, 0} would also be a correct answer. Note that {0, 0, 0, 1, 1, 1} is not a correct answer. The first two elements of this array say that the first cracker should be opened by person 0 and person 0, and that is not allowed: two distinct people must open each cracker.5
1
Returns: {0, 3, 1, 2, 1, 4 }If each of five people wants to open at least one cracker, we need at least three crackers. One person will open two crackers.3
4
Returns: {0, 1, 0, 1, 0, 2, 0, 2, 1, 2, 2, 1 }
Back to all problems