== include(page="template/taskheader" task_id="piese") ==
Poveste si cerinta...
Danut nu a descoperit inca informatica si se joaca cu piese de diferite dimensiuni. Piesele sale sunt de forma patratica si au latura o putere a lui $2$. Astfel, Danut are piese de dimensiuni {$1x1$}, {$2x2$}, {$4x4$}, {$8x8$}, etc. Putem considera ca Danut are un numar nelimitat de piese din fiecare tip. Sarcina lui este acum sa acopere cu aceste piese o tabla de dimensiuni {$M x N$}. El stie ca orice patratel al tablei trebuie sa fie acoperit de exact o piesa. Pentru ca vrea sa realizeze acoperirea cu efort minim, Danut vrea sa foloseasca un numar minim de piese.
h2. Date de intrare
Fisierul de intrare $piese.in$ ...
Fisierul de intrare $piese.in$ contine pe prima linie numerele $M$ si {$N$}, cu semnificatia din enunt.
h2. Date de iesire
In fisierul de iesire $piese.out$ ...
In fisierul de iesire $piese.out$ se va scrie pe prima linie {$MIN$}, numarul minim de piese folosit. Fiecare din urmatoarele $M$ linii contine cate $N$ numere ce descriu acoperirea cu piese a tablei. Oricare piesa va avea asociat un numar natural unic de la $1$ la {$MIN$}. Astfel, al $j$-lea numar de pe linia $i+1$ ({$i$} de la $1$ la $M$, $j$ de la $1$ la {$N$}) reprezinta numarul piesei care acopera patratelul de coordonate {$(i j)$} de pe tabla. Daca sunt mai multe solutii cu numar minim de piese se poate afisa oricare.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ M, N ≤ 500$
* Punctajul pe un test nu se acorda decat daca acoperirea cu piese este corecta (este folosit un numar minim de piese de tipul celor descrise mai sus si tabla este acoperita in intregime)
h2. Exemplu
table(example). |_. piese.in |_. piese.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|3 4
|6
1 1 2 4
1 1 3 3
5 6 3 3
|
h3. Explicatie
...
Acoperirea din exemplu corespunde figurii:
!problema/piese?acoperire.bmp!
== include(page="template/taskfooter" task_id="piese") ==
