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. Daca sunt mai multe solutii cu numar minim de piese se poate afisa oricare.
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)
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:
