Fişierul intrare/ieşire:valoare.in, valoare.outSursăAlgoritmiada 2018 Runda Finala
AutorAlexandru PetrescuAdăugată dealexpetrescuPetrescu Alexandru alexpetrescu
Timp execuţie pe test0.2 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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.invaloare.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 am lua.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?