Diferente pentru problema/metrouri intre reviziile #7 si #3

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="metrouri") ==
În Ţara lui Stuf-Vodă există o linie de metrou cu $N$ staţii, numerotate cu $1, 2, …, N$ plasate pe o dreaptă la distanţe egale, de la stânga la dreapta. MetroStuf dispune de $K$ metrouri care circulă pe această linie. Acestea pleacă din staţia $1$ către staţia $N$. Timpul de deplasare a unui metrou între două staţii consecutive este de un minut.
În Ţara lui Stuf-Vodă există o linie de metrou cu N staţii, numerotate cu 1, 2, …, n, plasate pe o dreaptă la distanţe egale, de la stânga la dreapta. MetroStuf dispune de K metrouri care circulă pe această linie. Acestea pleacă din staţia 1 către staţia N. Timpul de deplasare a unui metrou între două staţii consecutive este de un minut.
Stuf-Vodă vrea însă să îşi ţină oameni cât mai fericiţi, aşa că vrea să găsească un scenariu optim de plecare a metrourilor din staţia $1$ către staţia $N$, astfel încât oameni să aştepte cât mai puţin. Se dau $M$ perechi de forma $(S{~i~}, T{~i~})$ cu semnificaţia: în staţia $S{~i~}$ la minutul $T{~i~}$ ajunge o persoană. Se defineşte costul unui metrou, ca fiind timpul cel mai mare de aşteptare al unei persoane, care s-a urcat în metroul respectiv. Stuf-Vodă şi-a dat seama că oamenii din ţara lui sunt cu atât mai fericiţi cu cât suma costurilor metrourilor este mai mică. O persoană urcă întotdeauna în primul metrou care soseşte în staţie.
Stuf-Vodă vrea însă să îşi ţină oameni cât mai fericiţi, aşa că vrea să găsească un scenariu optim de plecare a metrourilor din staţia 1 către staţia N, astfel încât oameni să aştepte cât mai puţin. Se dau M perechi de forma (S¬i, Ti) cu semnificaţia: în staţia Si la minutul Ti ajunge o persoană. Se defineşte costul unui metrou, ca fiind timpul cel mai mare de aşteptare al unei persoane, care s-a urcat în metroul respectiv. Stuf-Vodă şi-a dat seama că oamenii din ţara lui sunt cu atât mai fericiţi cu cât suma costurilor metrourilor este mai mică. O persoană urcă întotdeauna în primul metrou care soseşte în staţie.
Dându-se $N$, $M$, $K$ şi $M$ perechi de forma $(S{~i~}, T{~i~})$ cu semnificaţia de mai sus, se cere să se calculeze momentele de timp la care trebuie să plece metrourile din staţia $1$ către staţia $N$, astfel încât suma costurilor metrourilor să fie minimă.
Dându-se N, M, K şi M perechi de forma (Si, Ti) cu semnificaţia de mai sus, se cere să se calculeze momentele de timp la care trebuie să plece metrourile din staţia 1 către staţia N, astfel încât suma costurilor metrourilor să fie minimă.
h2. Date de intrare
Pe prima linie a fişierului $metrouri.in$ se vor găsi trei numere: $N$, $M$ şi $K$ separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe următoarele $M$ linii se vor găsi câte două numere, $S{~i~}$ şi $T{~i~}$, cu semnificaţia că la momentul de timp $T{~i~}$ în staţia $S{~i~}$ ajunge o persoană.
Pe prima linie a fişierului metrouri.in se vor găsi trei numere: N, M şi K separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii se vor găsi câte două numere, Si şi Ti, cu semnificaţia că la momentul de timp Ti în staţia Si ajunge o persoană.
h2. Date de ieşire
Fisierului de ieşire $metrouri.out$ va conţine un singur număr şi anume suma costurilor celor $K$ metrouri.
Fisierului de ieşire metrouri.out va conţine un singur număr şi anume suma costurilor celor K metrouri.
h2. Restricţii
* $1 ≤ N, M, K ≤ 100 000$
* Metrourile nu merg decât într-un singur sens şi odată ajunse în staţia $N$ rămân acolo până la sfârşitul zilei
* Pentru $30%$ din teste $N ≤ 200, M ≤ 1000, K ≤ 100$
* Pentru $60%$ din teste $N ≤ 10 000, M ≤ 20 000, K ≤ 300$
* $1 ≤ S{~i~} ≤ N$
* $0 ≤ T{~i~} ≤ 1 000 000$
* MetroStuf se deschide la minutul $0$ (persoanele nu pot ajunge mai devreme de aceasta ora în staţii), însă metrourile pot pleca din staţia $1$ înainte de acest moment.
* În oricare metrou pot să urce oricâte persoane.
* 1 ≤ N, M, K ≤ 100 000
* Metrourile nu merg decât într-un singur sens şi odată ajunse în staţia N rămân acolo până la sfârşitul zilei
* Pentru 30 % din teste N <= 200, M <= 1000, K <= 100
* Pentru 60 % din teste N <= 10 000, M <= 20 000, K <= 300
* 1 ≤ Si ≤ N
* 0 ≤ Ti ≤ 1 000 000
* MetroStuf se deschide la minutul 0 (persoanele nu pot ajunge mai devreme de aceasta ora în staţii), însă metrourile pot pleca din staţia 1 înainte de acest moment.
	În oricare metrou pot să urce oricâte persoane.
 
h2. Exemplu
h3. Explicaţie
Metroul $1$ pleacă din staţia $1$ la minutul $2$, metroul $2$ pleacă la minutul $6$, iar metroul $3$ la minutul $8$. Costul metroului $1$ este $1$, costului metroului $2$ este $1$, iar costul metroului $3$ este $0$. Suma costurilor metrourilor este $2$.
Metroul 1 pleacă din staţia 1 la minutul 2, metroul 2 pleacă la minutul 6, iar metroul 3 la minutul 8. Costul metroului 1 este 1, costului metroului 2 este 1, iar costul metroului 3 este 0. Suma costurilor metrourilor este 2.
== include(page="template/taskfooter" task_id="metrouri") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

5671