Diferente pentru problema/foametea intre reviziile #52 si #82

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="foametea") ==
$Fomistul$ nostru preferat locuieşte într-o ţară cu $N$ oraşe conectate prin $M$ drumuri unidirecţionale. Fiecare drum din ţara sa are o anumită lungime, **L{~i~}** şi o anumită dificultate **C{~i~}**, egală cu numărul de sarmale pe care $Fomistul$ trebuie să le consume **la începerea** deplasării pe respectivul drum pentru a-l putea parcurge cu succes. Mai ştim că acesta poate căra cu sine maxim **$K$** sarmale şi, din fericire, în fiecare oraş cunoaşte câte o mătuşă care îi oferă maxim **s{~i~}** sarmale (în limita valorii $K$) la fiecare vizită pe care i-o face. Luând în considerare că timpul necesar parcurgerii unui drum de lungime $l$ este egal cu $l * (s^2^ + 1)$, unde $s$ este numărul de sarmale pe care le cară, ajutaţi-l pe $Fomist$ să afle cât de repede poate ajunge la cina festivă din oraşul $N$, plecând din oraşul $1$.
Fomistul nostru preferat locuieşte într-o ţară cu **$N$** oraşe conectate prin **$M$** drumuri unidirecţionale. Fiecare drum din ţara sa are o anumită lungime, **L{~i~}** şi o anumită dificultate **C{~i~}**, egală cu numărul de sarmale pe care Fomistul trebuie să le consume **la începerea** deplasării pe respectivul drum pentru a-l putea parcurge cu succes. Acesta poate căra în traistă maxim **$K$** sarmale şi, din fericire, în fiecare oraş cunoaşte câte o mătuşă care îi oferă maxim **s{~i~}** sarmale la fiecare vizită a sa în oraşul cu pricina. Este bine cunoscut faptul că timpul necesar parcurgerii unui drum de lungime **$L$** este egal cu **$L * (S^2^ + 1)$**, unde **$S$** este numărul de sarmale care îi rămân în traistă după ce consumă cantitatea necesară parcurgerii drumului respectiv. Fomistul, pentru că îi este prea foame pentru a se descurca singur, vă roagă să îi spuneţi cât de repede poate ajunge la cina festivă din oraşul **$N$** (unde se vor servi sarmale), plecând din oraşul **$1$**.
h2. Date de intrare
Fişierul de intrare $foametea.in$ va conţine pe prima linie numerele $N$ (numărul de oraşe), $M$ (numărul de drumuri), $K$ (capacitatea stomacului $Fomistului$). Următoarea linie va conţine numerele $s{~1~}, s{~2~}, ..., s{~N~}$ (numărul maxim de sarmale oferit de mătuşă în fiecare dintre cele $N$ oraşe). Următoarele $M$ linii vor conţine fiecare câte 4 întregi, $A$, $B$, $L$, $C$ semnificând că există un drum ce pleacă din oraşul $A$, ajunge în oraşul $B$, are lungimea $L$ şi poate fi parcurs de $Fomist$ consumând $C$ sarmale din rezerva sa.
Fişierul de intrare $foametea.in$ va conţine pe prima linie numerele $N$ (numărul de oraşe), $M$ (numărul de drumuri), $K$ (capacitatea traistei Fomistului).
Următoarea linie va conţine numerele $s{~1~}, s{~2~}, ..., s{~N~}$ (numărul maxim de sarmale oferit de fiecare dintre cele $N$ mătuşi).
Următoarele $M$ linii vor conţine fiecare câte 4 întregi, $A$, $B$, $L$, $C$ semnificând că există un drum ce pleacă din oraşul $A$, ajunge în oraşul $B$, are lungimea $L$ şi poate fi parcurs de $Fomist$ consumând $C$ sarmale.
h2. Date de ieşire
Fişierul de ieşire $foametea.out$ va conţine o singură linie cu răspunsul la întrebarea $Fomistului$, iar în cazul în care acesta nu poate ajunge la cina festivă afişaţi mesajul "Fomistul moare de foame" (fără ghilimele).
Fişierul de ieşire $foametea.out$ va conţine o singură linie cu răspunsul la întrebarea $Fomistului$.
**În cazul în care acesta nu poate ajunge la cina festivă afişaţi mesajul "Fomistul moare de foame" (fără ghilimele).**
h2. Restricţii
* $1 ≤ N ≤ 5000$
* $1 ≤ M ≤ 25000$
* $0 ≤ K ≤ 30$
* $0 ≤ s{~i~} ≤ K$
* $1 ≤ A, B ≤ N$
* $0 ≤ L ≤ 10000$
* $0 ≤ C ≤ K$
h2. Precizări
* Pentru teste în valoare de 20 puncte se garantează că $L$ = 1 şi că $C$ = 0 pentru toate drumurile.
* Pentru teste în valoare de 20 puncte se garantează că $C$ = 0 pentru toate drumurile şi că nu există cicluri (graful rezultat este un DAG).
* Pentru teste în valoare de 30 de puncte se garantează că $C$ = 0 pentru toate drumurile.
* În fiecare oraş $Fomistul$ poate alege să mănânce oricâte sarmale între 0 şi s{~i~} cu condiţia să nu depăşască limita de $K$.
* $Fomistul$ are iniţial $0$ sarmale în stomac. Cât consideră că se cuvine din oraşul $1$, atâta va şi consuma.
* Pentru alte teste în valoare de 20 puncte se garantează că $C$ = 0 pentru toate drumurile şi că nu există cicluri (graful rezultat este un DAG).
* Pentru alte teste în valoare de 30 de puncte se garantează că $C$ = 0 pentru toate drumurile.
* Pentru alte teste în valoare de 30 de puncte se aplică restricţiile iniţiale.
* **În fiecare oraş i, Fomistul poate alege să introducă în traistă oricâte sarmale între 0 şi s{~i~}, cu condiţia ca numărul total să nu depăşască limita de $K$.**
* **Fomistul are iniţial $0$ sarmale în traistă. Va lua cât consideră de cuviinţă de la mătuşa din primul oraş.**
h2. Exemplu
5 4 0 2
3 5 8 2
1 3 7 2
| 159
| 43
|
| 5 3 5
2 3 1 0 1
1 4 5 4
| Fomistul moare de foame
|
|6 10 24
24 11 15 8 16 23
2 6 2 19
1 3 5 0
5 4 3 12
2 5 4 12
4 2 5 9
3 5 3 21
1 2 5 15
3 2 3 23
3 4 4 20
6 1 3 14
|327
|
h3. Explicaţie
1. $Fomistul$ mănâncă 4 sarmale în primul oraş, ajunge în oraşul $3$ în 7 * (1 + 4^2^) = 119, iar apoi în oraşul $5$ în 119 + 8 * (1 + 2^2^) = 159.
2. $Fomistul$ nu poate ajunge în oraşul $5$.
ex. 1:
Fomistul îşi încarcă în traistă 4 sarmale din primul oraş.
Se pregăteşte de drumul (1, 3) mâncând 2 dintre sarmalele din traistă şi ajunge în oraşul 3 în $7 * (1 + 2^2^) = 35$ unităţi de timp.
În oraşul 3 nu i se oferă nicio sarma.
Se pregăteşte de drumul (3, 5) mâncând 2 sarmale şi ajunge în oraşul 5 după încă $8 * (1 + 0^2^) = 8$ momente de timp.
Răspunsul final este, aşadar $35 + 8 = 43$.
 
ex. 2:
Fomistul nu poate ajunge în oraşul 5.
== include(page="template/taskfooter" task_id="foametea") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.