Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | valoare.in, valoare.out | Sursă | Algoritmiada 2018 Runda Finala |
| Autor | Alexandru Petrescu | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Valoare
La fiecare concurs international la care participa, Marcel colecteaza cateva monezi din tara in care se duce. Pana acum a facut rost de N monezi, a i-a avand valoarea Vi. Astazi, fiindca are o ocazie foarte importanta, dar si secreta, s-a hotarat sa foloseasca cateva monezi pentru a cumpara un obiect cu valoare necunoscuta. Din acest motiv, vrea sa afle valoarea maxima U pentru care, luand K monede, poate garanta ca poate plati orice valoare naturala nenula mai mica sau egala cu U folosind doar monezi din cele K alese. El vrea sa il afle pe U pentru fiecare K de la 1 la N.
Date de intrare
Fişierul de intrare valoare.in contine, pe prima linie, numarul natural N. Pe urmatoarea linie se afla N numere naturale Vi.
Date de ieşire
În fişierul de ieşire valoare.out se afla N numere naturale, fiecare numar pe cate o linie, al i-ulea reprezentand numarul natural U considerandu-l pe K egal cu i.
Restricţii
- Desi Marcel a participat la foarte multe concursuri internationale, in aceasta problema vom limita N la maxim 50.000
- Cu alte cuvinte, 1 ≤ N ≤ 50.000
- 1 ≤ Vi ≤ 1.000.000.000
- Pentru 40% din puncte, N ≤ 500
Exemplu
| valoare.in | valoare.out |
|---|---|
| 4 1 2 3 4 | 1 3 7 10 |
| 3 1 2 5 | 1 3 3 |
| 2 2 2 | 0 0 |
Explicaţie
In primul exemplu, luand
- o moneda, o vom lua pe cea de valoare 1 pentru a garanta ca putem plati un obiect de valoare 1
- doua monezi, le vom lua pe cele de valori 1 si 2 pentru a garanta ca putem plati un obiect de valoare intre 1 si 3
- trei monezi, le vom lua pe cele de valori 1, 2 si 4 pentru a garanta ca putem plati un obiect de valoare intre 1 si 7. De exemplu, pe 5 il putem scrie ca 1 + 4, folosind, iata, doar monezi din cele trei alese. Observatie: Daca am fi luat moneda 3 in loc de moneda 4, nu am fi putut plati suma 7
- toate cele patru monezi, garantam ca putem plati un obiect de valoare intre 1 si 10. De exemplu, pe 7 il putem scrie ca 1 + 2 + 4 sau ca 3 + 4
In al doilea exemplu, luand
- o moneda, o vom lua pe cea de valoare 1 pentru a garanta ca putem plati un obiect de valoare 1
- doua monei, le vom lua pe cele de valori 1 si 2 pentru a garanta ca putem plati un obiect de valoare intre 1 si 3
- toate cele trei monezi, garantam ca putem plati un obiect de valoare intre 1 si 3, dar, neputand plati un obiect de valoare egala cu 4, nu putem garanta ca putem plati un obiect de valoare intre 1 si o valoare mai mare sau egala cu 4
In al treilea exemplu, nu putem plati un obiect de valoare egala cu 1, prin urmare U = 0, oricate monede as lua.
