economie

Economie

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

Poveste si cerinta...

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.

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

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1000$
* $1 ≤ V{~i~} ≤ 50 000$

h2. Exemplu
table(example). |_. economie.in |_. economie.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
  1
  3
  5
| 1
  1

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

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

2405