Diferente pentru problema/metrou intre reviziile #4 si #14

Nu exista diferente intre titluri.

Diferente intre continut:

Traim intr-o lume ciudata, in care statiile de metrou sunt si mai ciudate. Iar pe cat de ciudat, pe atat de aglomerat. Fiind multa imbulzeala, avem nevoie de ajutorul vostru pentru a face ordine prin multime.
Un metrou are $N$ usi. In momentul in care ajunge metroul in statie, stim ca la fiecare usa $i$, plasata in pozitia $x[i]$ a axei $Ox$ ({$1 ≤ i ≤ N$}) sunt $a[i]$ oameni care doresc sa intre in metrou si $b[i]$ oameni care doresc sa iasa din metrou. Singura problema este ca, din cauza noilor reguli, printr-o usa se poate fie intra, fie iesi, una dintre aceste actiuni fiind intotdeauna interzisa. Niciunul dintre oamenii care fie vor sa intre in metrou, fie vor sa iasa nu stiu daca usa la care sunt amplasati este de deschidere sau de inchidere. Asa ca, daca in caz usa $i$ din pozitia $x[i]$ ({$1 ≤ i ≤ N$}) este de intrare, cei $b[i]$ oameni amplasati la aceasta usa vor fi nevoiti sa se mute la cea mai apropiata usa de iesire pentru a cobori la aceasta statie. Se mai stie ca efortul unui om de a se deplasa de la usa $i$ la usa $j$ este $|x[i] - x[j]|$ ({$1 ≤ i, j ≤ N$}).
Un metrou are $N$ usi. In momentul in care ajunge metroul in statie, stim ca la fiecare usa $i$, plasata in pozitia $x[i]$ a axei $Ox$ ({$1 ≤ i ≤ N$}) sunt $a[i]$ oameni care doresc sa intre in metrou si $b[i]$ oameni care doresc sa iasa din metrou. Singura problema este ca, din cauza noilor reguli, printr-o usa se poate fie intra, fie iesi, una dintre aceste actiuni fiind intotdeauna interzisa. Niciunul dintre oamenii care fie vor sa intre in metrou, fie vor sa iasa nu stiu daca usa la care sunt amplasati este de deschidere sau de inchidere. Asa ca, de exemplum daca usa $i$ din pozitia $x[i]$ ({$1 ≤ i ≤ N$}) este de intrare, cei $b[i]$ oameni amplasati la aceasta usa vor fi nevoiti sa se mute la cea mai apropiata usa de iesire pentru a cobori la aceasta statie. Se mai stie ca efortul unui om de a se deplasa de la usa $i$ la usa $j$ este $|x[i] - x[j]|$ ({$1 ≤ i, j ≤ N$}).
Avand la dispozitie numarul $N$ de usi, pozitia acestora pe axa $Ox$ si numarul de oameni care doresc sa intre si sa iasa din metrou la fiecare usa in parte, sa se gaseasca o intrebuintare a usilor de tipul $0$ sau $1$ ({$0$} pentru usa de intrare, $1$ pentru usa de iesire ), astfel incat efortul total depus de oameni pentru deplasare in urma intrarii si iesirii din metrou sa fie minim. Se cere efortul minim depus de oameni.
Avand la dispozitie numarul $N$ de usi, pozitia acestora pe axa $Ox$ si numarul de oameni care doresc sa intre si sa iasa din metrou la fiecare usa in parte, sa se determine efortul minim depus de oameni pentru deplasare in urma intrarii si iesirii din metrou.
h2. Date de intrare
h2. Restricţii
* $1 ≤ 2000 ≤ N$
* $1 ≤ x[i] ≤ 100.000$
* $1 ≤ a[i], b[i] ≤ 1000
* $Elementele sirului x sunt in ordine crescatoare.
* $2 ≤ N ≤ 2000$
* $0 ≤ x[i] ≤ 100.000$
* $1 ≤ a[i], b[i] ≤ 1000$
* $Elementele sirului x sunt in ordine crescatoare.$
* $Se garanteaza ca raspunsul intra in 32 de biti cu semn.$
h2. Exemplu
1 3 4 5
1 2 3 5
2 3 3 1
| This is another
  text written on
  multiple lines.
| 9
|
h3. Explicaţie
...
Prima si a treia usa for fi de iesire, iar a doua si a patra usa de intrare.
Efortul depus de oamenii care vor sa intre este $1*2 + 2*0 + 3*1 + 5*0 = 5$
Efortul depus de oamenii care vor sa iasa este $2*0 + 3*1 + 3*0 + 1*1 = 4$
Efortul total este $4 + 5 = 9$
== include(page="template/taskfooter" task_id="metrou") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
8425