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 less than or equal to K.
You are given the two
Definition
- Class:
- AlienAndSetDiv2
- Method:
- getNumber
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int getNumber(int N, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 50, inclusive.
- K will be between 1 and 10, inclusive.
Examples
2
1
Returns: 4
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 invalid. One of the reasons is that in both cases the difference between the smallest element in A and the smallest element in B is too large (3-1 = 2, which is more than 1). The other 4 options are valid. Note that order of the two sets matters: the option A={1,3} and B={2,4} differs from the option A={2,4} and B={1,3}.
3
1
Returns: 8
4
2
Returns: 44
10
10
Returns: 184756
10
1
Returns: 1024
10
2
Returns: 18272
10
3
Returns: 59158
10
4
Returns: 103112
10
5
Returns: 137574
10
6
Returns: 160770
10
7
Returns: 174702
10
8
Returns: 181682
10
9
Returns: 184244
50
10
Returns: 153890414
50
9
Returns: 229887715
50
8
Returns: 859928623
50
7
Returns: 403429534
50
6
Returns: 869350078
50
5
Returns: 111275134
50
4
Returns: 875217107
50
3
Returns: 549774365
50
2
Returns: 100357637
50
1
Returns: 898961331
47
7
Returns: 941345617
44
3
Returns: 89196202
49
8
Returns: 456431953
17
10
Returns: 192845768
17
5
Returns: 933432196
25
5
Returns: 117863904
36
6
Returns: 852563978
44
9
Returns: 547020099
18
8
Returns: 137210797
35
3
Returns: 204648334
37
8
Returns: 167326465
27
9
Returns: 980662362
16
1
Returns: 65536
16
8
Returns: 507002020
38
4
Returns: 888484602
33
10
Returns: 122638209
32
7
Returns: 226530787
47
3
Returns: 434791923