Bombar

bombar

==Include(page="template/taskheader" task_id="bombar")==

== include(page="template/taskheader" task_id="bombar") ==

În timpul bombardamentelor, Paftenie a devenit genist. Trebuie să dezamorseze nişte bombe aflate adânc în pământ şi asta repede. Sunt exact $2*N$ bombe, aşezate în două rânduri paralele, ca în figura următoare:

Poveste ...

!problema/bombar?bombar0.png!

h2. Cerinta

Între oricare două bombe consecutive din acelaşi rând sau o bombă şi corespunzătoarea sa din celălalt rând se poate săpa un tunel (bombele între care se pot săpa tuneluri apar legate în figură). Trebuie să le dezamorseze pe toate, una care una, săpând exact $2*N-1$ tuneluri şi trebuie sa poată circula intre oricare doua bombe numai prin tunelurile săpate. Înainte de a trece la treaba, Paftenie se întreabă în câte moduri se pot sapa tunelurile.

...

h2. Cerinţă

h2. Restrictii

Ajutaţi-l să afle pâna nu e prea târziu!

...

h2. Date de Intrare

h2. Date de intrare

Pe prima linie a fişierului de intrare $bombar.in$ este dat numărul $N$ al bombelor de pe un şir.

...

h2. Date de Ieşire

h2. Date de iesire

Fişierul de ieşire $bombar.out$ va conţine pe prima linie un singur număr, reprezentând numărul de posibilităţi în care se pot săpa tunelurile.
 
h2. Restricţii şi precizări
 
* $1 ≤ N ≤ 20.000$

...

h2. Exemplu

table(example). |_. bombar.in |_. bombar.out |
| 2 | 4 |
 
h3. Explicaţie
 
Bombele sunt plasate astfel:
 
!problema/bombar?bombar1.png!
 
Paftenie poate săpa tunelurile în 4 feluri:
 
!problema/bombar?bombar2.png!
 
table(example). |_. bombar.in |_. bombar.out |
|3 |15 |
 
==Include(page="template/taskfooter" task_id="bombar")==
 

| bombar.in | bombar.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="bombar") ==

383