economie

Economie

== include(page="template/taskheader" task_id="economie") ==

Vultur este un veritabil colectionar de monezi si momentan colectia lui numara $N$ monezi cu valori numerele 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 poate fi posibil sa obtina orice valoare a monezilor 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 (o moneda din subsetul ales poate fi adunata de mai multe ori).

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).

h2. 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 initial.

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.

h2. Date de iesire

Pe prima linie a fisierului $economie.out$ se afla numar $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.

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.

h2. Restrictii

h3. Explicatie

Daca alegem moneda cu valoarea $1$ atunci monezile cu valorile $3$ si $5$ pot fi obtinute folosind $3$ monezi cu valoare $1$, respectiv $5$ monezi cu valoarea $1$.

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$.

== include(page="template/taskfooter" task_id="economie") ==

2405