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

Diferente intre titluri:

foametea
Foametea

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. $Fomistul$ este pasionat de mersul viguros, dar acesta nu poate face niciun pas fă  fi mâncat o cantitate rezonabilă de sarmale în avans. În fiecare dintre cele $N$ ore, acesta cunoaşte o mătuşă care îi poate oferi maxim $s{~i~}$ sarmale la fiecare vizita a sa în oraşul respectiv. $Fomistul$ nostru nu e spart, aşa că poate depozita maxim $K$ sarmale în stomacul său. Unele drumuri sunt mai greu de parcurs decât altele, fiecare costându-l pe $Fomist$ un număr de sarmale. Tineţi cont şi ca Fomistul se mişcă cu atât mai greu cu cât a mâncat mai multe sarmale (că na, atârnă). În consecinţă, dacă a mâncat suficient pentru a parcurge un drum de lungime $l$, atunci îl va parcurge în $l * (s^2^ + 1)$ unităţi de timp, unde $s$ este numărul de sarmale pe care le are în stomac în momentul începerii deplarii viguroase (pe drumul respectiv). Ajuti-l pe Fomist să afle cât de repede poate ajunge la cina festivă din oraşul $N$, ştiind  pleacă 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ş cunote 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$, $C$, $D$ semnificând că există un drum ce pleacă din oraşul $A$, ajunge în oraşul $B$, are lungimea $C$ şi poate fi parcurs de $Fomist$ dacă consumă $D$ sarmale.
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 ≤ C ≤ 10000$
* $0 ≤ D ≤ K$
* $0 ≤ L ≤ 10000$
* $0 ≤ C ≤ K$
h2. Precizări
* Pentru teste în valoare de 15 puncte se garantează că $C$ = 1 şi că $D$ = 0 pentru toate drumurile.
* Pentru teste în valoare de 15 puncte se garantează că $D$ = 0 pentru toate drumurile şi că nu există cicluri (graful rezultat este un DAG).
* Pentru teste în valoare de 20 de puncte se garantează că $D$ = 0 pentru toate drumurile.
* În fiecare oraş $Fomistul$ poate alege să mănânce oricâte sarmale între 0 şi s{~i~} dacă nu depăşeşte limita de $K$.
* $Fomistul$ are iniţial $0$ sarmale în stomac. Va mânca cât consideră că se cuvine din oraşul $1$.
* Pentru teste în valoare de 20 puncte se garantează că $L$ = 1 şi că $C$ = 0 pentru toate drumurile.
* 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
2 1 5 4
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
...
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.