bombar

Bombar

== include(page="template/taskheader" task_id="bombar") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| bombar.in | bombar.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="bombar") ==

==Include(page="template/taskheader" task_id="bombar")==
==Include(page="template/raw")==
 
Link: [1]File-List
 
bombardament
 
 
 
In timpul bombardamentelor, Paftenie a devenit genist. Trebuie sa dezamorseze niste bombe aflate adanc in pamant si asta repede. Sunt exact 2*N bombe, asezate in doua randuri paralele, ca in figura urmatoare :
 
*--*--*..*
| | | |
*--*--*..*
 
Intre oricare doua bombe consecutive din acelasi rand sau o bomba si corespunzatoarea sa din celalalt rand se poate sapa un tunel (bombele intre care se pot sapa tuneluri apar legate in figura). Trebuie sa le dezamorseze pe toate, una care una, sapand exact 2*N-1 tuneluri si trebuie sa poata circula intre oricare doua bombe numai prin tunelurile sapate. Inainte de a trece la treaba, Paftenie se intreaba in cate moduri se pot sapa tunelurile.
 
h2. Cerinta
 
Ajutati-l sa afle pana nu e prea tarziu!
 
h2. Date de Intrare (fisier: bombar.in)
 
Pe prima linie a fisierului de intrare este dat numarul N al bombelor de pe un sir.
 
h2. Date de Iesire (fisier: bombar.out)
 
Fisierul de iesire va contine pe prima linie un singur numar, reprezentand numarul de posibilitati in care se pot sapa tunelurile.
 
h2. Restrictii si precizari
 
S 1 <= N <= 20.000
 
h2. Exemplu
 
 
|bombar.in |bombar.out |Explicatie |
 
|2 |4 |Bombele sunt plasate astfel: |
| | | |
| | |*--* |
| | || | |
| | |*--* |
| | | |
| | |El poate sapa tunelurile in 4 feluri: |
| | | |
| | |*--* *--* *--* *--* |
| | || | | | | | | | |
| | |*--* *--* *--* *--* |
 
|3 |15 | |
 
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/bombar/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="bombar")==