colectie

Colectie

== include(page="template/taskheader" task_id="colectie") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| colectie.in | colectie.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="colectie") ==

==Include(page="template/taskheader" task_id="colectie")==
==Include(page="template/raw")==
 
Colectie
 
Tudor s-a gandit ca, deja, colectia lui de CD-uri si DVD-uri a devenit destul de impresionanta si, pentru a organiza mai usor discurile, vrea sa le numeroteze cu etichete. El vrea sa cumpere cutii care contin etichete cu cifre.
 
La magazinul din apropiere se gasesc k asemenea pachete care contin etichete cu cateva cifre de 0, cateva cifre de 1 si asa mai departe (pachete diferite pot avea continut diferit).
 
Tudor ar vrea sa cumpere cateva dintre pachete si sa poata forma din etichete toate numerele de la 1 la K (K fiind numarul de CD-uri si DVD-uri din colectie).
 
O conditie pentru a realiza etichetarea este ar fi sa nu ramana etichete care nu sunt folosite pentru ca Tudor nu ar avea ce face cu ele. Acest lucru nu este tot timpul posibil. Daca este posibil, atunci ne intereseaza solutia care foloseste un numar minim de pachete.
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare colectie.in se afla doua numere naturale N si K, reprezentand numarul de pachete de la magazin, respectiv numarul de CD-uri si DVD-uri din colectia lui Tudor. Pe urmatoarele N linii se vor afla cate zece numere intregi separate prin spatii; linia i + 1 contine numarul de etichete cu cifrele 0, 1, ... 9 din pachetul i.
 
h2. Date de Iesire
 
In fisierul de iesire colectie.out se va scrie pe prima linie valoarea 1 daca exista o solutie, sau valoarea 0 daca problema nu are solutie. Daca problema are solutie atunci pe urmatoarea linie va fi scris numarul L al pachetelor folosite intr-o solutie optima, iar urmatoarea linie va contine L numere intregi, reprezentand pachetele alese.
 
h2. Restrictii
 
. 1 <= N <= 32
 
. 1 <= K <= 100.000.000
 
h2. Exemplu
 
colectie.in colectie.out
 
4 11 1
 
0 1 0 0 0 0 1 1 0 0 2
 
1 2 1 1 1 1 0 0 0 0 2 4
 
0 1 0 0 0 0 0 0 1 1
 
0 2 0 0 0 0 1 1 1 1
 
 
==Include(page="template/taskfooter" task_id="colectie")==