| Fişierul intrare/ieşire: | economie.in, economie.out | Sursă | preONI 2008 Runda 1 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Economie
Vultur este un veritabil colectionar de monezi si momentan colectia lui numara N monezi cu valori numere naturale intre 1 si 50 000. El vrea sa-si cumpere insa un acvariu nou pentru pestii sai si de aceea se gandeste sa cedeze la banca o parte din monezi. Fiind un tip sensibil, el ar dori totusi ca folosind monezile care i-au ramas sa poata fi posibil sa obtina orice valoare a monezilor pe care le-a cedat la banca. Alegeti pentru Vultur un subset minim de monezi din cele N astfel incat orice valoare din cele N sa poata fi scrisa ca o suma de valori ale monezilor din subsetul ales (valoarea unei monezi din subsetul ales poate fi adunata de mai multe ori).
Date de intrare
Pe prima linie a fisierului economie.in se afla numarul N avand semnificatia din enunt, iar pe urmatoarele N linii se afla valoarea monezilor detinute de Vultur.
Date de iesire
Pe prima linie a fisierului economie.out se afla numarul MIN, reprezentand numarul minim de monezi din subsetul ales. Pe urmatoarele MIN linii se afla valorile monezilor alese. Daca exista mai multe solutii, se poate afisa oricare.
Restrictii
- 1 ≤ N ≤ 1000
- 1 ≤ Vi ≤ 50 000
Exemplu
| economie.in | economie.out |
|---|---|
| 3 1 3 5 | 1 1 |
Explicatie
Daca alegem moneda cu valoarea 1 atunci monezile cu valorile 3 si 5 pot fi obtinute folosind 3 monezi cu valoarea 1, respectiv 5 monezi cu valoarea 1.
