== include(page="template/taskheader" task_id="galeti") ==
Poveste şi cerinţă...
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ă.
Iniţial, găleţile lui Dorel au ordinea de exces $Q$. Pentru aceasta, el vrea să afle cantitatea minimă de apă $X{~Q~}$ pe care să o toarne pe rând în găleţi (acesta toarnă apă în găleţi în ordinea $1, 2, … N$ ) aşa încât la final găleţile să fie pline cu apă.
Apoi, Dorel vrea să găsească o ordine de exces $R$, pentru care cantitatea de apă $X{~R~}$ turnată pe rând în găleţi (în ordinea $1, 2, … N$ ) să fie minimă.
h2. Cerinţă
Ajutaţi-l pe Dorel să resolve problema descrisă mai sus.
h2. Date de intrare
Fişierul de intrare $galeti.in$ ...
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ăleţilor.
h2. Date de ieşire
În fişierul de ieşire $galeti.out$ ...
Î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ţ.
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ă.
h2. Exemplu
table(example). |_. galeti.in |_. galeti.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
1 2 3 4
4 2 3 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.
== include(page="template/taskfooter" task_id="galeti") ==
== include(page="template/taskfooter" task_id="galeti") ==
