| Fişierul intrare/ieşire: | galeti.in, galeti.out | Sursă | InfoOltenia 2018 - Clasa a 9-a |
| Autor | Marius Ciurez | Adăugată de |  Info-Oltenia 2018 •infooltenia |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Găleti
Dorel are N găleţi numerotate de la 1 la N. Găleata i are capacitatea Ci (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 Pi se umple, excesul se varsă în găleata Pi+1. Excesul din găleata PN 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ă XQ 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ă XR turnată pe rând în găleţi (în ordinea 1, 2, … N ) să fie minimă.
Cerinţă
Ajutaţi-l pe Dorel să resolve problema descrisă mai sus.
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 Q1, Q2, … QN separate printr-un spaţiu ce descriu ordinea iniţială de exces Q.
A 3-a linie conţine N numere C1, C2, … CN separate printr-un spaţiu ce descriu capacităţile găleţilor.
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 R1, R2, … RN ce descriu ordinea de exces R pentru care se obţine XR minim.
Pe a 3-a linie afişaţi XR cu semnificaţia din enunţ.
Restricţii
- 1 ≤ N ≤ 105
- 1 ≤ Ci ≤ 109 pentru orice i de la 1 la N
- pentru 30% din punctaj: 1 ≤ N ≤ 600, 1 ≤ Ci ≤ 10000 pentru orice i de la 1 la N
- pentru 50% din punctaj 1 ≤ N ≤ 1000
- Atât XQ cât şi XR trebuie să fie numere naturale.
- Orice ordine de acces R pentru care se obţine XR minim este acceptată.
Exemplu
| galeti.in | galeti.out |
|---|---|
| 4 1 2 3 4 4 2 3 2 | 4 2 3 4 1 3 |
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.
