ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2007 > задача:

A. Phalanx

Задачи сборника

• A. Phalanx
• B. Bitsorting
• C. Cubes
• D. Factorial
• E. Lights
• F. Parliament
• G. Strange Numbers
• H. Two Captains
• I. Boundary Troops

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Михаил Копачев, РГАТА. Сложность Гамма

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)

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

Input 1 Output 1
Input 2 Output 2

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