Diferente pentru problema/foametea intre reviziile #71 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. 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 pe care le cară în momentul respectiv în traistă. 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$**.
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 îimâ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
h2. Date de ieşire
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).
**Î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 traistă. Va lua cât consideră de cuviinţă de la mătuşa din primul oraş.
* 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
3 2 3 23
3 4 4 20
6 1 3 14
|3374
|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.