Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | piese.in, piese.out | Sursă | preONI 2008 Runda 3 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Piese
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 1×1, 2×2, 4×4, 8×8, 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.
Date de intrare
Fisierul de intrare piese.in contine pe prima linie numerele M si N, cu semnificatia din enunt.
Date de iesire
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.
Restrictii
- 1 ≤ M, N ≤ 500
Exemplu
| piese.in | piese.out |
|---|---|
| 4 3 | 6 1 1 2 1 1 3 4 5 5 6 5 5 |
Explicatie
Acoperirea din exemplu corespunde figurii:
!?acoperie.bmp?
