HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN303_2016Questions > problem:


HW083. 50671 - Phalanx

CEN303_2016Questions

Start: Oct.28.2016 at 05:00:00 PM
Finish: Nov.01.2016 at 05:00:00 AM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (8)

Contest problems

• HW051. 51019 - Finding the hidden...
• HW052. 51020 - Number of nodes r...
• HW061. 50448 - Paint Buckets
• HW062. 51021 - Number of Nodes
• HW071. 51042 - The most frequent ...
• HW072. 51043 - Genome Sequencing
• HW081. 51044 - Number of Trees
• HW082. 50699 - Fighting Vampires
• HW083. 50671 - Phalanx
• HW091. 51061 - The Longest Path
• HW101. 50682 - Hotel Durres
• HW102. 51067 - Jumping frog
• HW111. 50506 - The Biggest Island
• HW112. 50698 - Ayran Delivery
• PE11. 51023 - Preparing Keyword I...
• PE12. 50835 - Club Presidency
• PE13. 51024 - Total Stock Price

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