Fişierul intrare/ieşire:ninjago.in, ninjago.outSursăOJI 2017, Clasele 11-12
AutorMuresan CodrutaAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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. Totusi, 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ă.

Cerinta:

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  E Zane consumă energie doar pentru obstacolele de tip  A, B, C şi  D .

Raspundeti la urmatoarele cerinte:

  1. Precizati la cate dintre cele  N papusi poate ajunge Zane, fara a cere ajutorul altor ninja
  2. Precizati numarul minim de coridoare pentru eliberarea carora Zane trebuie sa ceara ajutor extern, pentru a reusi sa ajunga la toate cele  N papusi si, dintre aceste solutii, numarul minim de obstacole de tip  E ce se afla in total pe coridoare.
  3. Precizati, in contextul intrebarii 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 gasesc numerele naturale  N şi  M , separate printr-un spaţiu. Urmeaza pe  M 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.

Output:

  •  T = 1 : Fisierul ninjago.out contine pe prima linie doar numarul papusilor la care Zane poate ajunge de unul singur.
  •  T = 2 : 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  N papusi, iar pe a doua numarul minim de obstacole de tip  E ce se afla in total pe o astfel de multime de coridoare.
  •  T = 3 : 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.

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 \leq N, M \leq 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:

ninjago.inninjago.outExplicatie
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?