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

Poveste si cerinta...

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 |

| 3
  1
  3
  5
| 1
  1

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

|
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