== include(page="template/taskheader" task_id="ninjago") ==
Poveste şi cerinţă...
Zane trebuie să păzească cele <tex> N </tex> păpuşi din muzeu. Între aceste păpuşi există <tex> M </tex> coridoare pe care se poate circula în ambele sensuri. Se garantează faptul că pe cele <tex> M </tex> coridoare Zane poate ajunge la fiecare dintre cele <tex> N </tex> păpuşi.
Skulkiu, având la dispoziţie <tex> 5 </tex> tipuri de obstacole <tex> (A, B, C, D, E) </tex> încearcă să-l oprească pe Zane punând pe fiecare coridor exact <tex> 4 </tex> obstacole. Zane poate distruge obstacolele *doar* de tip <tex> A, B, C, D </tex>.
Pentru a distruge un obstacol de tipul <tex> A </tex> arma lui Zane are nevoie de <tex> 1 </tex> unitate de energie, pentru a distruge un obstacol de tipul <tex> B </tex> de <tex> 2 </tex> unităţi de energie, pentru a distruge un obstacol de tipul <tex> C </tex> de <tex> 3 </tex> unităţi de energie, iar pentru a distruge un obstacol de tipul <tex> D </tex> de <tex> 4 </tex> unităţi de energie. Totusi, datorită dispozitivului cu care Skulkiu amplasează obstacolele pe coridor, pentru a distruge al doilea obstacol amplasat pe coridor este nevoie de <tex> 5 </tex> ori mai multă energie decât cea obişnuită, pentru a distruge cel de-al treilea obstacol amplasat pe coridor este nevoie de <tex> 25 </tex> ori mai multă energie decât cea obişnuită, iar pentru a distruge al patrulea obstacol amplasat pe acelaşi coridor este nevoie de <tex> 125 </tex> de ori mai multă energie decât cea obişnuită.
h2. Date de intrare
h2. Cerinta:
Fişierul de intrare $ninjago.in$ ...
Zane doreste sa elibereze coridoare astfel incat sa aiba acces la fiecare papusa. El nu va înlătura obstacolele de pe toate coridoarele, ci doar strictul necesar pentru a avea acces la fiecare păpuşă. Zane doreşte să-i lase pe ceilalţi ninja să se antreneze aşa că face în aşa fel încât ajutorul pentru distrugerea obstacolelor de tip E să fie minim şi abia apoi, dintre toate posibilitatile cu ajutor minim, el să utilizeze un număr minim de unităţi de energie. Pentru coridoarele pe care se află obstacole de tip <tex> E </tex> Zane consumă energie doar pentru obstacolele de tip <tex> A, B, C </tex> şi <tex> D </tex>.
h2. Date de ieşire
Raspundeti la urmatoarele cerinte:
În fişierul de ieşire $ninjago.out$ ...
# Precizati la cate dintre cele <tex> N </tex> papusi poate ajunge Zane, *fara* a cere ajutorul altor ninja
# Precizati numarul *minim* de coridoare pentru eliberarea carora Zane trebuie sa ceara ajutor extern, pentru a reusi sa ajunga la toate cele <tex> N </tex> papusi si, dintre aceste solutii, numarul *minim* de obstacole de tip <tex> E </tex> ce se afla in total pe coridoare.
# Precizati, in contextul intrebarii de mai sus, care este numărul *minim* de unităţi de energie utilizate.
h2. Restricţii
h2. Input:
* $... ≤ ... ≤ ...$
Fişierul $*ninjago.in*$ conţine pe prima linie un număr natural <tex> T </tex> care poate avea doar valorile <tex> 1 </tex>, <tex> 2 </tex> sau <tex> 3 </tex>, reprezentând cerinţa care va fi rezolvată. Pe a doua linie se gasesc numerele naturale <tex> N </tex> şi <tex> M </tex>, separate printr-un spaţiu. Urmeaza pe <tex> M </tex> linii descrierea coridoarelor. Fiecare linie va contine doua numere naturale, separate printr-un spatiu, reprezentand cele doua papusi intre care se poate circula pe coridorul respectiv. Pe aceeasi linie, separat printr-un spatiu, se gaseste un sir de patru litere corespunzatoare celor patru tipuri de obstacole, in ordinea in care acestea au fost amplasate pe coridorul respectiv. Intre cele patru litere nu se afla niciun spatiu.
h2. Exemplu
h2. Output:
table(example). |_. ninjago.in |_. ninjago.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* <tex> T = 1 </tex>: Fisierul *$ninjago.out$* contine pe prima linie doar numarul papusilor la care Zane poate ajunge de unul singur.
* <tex> T = 2 </tex>: Fisierul *$ninjago.out$* contine pe prima linie numarul *minim* de coridoare pentru eliberarea carora Zane trebuie sa ceara ajutor extern, pentru a reusi sa ajunga la toate cele <tex> N </tex> papusi, iar pe a doua numarul *minim* de obstacole de tip <tex> E </tex> ce se afla in total pe o astfel de multime de coridoare.
* <tex> T = 3 </tex>: Fisierul *$ninjago.out$* contine pe prima linie doar numărul *minim* de unităţi de energie utilizate, in contextul unei solutii de la intrebarea de mai sus.
h3. Explicaţie
h2. Restricţii
...
* *Iniţial Zane se află lângă păpuşa* <tex> 1 </tex>.
* *Indiferent de sensul de parcurgere al coridorului de către Zane pentru a înlătura obstacolele, energia consumată este aceeaşi.*
* <tex> 1 \leq N, M \leq 31.200 </tex>.
* Pentru rezolvarea corectă a primei cerinţe se acordă <tex> 20 </tex> de puncte.
* Pentru rezolvarea corectă a celei de-a doua cerinţe se acordă <tex> 40 </tex> de puncte.
* Pentru rezolvarea corectă a celei de-a treia cerinţe se acordă <tex> 30 </tex> de puncte.
* *Conform regulamentului OJI, se vor acorda* <tex> 10 </tex> *puncte din oficiu.*
h2. Exemplu:
table(example). |_. *ninjago.in* |_. *ninjago.out* |_. Explicatie |
| 1
9 15
1 2 CBAA
1 5 ABAA
2 6 CBEA
2 7 ACBA
2 5 CBEA
3 4 ABAA
3 7 AECE
3 8 CBAC
3 9 ECEE
4 8 DBAD
4 9 ECEB
5 6 CBAD
5 7 BAAD
6 7 CBAA
7 8 ECEB
| 5
| Zane va putea ajunge la nodurile 1, 2, 5, 6, 7
eliberând singur coridoarele (1,2), (1,5), (2,7) şi (6,7) |
| 2
9 15
1 2 CBAA
1 5 ABAA
2 6 CBEA
2 7 ACBA
2 5 CBEA
3 4 ABAA
3 7 AECE
3 8 CBAC
3 9 ECEE
4 8 DBAD
4 9 ECEB
5 6 CBAD
5 7 BAAD
6 7 CBAA
7 8 ECEB
| 2
4
| Zane trebuie să ceară ajutor pentru eliberarea a 2 coridoare
pentru a putea ajunge la toate cele 9 păpuşi
Zane are nevoie de ajutor pentru a elibera coridoarele (3,7) şi (4,9).
Pe fiecare dintre aceste 2 coridoare se află câte 2 obstacole de tip E,
deci în total 4 obstacole de tip E. |
| 3
9 15
1 2 CBAA
1 5 ABAA
2 6 CBEA
2 7 ACBA
2 5 CBEA
3 4 ABAA
3 7 AECE
3 8 CBAC
3 9 ECEE
4 8 DBAD
4 9 ECEB
5 6 CBAD
5 7 BAAD
6 7 CBAA
7 8 ECEB
| 1593
| Zane va consuma minim 1593 de unităţi de energie astfel:
163 pentru coridorul (1,2)
161 pentru coridorul (1,5)
191 pentru coridorul (2,7)
161 pentru coridorul (3,4)
76 pentru coridorul (3,7)
413 pentru coridorul (3,8)
265 pentru coridorul (4,9)
163 pentru coridorul (6,7)
Pentru coridorul (4,9) obstacolele sunt ECEB,
Deci Zane va consuma 0+3*5+0*25+2*125=265 unităţi de energie |
== include(page="template/taskfooter" task_id="ninjago") ==
