AlienAndSetDiv1
SRM 605 · 2013-12-22 · by Witaliy
Problem Statement
Alien Fred wants to destroy the Earth. But before he does that, he wants to solve the following problem.
He has the set {1, 2, 3, ..., 2N}. He wants to split this set into two new sets A and B. The following conditions must all be satisfied:
- Each element of the original set must belong to exactly one of the sets A and B.
- The two new sets must have the same size. (I.e., each of them must contain exactly N numbers.)
- For each i from 1 to N, inclusive: Let A[i] be the i-th smallest element of A, and let B[i] be the i-th smallest element of B. The difference |A[i] - B[i]| must be greater than or equal to K.
You are given the two
Constraints
- N will be between 1 and 50, inclusive.
- K will be between 1 and 10, inclusive.
2 2 Returns: 2
The initial set is {1, 2, 3, 4}. The following 6 pairs of subsets are possible in this case: A={1, 2} and B={3, 4} A={1, 3} and B={2, 4} A={1, 4} and B={2, 3} A={2, 3} and B={1, 4} A={2, 4} and B={1, 3} A={3, 4} and B={1, 2} The first option and the last option are both valid. The other 4 options are invalid. Note that order of the two sets matters: the option A={1,2} and B={3,4} differs from the option A={3,4} and B={1,2}.
3 1 Returns: 20
4 2 Returns: 14
10 7 Returns: 40
10 1 Returns: 184756
Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AlienAndSetDiv1 with a public method int getNumber(int N, int K) · 53 test cases · 2 s / 256 MB per case