HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC-2014-15 Questions > problem:


Ind_02-30. 50657 - Permutations and Combinatorics

IMPC-2014-15 Questions

Start: Nov.22.2014 at 03:00:00 PM
Finish: Nov.22.2014 at 08:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 4th-3. 50535 - Image Compression
• 4th-6. 50536 - Epoka Furgon Shpk
• Ind_01-10. 50752 - Student Groups
• Ind_01-20. 50416 - Placing Domino...
• Ind_01-30. 50764 - Fast Typing Co...
• Ind_01-50. 50718 - Elevator
• Ind_02-10. 50497 - Falling Bricks - ...
• Ind_02-20. 50745 - Bitonic Sequence
• Ind_02-30. 50657 - Permutatio...
• Ind_03-10. 50743 - Total Scholarshi...
• Ind_03-20. 50515 - Lines - Revisited
• Ind_03-40. 50777 - Dwarfs Maze
• Ind_03-50. 50679 - Jetpack Hurdle J...
• Ind_04-10. 50787 - Expected Value
• Ind_04-20. 50520 - Filling a Matrix ...
• Ind_04-30. 50658 - The Message

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)



Для отправки решений необходимо выполнить вход.

www.contester.ru