Diferente pentru problema/ninjago intre reviziile #7 si #6

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="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ă.
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. Cerinţă:
h2. Cerinta:
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$.
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>.
Răspundeţi la următoarele cerinţe:
Raspundeti la urmatoarele cerinte:
# Precizaţi la câte dintre cele $N$ păpuşi poate ajunge Zane, *fără* a cere ajutorul altor ninja
# 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.
# Precizaţi, în contextul întrebării de mai sus, care este numărul *minim* de unităţi de energie utilizate.
# 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. 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.
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. 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.
* <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.
h2. Restricţii
* *Iniţial Zane se află lângă păpuşa* $1$.
* *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.*
* $1 &le; N, M &le; 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.*
* <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* |_. Explicaţie |
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
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
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
| 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,
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
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)
265 pentru coridorul (4,9)
163 pentru coridorul (6,7)
Pentru coridorul (4,9) obstacolele sunt ECEB,
Deci Zane va consuma 0+3&#42;5+0&#42;25+2&#42;125=265 unităţi de energie |
Deci Zane va consuma 0+3*5+0*25+2*125=265 unităţi de energie |
== include(page="template/taskfooter" task_id="ninjago") ==
== include(page="template/taskfooter" task_id="ninjago") ==
 

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.