Fişierul intrare/ieşire:banuti.in, banuti.outSursăAutumn Warmup 2007, Runda 1
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Banuti

Taranul Victor are la dispozitie N tipuri de bancnote, fiecare in numar nelimitat. El este curios care este suma minima Smin, astfel incat orice suma mai mare ca Smin sa poata fi platita din bancnotele pe care le are la dispozitie.

Cerinta

Cunoscand valorile celor N tipuri de bancnote, aflati Smin.

Date de intrare

Pe prima linie a fisierului banuti.in se afla numarul N. Pe urmatoarea linie se afla N numere Vi care reprezinta valoarea fiecarui tip de bancnota.

Date de iesire

Pe prima linie a fisierului banuti.out se gaseste numarul Smin sau -1, daca nu exista solutie.

Restrictii

  • 2 ≤ N ≤ 50 000
  • 1 ≤ Vi ≤ 10 000 000
  • Se garanteaza ca exista cel putin o bancnota cu valoarea ≤ 5000.
  • Smin < 1 000 000 000
  • Pentru 20% din teste N ≤ 50, Smin ≤ 100 000 si valoarea minima a cel putin unei bancnote ≤ 200.
  • Pentru 50% din teste N ≤ 1000.

Exemplu

banuti.inbanuti.out
2
3 5
7
2
3 6
-1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content