HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50671 - Phalanx

Guest
• Review clarifications (8)

Section problems

• 50672 - Math and Soldiers
• 50671 - Phalanx
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys

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.
Автор: Михаил Копачев, РГАТА.

Bonus Question

There are n castles upon the checkered nxn-sized board, every vertical line having one castle. Let a horizontal line having at least one castle be called a bat. The position on the board will be called a phalanx if:

• the castle standing at the leftmost vertical line, stands also in the lowest horizontal line (and beats it);
• there is no unbeaten horizontal line, that separate any castle from the lower horizontal line (the beaten horizontal lines form a continuous beaten field having no gaps at the bottom of the board);
• selecting first left k castles we shall get a regular phalanx of the width k.

The drawins below show four positions, two of which - those on the left are phalanxes, and those on the right are not.

Position (c) is not a regular phalanx as the second (unbeaten) horizontal line separates the second and the third castles from the lower horizontal line (condition 2 of the above list is not satisfied).
Position (d) is not a regular phalanx: if we take two left castles, they will not form a regular phalanx (condition 3 of the above list is not satisfied).

Your task is to make a program that will use the specified number n to define the quantity of different arrangements for castles m, that will be phalanxes.
For example, when n=3, it is possible to have only m=5 phalanxes (e1)-(e5)

Input
The input contains the only number n.
Output
Output must contain the only number - the answer.
Limitations
0 < n ≤ 18

Input 1 Output 1
3
5
Input 2 Output 2
5
35

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

www.contester.ru