Diferente pentru problema/drumetii intre reviziile #10 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!). 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$.
$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 $P$ 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+N-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$.
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
h2. Restricţii
* $2 ≤ N ≤ 20$
* $2 ≤ N ≤ 16$
* $1 ≤ P ≤ 500$
* $1 ≤ L ≤ 100 000$
* $1 ≤ V{~i~} ≤ 1 000$
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