Fişierul intrare/ieşire:piese.in, piese.outSursăpreONI 2008 Runda 3
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/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 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.

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.inpiese.out
3 4
6
1 1 2 4
1 1 3 3
5 6 3 3

Explicatie

Acoperirea din exemplu corespunde figurii:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content