==Include(page="template/taskheader" task_id="boom")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
Boom
 
 
 
Va las sa ghiciti cine este protagonistul acestei probleme. Nu este foarte greu de imaginat ca numele lui va fi tot Petrica. Ce face el de data aceasta este ceva cu totul aparte: se "joaca" cu sobolanul cel ghidus. Acesta din urma este localizat intr-o galerie subterana care se prezinta ca o succesiune de N camere dispuse in linie si care sunt numerotate de la 1 la N in ordinea parcurgerii lor de la un capat la celalalt. Petrica nu stie unde este localizat sobolanul dar vrea cu orice pret sa-l rada de pe fata pamantului. Astfel, el poate detona bombe otravitoare in unele din camerele galeriei (uneori chiar in mai multe simultan) pentru a omori sobolanul. Daca acesta este intr-una din camerele gazate moare pe loc, daca nu camera nu pateste nimic si sobolanul poate circula prin ea imediat dupa detonarea bombei. Lucrurile stau in felul urmator: cei doi inamici joaca in mod cinstit astfel ca dupa ce Petrica detoneaza un set bombe care vor exploda simultan, sobolanul, daca nu a murit, se va muta intr-una din
camerele vecine celei in care se afla (camerele de la capete au o singura camera vecina). Petrica a alcatuit un plan de atac compus din M sarje. Pentru fiecare sarja se cunosc pretul realizarii ei si camerele gazate daca ea este pusa in practica. La fiecare pas Petrica va alege doar una din cele M sarje pentru a gaza anumite camere.
 
h2. Cerinta
 
Ajutati-l pe Petrica sa gaseasca o strategie de cost minim in urma careia sobolanul va fi omorat indiferent de pozitia initiala a acestuia.
 
h2. Date de Intrare
 
Pe prima linie in fisierul de intrare boom.in se afla doua numere intregi separate de un singur spatiu N si M, reprezentand numarul de camere ale galeriei si numarul de sarje. Pe urmatoarele M linii sunt date informatiile cu privire la fiecare sarja (ele sunt numerotate de la 1 la M in ordinea in care se gasesc in fisierul de intrare). Astfel, pe fiecare linie sunt doi intregi P si Q, reprezentand pretul si numarul de camere gazete in sarja. Urmeaza Q numere (Q nu este mai mare decat 4) reprezentand camerele gazate.
 
h2. Date de Iesire
 
Pe prima linie din fisierul de iesire boom.out se va gasi un numar intreg reprezentand costul minim al unei strategii in urma careia sobolanul va fi mort. Pe urmatoarele linie se afla un numar T reprezentand numarul de sarje care il va omori in mod sigur. Urmatoarele T linii contin numerele sarjelor utilizate de Petrica (aceasta sunt date in ordinea in care au fost utilizate).
 
h2. Restrictii si precizari
 
S 1 <= N <= 20
 
S 1 <= M <= 50
 
S Sobolanul nu poate sta pe loc
 
S Daca exista mai multe solutii cu acelasi cost minim se poate afisa oricare dintre ele
 
S O sarja poate fi folosita de mai multe ori
 
h2. Exemplu
 
boom.in boom.out
3 2 2
 
1 2 1 3 2
 
2 1 2 1
 
1
 
 
 
Explicatii
 
 
 
Petrica detoneaza foloseste de doua ori sarja 1. Oriunde s-ar afla sobolanul acesta va muri: daca este in camera 1 sau 3 va muri dupa prima gazare daca se afla in a doua camera va fi obligat sa se mute intr-un din camerele 1 si 3 la urmatorul pas, fiind astfel prins de cea dea doua gazare. Costul total este 2 cel mai mic posibil.
 

==Include(page="template/taskheader" task_id="boom")==
 
Va las sa ghiciti cine este protagonistul acestei probleme. Nu este foarte greu de imaginat ca numele lui va fi tot Petrica. Ce face el de data aceasta este ceva cu totul aparte: se joaca cu sobolanul cel ghidus. Acesta din urma este localizat intr-o galerie subterana care se prezinta ca o succesiune de $N$ camere dispuse in linie si care sunt numerotate de la $1$ la $N$ in ordinea parcurgerii lor de la un capat la celalalt. Petrica nu stie unde este localizat sobolanul dar vrea cu orice pret sa-l rada de pe fata pamantului. Astfel, el poate detona bombe otravitoare in unele din camerele galeriei (uneori chiar in mai multe simultan) pentru a omori sobolanul. Daca acesta este intr-una din camerele gazate moare pe loc, daca nu camera nu pateste nimic si sobolanul poate circula prin ea imediat dupa detonarea bombei. Lucrurile stau in felul urmator: cei doi inamici joaca in mod cinstit astfel ca dupa ce Petrica detoneaza un set bombe care vor exploda simultan, sobolanul, daca nu a murit, se va muta intr-una din camerele vecine celei in care se afla (camerele de la capete au o singura camera vecina). Petrica a alcatuit un plan de atac compus din $M$ sarje. Pentru fiecare sarja se cunosc pretul realizarii ei si camerele gazate daca ea este pusa in practica. La fiecare pas Petrica va alege doar una din cele $M$ sarje pentru a gaza anumite camere.
 
h2. Cerinta
 
Ajutati-l pe Petrica sa gaseasca o strategie de cost minim in urma careia sobolanul va fi omorat indiferent de pozitia initiala a acestuia.
 
h2. Date de Intrare
 
Pe prima linie in fisierul de intrare $boom.in$ se afla doua numere intregi separate de un singur spatiu $N$ si {$M$}, reprezentand numarul de camere ale galeriei si numarul de sarje. Pe urmatoarele $M$ linii sunt date informatiile cu privire la fiecare sarja (ele sunt numerotate de la $1$ la $M$ in ordinea in care se gasesc in fisierul de intrare). Astfel, pe fiecare linie sunt doi intregi $P$ si {$Q$}, reprezentand pretul si numarul de camere gazete in sarja. Urmeaza $Q$ numere ({$Q$} nu este mai mare decat {$4$}) reprezentand camerele gazate.
 
h2. Date de Iesire
 
Pe prima linie din fisierul de iesire $boom.out$ se va gasi un numar intreg reprezentand costul minim al unei strategii in urma careia sobolanul va fi mort. Pe urmatoarele linie se afla un numar $T$ reprezentand numarul de sarje care il va omori in mod sigur. Urmatoarele $T$ linii contin numerele sarjelor utilizate de Petrica (aceasta sunt date in ordinea in care au fost utilizate).
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 20$
* $1 ≤ M ≤ 50$
* Sobolanul nu poate sta pe loc
* Daca exista mai multe solutii cu acelasi cost minim se poate afisa oricare dintre ele
* O sarja poate fi folosita de mai multe ori
 
h2. Exemplu
 
table(example). |_. boom.in |_. boom.out |
| 3 2
1 2 1 3
2 1 2
| 2
2
1
1 |
 
h3. Explicatii
 
Petrica detoneaza foloseste de doua ori sarja 1. Oriunde s-ar afla sobolanul acesta va muri: daca este in camera 1 sau 3 va muri dupa prima gazare daca se afla in a doua camera va fi obligat sa se mute intr-un din camerele 1 si 3 la urmatorul pas, fiind astfel prins de cea dea doua gazare. Costul total este 2 cel mai mic posibil.
 
==Include(page="template/taskfooter" task_id="boom")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/boom/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="boom")==

140