Problem Statement
This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.
Little Elephant from the Zoo of Lviv likes permutations. A permutation of size N is a sequence (a1, ..., aN) that contains each of the numbers from 1 to N exactly once. For example, (3,1,4,5,2) is a permutation of size 5.
Given two permutations A = (a1, ..., aN) and B = (b1, ..., bN), the value magic(A,B) is defined as follows: magic(A,B) = max(a1,b1) + max(a2,b2) + ... + max(aN,bN).
You are given the
Definition
- Class:
- LittleElephantAndPermutationDiv2
- Method:
- getNumber
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long getNumber(int N, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 10, inclusive.
- K will be between 1 and 100, inclusive.
Examples
1
1
Returns: 1
For N=1 the only pair of permutations is ( (1), (1) ). The magic of this pair of permutations is 1, so we count it.
2
1
Returns: 4
Now there are four possible pairs of permutations. They are shown below, along with their magic value. magic( (1,2), (1,2) ) = 1+2 = 3 magic( (1,2), (2,1) ) = 2+2 = 4 magic( (2,1), (1,2) ) = 2+2 = 4 magic( (2,1), (2,1) ) = 2+1 = 3 In all four cases the magic value is greater than or equal to K.
3
8
Returns: 18
When A = (1,2,3), there are 3 possibilities for B: (2,3,1), (3,1,2) and (3,2,1). For each of the other 5 values of A, it can be shown that there are 3 possibilities for B as well. Therefore the answer is 3*6 = 18.
10
47
Returns: 13168189440000
7
1
Returns: 25401600
7
7
Returns: 25401600
7
47
Returns: 0
10
100
Returns: 0
9
74
Returns: 0
9
65
Returns: 1881169920
10
80
Returns: 52254720000
10
70
Returns: 9397924300800
10
65
Returns: 12799692057600
10
57
Returns: 13168153152000
10
40
Returns: 13168189440000
10
47
Returns: 13168189440000
10
1
Returns: 13168189440000
10
12
Returns: 13168189440000
9
50
Returns: 131413726080
9
1
Returns: 131681894400
8
1
Returns: 1625702400
7
1
Returns: 25401600
6
1
Returns: 518400
5
1
Returns: 14400
4
1
Returns: 576
3
1
Returns: 36
7
32
Returns: 24857280
6
17
Returns: 518400
5
7
Returns: 14400
6
15
Returns: 518400
5
10
Returns: 14400
1
100
Returns: 0
8
100
Returns: 0
10
66
Returns: 12496977561600
10
89
Returns: 0
10
30
Returns: 13168189440000
10
62
Returns: 13133723097600
10
55
Returns: 13168189440000
10
99
Returns: 0
10
88
Returns: 0
10
60
Returns: 13164284851200
10
56
Returns: 13168185811200
10
11
Returns: 13168189440000
3
20
Returns: 0
5
16
Returns: 14280
3
100
Returns: 0
4
14
Returns: 96
2
4
Returns: 2
1
2
Returns: 0
4
100
Returns: 0
10
67
Returns: 12033071769600
4
12
Returns: 480
8
40
Returns: 1619412480
5
21
Returns: 2400
2
100
Returns: 0
5
17
Returns: 13800
10
73
Returns: 5323972147200