Diferente pentru problema/galeti intre reviziile #14 si #6

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="galeti") ==
Dorel are $N$ găleţi numerotate de la 1 la $N$. Găleata $i$ are capacitatea $C{~i~}$ (capacităţile sunt numere naturale). O ordine de exces este o permutare $P$ de lungime $N$ ce are următoarea semnificaţie: dacă găleata P{~i~} se umple, excesul se varsă în găleata $P{~i+1~}$. Excesul din găleata $P{~N~}$ nu se varsă în nicio găleată.
Dorel are N găleţi numerotate de la 1 la N, fiecare găleata are o capacitate C în litri. Dorel are un furtun legat la o surinfinită de apă şi doreşte  umple toate găleţile. Dorel însă, vrea să toarne accei cantitate de apă în toate găleţile şi işi doreşte umple toate găleţile turnând aceeaşi cantitate minimă în toate.
Iniţial, găleţile lui Dorel au ordinea de exces $Q$. Pentru aceasta, el vrea să afle cantitatea minimă de a$X{~Q~}$ pe careo toarne pe rând în găleţi (acesta toarnă a în găleţi în ordinea $1, 2,  N$ ) aşa încât la final găleţile să fie pline cu a.
Pentru a face acest lucru, el a stabilit o ordine de exces, ordinea de exces înseamna că dacă o găleata s-a umplut şi înca mai este apă de turnat în ea, restul de apă va fi turnată în găleata următoare specificată în ordine. De exemplu, dacă ordinea este 1 -> 3 -> 2 -> 4, asta înseamnă  dacă găleata 1 se umple, restul se toarnă în găleata 3, dacă şi găleata 3 se umple, restul se toarna în găleata 2, dacă şi găleata 2 se umple, restul se toarna în leata 4, excesul din găleata 4 este folosit pentru a uda florile, adică nu ne intereseaza.
Apoi, Dorel vrea să găsească o ordine de exces $R$, pentru care cantitatea de apă $X{~R~}$ turna pe rând în găleţi (în ordinea $1, 2,  N$ ) să fie minimă.
În afară de ordinea de exces, Dorel va turna apă în găleţi în ordinea 1, 2, ... N
h2. Cerinţă
Ajutaţi-l pe Dorel să resolve problema descrisă mai sus.
Stiind N, numărul de găleţi, capacitatea fiecarei găleţi şi ordinea de exces a găleţilor, aflaţi cantitatea minima de apă, în litri, necesară pentru a fi umplute toate găleţile. Determinaţi o ordine de vărsare mai buna astfel încât să minimalizaţi cantitatea minima de apă necesară pentru a umple toate găleţile şi afisaţi noua cantitate. Se garanteaza ca nu vor exista cicluri în ordinea de exces.
h2. Date de intrare
Prima linie a fişierului $galeti.în$ va conţine numărul $N$ cu semnificaţia din enunţ.
A 2-a linie conţine $N$ numere $Q{~1~}, Q{~2~}, … Q{~N~}$ separate printr-un spaţiu ce descriu ordinea iniţială de exces $Q$.
A 3-a linie conţine $N$ numere $C{~1~}, C{~2~}, … C{~N~}$ separate printr-un spaţiu ce descriu capacităţile gălilor.
Prima linie a fişierului $galeti.in$ va conţine numărul N cu semnificaţia din enunţ.
A 2-a linie conţine N numere ce reprezinta ordinea de exces.
A 3-a linie conţine N numere, al i-lea număr reprezinta capacitatea pentru găleata cu numărul i.
h2. Date de ieşire
În fişierul $galeti.out$ afişaţi pe prima linie cantitatea de apă XQ cu semnificaţia din enunţ.
Pe a 2-a linie afişaţi $N$ numere $R{~1~}, R{~2~}, … R{~N~}$ ce descriu ordinea de exces R pentru care se obţine XR minim.
Pe a 3-a linie afişaţi $X{~R~}$ cu semnificaţia din enunţ.
În fişierul $galeti.out$ afişaţi pe prima linie cantitatea necesară pentru a umple toate găleţile.
Pe a 2-a linie afişaţi noua ordine de exces, dacă există mai multe, afişaţi pe oricare dintre ele.
Pe a 3-a linie afişaţi noua cantitate minimă necesară pentru a umple toate găleţile.
h2. Restricţii
* $1 ≤ N ≤ 10^5^$
* $1 ≤ C{~i~} ≤ 10^9^$ pentru orice $i$ de la $1$ la $N$
* pentru $30%$ din punctaj: $1 ≤ N ≤ 600$, $1 ≤ C{~i~} ≤ 10000$ pentru orice $i$ de la $1$ la $N$
* pentru $50%$ din punctaj $1 ≤ N ≤ 1000$
* Atât $X{~Q~}$ cât şi $X{~R~}$ trebuie să fie numere naturale.
* Orice ordine de acces $R$ pentru care se obţine $X{~R~}$ minim este acceptată.
* 1 ≤ N ≤ 10 ^5^
* 1 ≤ C ≤ 10 ^9^
* pentru 30% din punctaj: 1 ≤ N ≤ 600, 1 ≤ C ≤ 10000
* pentru 50% din punctaj 1 ≤ N ≤ 1000
h2. Exemplu
table(example). |_. galeti.in |_. galeti.out |
| 4
1 2 3 4
4 2 3 2
4 2 4 2
| 4
2 3 4 1
3
h3. Explicaţie
Cu ordinea iniţiala de exces, valoarea minimă cerută este 4, iar cantităţile din găleţi după fiecare turnare sunt următoarele:
4 0 0 0
4 2 2 0
4 2 3 2
4 2 3 2
 
Cu noua ordine de exces valoarea minimă cerută este 3, iar cantităţile din găleţi după fiecare turnare sunt următoarele:
3 0 0 0
3 2 1 0
3 2 3 1
4 2 3 2
Nu există o ordine de acces prin care să se umple găleţile turnând pe rând mai puţin de 3 litri.
Cu ordinea iniţiala de exces, valoarea minimă cerută este 4. Cu noua ordine de exces, excesul de 1 litru din găleata 2 se va turna în găleata 3 şi se va umble, excesul de 1 litru din găleata 4 se va turna în găleata 1 şi se va umple, raspuns final 3. O altă nouă ordine de exces validă putea fi: 2 4 1 3
== include(page="template/taskfooter" task_id="galeti") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.