Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
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)
Для отправки решений необходимо выполнить вход.
|