|
Лимит времени 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) Input The input contains the only number n. Output Output must contain the only number - the answer. Limitations 0 < n ≤ 25
Для отправки решений необходимо выполнить вход. |