|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Enes Kristo.
Permutations
Combinatorics is one of the most complicated
areas of mathematics. Fortunately informatics
has enabled mathematicians to calculate large
amounts of complex data in much shorter times.
Pr. Green, who isn't very creative, needs to
solve a problem:
We have the set of numbers from 1 to n, and
we have to prepare the permutations of the numbers
from 1 to n in such a way that if we call
the permutation a1, a2,...,an; we take any
two numbers from the set ai and aj,
where i < j, then ai + i ≤ aj + j.
Question:
How many permutations are there complying
the given criteria?
Input specification
You will be given an integer (n) which determines
the range from 1 to n where n ≤ 20
Output specification
The number of the possible combinations
that follow this condition.
Sample Input
3
|
Sample Output
4
|
Explanation:
There are 4 cases possible here:
- 3,2,1 (since 3+1 ≤ 2+2 ≤ 1+3)
- 1,3,2 (since 1+1 ≤ 3+2 ≤ 2+3)
- 1,2,3 (since 1+1 ≤ 2+2 ≤ 3+3)
- 2,1,3 (since 2+1 ≤ 1+2 ≤ 3+3)
On the other hand, 2 3 1 doesn’t comply, since
(2+1) is less than (3+2),
but, (3+2) is not less than (1+3)
Для отправки решений необходимо выполнить вход.
|