Revizia anterioară Revizia următoare
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 păpuşi din muzeu. Între aceste păpuşi există coridoare pe care se poate circula în ambele sensuri. Se garantează faptul că pe cele coridoare Zane poate ajunge la fiecare dintre cele păpuşi.
Skulkiu, având la dispoziţie tipuri de obstacole încearcă să-l oprească pe Zane punând pe fiecare coridor exact obstacole. Zane poate distruge obstacolele doar de tip .
Pentru a distruge un obstacol de tipul arma lui Zane are nevoie de unitate de energie, pentru a distruge un obstacol de tipul de unităţi de energie, pentru a distruge un obstacol de tipul de unităţi de energie, iar pentru a distruge un obstacol de tipul de 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 ori mai multă energie decât cea obişnuită, pentru a distruge cel de-al treilea obstacol amplasat pe coridor este nevoie de ori mai multă energie decât cea obişnuită, iar pentru a distruge al patrulea obstacol amplasat pe acelaşi coridor este nevoie de 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 Zane consumă energie doar pentru obstacolele de tip şi .
Raspundeti la urmatoarele cerinte:
- Precizati la cate dintre cele 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 papusi si, dintre acestea, numarul minim de obstacole de tip 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.
Input:
Fişierul ninjago.in conţine pe prima linie un număr natural care poate avea doar valorile , sau , reprezentând cerinţa care va fi rezolvată. Pe a doua linie se gasesc numerele naturale şi , separate printr-un spaţiu. Urmeaza pe 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:
- :
Fisierul ninjago.out contine pe prima linie doar numarul papusilor la care Zane poate ajunge de unul singur. - :
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 papusi, iar pe a doua numarul minim de obstacole de tip ce se afla in total pe o astfel de multime de coridoare. - :
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 .
- Indiferent de sensul de parcurgere al coridorului de către Zane pentru a înlătura obstacolele, energia consumată este aceeaşi.
- .
- Pentru rezolvarea corectă a primei cerinţe se acordă de puncte.
- Pentru rezolvarea corectă a celei de-a doua cerinţe se acordă de puncte.
- Pentru rezolvarea corectă a celei de-a treia cerinţe se acordă de puncte.
- Conform regulamentului OJI, se vor acorda puncte din oficiu.
Exemplu:
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 |