Fişierul intrare/ieşire: | banuti.in, banuti.out | Sursă | Autumn Warmup 2007, Runda 1 |
Autor | Paul-Dan Baltescu | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/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.in | banuti.out |
---|---|
2 3 5 | 7 |
2 3 6 | -1 |