Diferente pentru problema/drumetii intre reviziile #5 si #17

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="drumetii") ==
$N$ personaje fantastice vor sa viziteze padurea fermecata. Padurea fermecata are $P$ luminisuri legate intre ele prin cararui de diferite lungimi. Initial personajele sunt in luminisul $1$. Stim ca oricare doua cararui nu se vor intersecta decat intr-un luminis, si ca numarul total de cararui va fi $P-1$. Fiecare dintre cele $N$ personaje urmeaza urmatoarea strategie de vizitare a padurii: Din luminisul in care se afla acum, alege o cararuie pe care nu a parcurs-o in prealabil, si merge pe aceasta. Deasemenea, daca sunt mai multe personaje in acelasi luminis care vor sa mearga mai departe pe aceeasi cararuie, atunci vor merge ca grup - se vor deplasa pe respectiva cararuie cu viteza celui mai incet dintre ele (calul lui Harap-Alb este mai rapid decat Cenusareasa!). Definim energia magica a unui personaj ca fiind egala cu suma din $distanta * viteza$ pentru fiecare cararuie parcursa de acel personaj. Personajele fantastice vor sa gasesti suma maxima a energiilor magice pe care o pot obtine parcurgand padurea. Daca esti vrednic sa rezolvi aceasta problema vei fi rasplatit cu placeri nebanuite...si $100p$.
$N$ personaje fantastice vor sa viziteze padurea fermecata. Padurea fermecata are $P$ luminisuri legate intre ele prin cararui de diferite lungimi. Initial personajele sunt in luminisul $1$. Stim ca oricare doua cararui nu se vor intersecta decat intr-un luminis si ca numarul total de cararui va fi $P-1$. Fiecare dintre cele $N$ personaje urmeaza urmatoarea strategie de vizitare a padurii: Din luminisul in care se afla acum, alege o cararuie pe care nu a parcurs-o in prealabil, si merge pe aceasta. Deasemenea, daca sunt mai multe personaje in acelasi luminis care vor sa mearga mai departe pe aceeasi cararuie, atunci vor merge ca grup - se vor deplasa pe respectiva cararuie cu viteza celui mai incet dintre ele (calul lui Harap-Alb este mai rapid decat Cenusareasa!). In cazul in care un personaj ajunge intr-un luminis din care nu poate iesi (nu exista cararui nevizitate), atunci acel personaj se va opri. Vom numi un astel de luminis $luminis terminal$. Stim ca in padure exista **cel mult** $N$ luminisuri terminale. Definim energia magica a padurii ca fiind egala cu suma din $distanta * viteza$ pentru fiecare cararuie (daca o cararuie nu va fi parcursa, aceasta suma va fi $0$). Personajele fantastice vor sa gasesti energia magica maxima ce se poate obtine. Daca esti vrednic sa rezolvi aceasta problema vei fi rasplatit cu placeri nebanuite...si $100p$.
h2. Date de intrare
Fişierul de intrare $drumetii.in$ va contine pe prima linia numarul $N$ reprezentand numarul de personaje fantastice. Pe a doua linie din input se vor gasi $N$ numere $V{~1~},V{~2~}...V{~N~}$ reprezentand vitezele de deplasare ale celor $N$ personaje. A treia linie din input va contine numerul $P$ reprezentand numarul de luminisuri. Pe fiecare dintre liniile de la $4$ la $4+P-2$ se va gasi cate o pereche de numere $X,Y,L$ reprezentand faptul ca exista o carare de la $X$ la $Y$ de lungime $L$.
Fişierul de intrare $drumetii.in$ va contine pe prima linia numarul $N$ reprezentand numarul de personaje fantastice. Pe a doua linie din input se vor gasi $N$ numere $V{~1~},V{~2~}...V{~N~}$ reprezentand vitezele de deplasare ale celor $N$ personaje. Pe a treia linie din input se va afla numarul $P$. Pe fiecare dintre liniile de la $4$ la $4+P-2$ se va gasi cate o pereche de numere $X,Y,L$ cu semnificatia ca exista o cararuie de la $X$ la $Y$ de lungime $L$.
h2. Date de ieşire
În fişierul de ieşire $drumetii.out$ trebuie sa afisati energia magica maxima ce poate fi obtinuta de cele $N$ personaje.
În fişierul de ieşire $drumetii.out$ trebuie sa afisati energia magica maxima ce poate fi obtinuta.
h2. Restricţii
* $1 ≤ N ≤ 15$
* $1 ≤ P ≤ 1000$
* $1 ≤ L ≤ 1000$
* $2 ≤ N ≤ 16$
* $1 ≤ P ≤ 500$
* $1 ≤ L ≤ 100 000$
* $1 ≤ V{~i~} ≤ 1 000$
* Se garanteaza ca se poate ajunge din nodul $1$ in orice alt nod al padurii.
* O muchie poate fi parcursa in ambele sensuri.
* Un personaj nu are voie sa astepte intre-un poiana. Cu alte cuvinte, cazul in care doua personaje sunt in acelasi nod si aleg ambele sa mearga pe aceeasi cararuie, primul personaj merge iar al doilea astepta si merge dupa acesta este invalid.
* Odata ce un personaj sau grup de personaje nu se mai poate deplasa pe o cararuie nevizitata, acest personaj sau grup se va opri.
h2. Exemplu
table(example). |_. drumetii.in |_. drumetii.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 3
3 4 9
3
1 2 10
1 3 10
| 120
|
| 4
81 372 461 987
4
1 2 64270
1 3 56978
3 4 28202
| 89278530
|
h3. Explicaţie
...
In primul exemplu, personajele $1$ si $2$ vor calatori impreuna spre poiana $2$, iar personajul al treilea va calatori singur spre poiana $3$. Primele doua personaje vor parcurge muchia $(1,2)$ cu viteza 3, iar personajul $3$ va parcurge muchia $(1,3)$ cu viteza $9$. Costul total va fi $3*10+9*10=120$.
== include(page="template/taskfooter" task_id="drumetii") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
8840