== 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 unic numar natural 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.

h2. Restrictii

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

* $1 ≤ M, N ≤ 500$

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

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

|4 3
|6
1 1 2
1 1 3
4 5 5
6 5 5

|
h3. Explicatie

...

Acoperirea din exemplu corespunde figurii:
!?acoperie.bmp?

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