Fişierul intrare/ieşire:boom.in, boom.outSursăConcurs de incalzire 2004
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

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.

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.

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).

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

Exemplu

boom.inboom.out
3 2
1 2 1 3
2 1 2
2
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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content