Fişierul intrare/ieşire:economie.in, economie.outSursăpreONI 2008 Runda 1
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.1 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/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.ineconomie.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content