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 int N. You are also given another int K. Return the number of pairs (A,B) such that both A and B are permutations of size N, and magic(A,B) is greater than or equal to K. (Note that A and B are not required to be distinct.)
Print the number of pairs (A,B) such that both A and B are permutations of size N, and magic(A,B) is greater than or equal to K.
Case 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.
Case 2:
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.
Case 3:
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.
