Fişierul intrare/ieşire:	ninjago.in, ninjago.out	Sursă	OJI 2017, Clasele 11-12
Autor	Muresan Codruta	Adăugată de	Vlad Dumitru-Popescu •depevlad
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ninjago

Zane trebuie să păzească cele N păpuşi din muzeu. Între aceste păpuşi există M coridoare pe care se poate circula în ambele sensuri. Se garantează faptul că pe cele M coridoare Zane poate ajunge la fiecare dintre cele N păpuşi.
Skulkiu, având la dispoziţie 5 tipuri de obstacole (A, B, C, D, E) încearcă să-l oprească pe Zane punând pe fiecare coridor exact 4 obstacole. Zane poate distruge obstacolele doar de tip A, B, C, D.
Pentru a distruge un obstacol de tipul A arma lui Zane are nevoie de 1 unitate de energie, pentru a distruge un obstacol de tipul B de 2 unităţi de energie, pentru a distruge un obstacol de tipul C de 3 unităţi de energie, iar pentru a distruge un obstacol de tipul D de 4 unităţi de energie. Totuşi, datorită dispozitivului cu care Skulkiu amplasează obstacolele pe coridor, pentru a distruge al doilea obstacol amplasat pe coridor este nevoie de 5 ori mai multă energie decât cea obişnuită, pentru a distruge cel de-al treilea obstacol amplasat pe coridor este nevoie de 25 ori mai multă energie decât cea obişnuită, iar pentru a distruge al patrulea obstacol amplasat pe acelaşi coridor este nevoie de 125 de ori mai multă energie decât cea obişnuită.

Cerinţă:

Zane doreşte să elibereze coridoare astfel încât să aibă acces la fiecare păpuşă. 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 posibilităţile cu ajutor minim, el să utilizeze un număr minim de unităţi de energie. Pentru coridoarele pe care se află obstacole de tip E Zane consumă energie doar pentru obstacolele de tip A, B, C şi D.

Răspundeţi la următoarele cerinţe:

1. Precizaţi la câte dintre cele N păpuşi poate ajunge Zane, fără a cere ajutorul altor ninja
2. Precizaţi numărul minim de coridoare pentru eliberarea cărora Zane trebuie să ceară ajutor extern, pentru a reuşi să ajungă la toate cele N păpuşi şi, dintre aceste soluţii, numărul minim de obstacole de tip E ce se află în total pe coridoare.
3. Precizaţi, în contextul întrebării de mai sus, care este numărul minim de unităţi de energie utilizate.

Input:

Fişierul ninjago.in conţine pe prima linie un număr natural T care poate avea doar valorile 1, 2 sau 3, reprezentând cerinţa care va fi rezolvată. Pe a doua linie se găsesc numerele naturale N şi M, separate printr-un spaţiu. Urmează pe M linii descrierea coridoarelor. Fiecare linie va conţine două numere naturale, separate printr-un spaţiu, reprezentând cele două păpuşi între care se poate circula pe coridorul respectiv. Pe aceeaşi linie, separat printr-un spaţiu, se găseşte un şir de patru litere corespunzătoare celor patru tipuri de obstacole, în ordinea în care acestea au fost amplasate pe coridorul respectiv. Între cele patru litere nu se află niciun spaţiu.

Output:

• T = 1: Fişierul ninjago.out conţine pe prima linie doar numărul păpuşilor la care Zane poate ajunge de unul singur.
• T = 2: Fişierul ninjago.out conţine pe prima linie numărul minim de coridoare pentru eliberarea cărora Zane trebuie să ceară ajutor extern, pentru a reuşi să ajungă la toate cele N păpuşi, iar pe a doua numărul minim de obstacole de tip E ce se află în total pe o astfel de mulţime de coridoare.
• T = 3: Fişierul ninjago.out conţine pe prima linie doar numărul minim de unităţi de energie utilizate, în contextul unei soluţii de la întrebarea de mai sus.

Restricţii

• Iniţial Zane se află lângă păpuşa 1.
• Indiferent de sensul de parcurgere al coridorului de către Zane pentru a înlătura obstacolele, energia consumată este aceeaşi.
• 1 ≤ N, M ≤ 31.200.
• Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte.
• Pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 40 de puncte.
• Pentru rezolvarea corectă a celei de-a treia cerinţe se acordă 30 de puncte.
• Conform regulamentului OJI, se vor acorda 10 puncte din oficiu.

Exemplu:

Cum se trimit solutii?