Fişierul intrare/ieşire:colectie.in, colectie.outSursăFinala GInfo 2005
AutorCosmin Silvestru Negruseri, Leonard CrestezAdăugată de
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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

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.

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.

Restrictii

  • 1 ≤ N ≤ 32
  • 1 ≤ K ≤ 100.000.000

Exemplu

colectie.incolectie.out
4 11
0 1 0 0 0 0 1 1 0 0
1 2 1 1 1 1 0 0 0 0
0 1 0 0 0 0 0 0 1 1
0 2 0 0 0 0 1 1 1 1
1
2
2 4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content