placare

Placare

== include(page="template/taskheader" task_id="placare") ==

O suprafaţă dreptunghiulară de înălţime $N$ şi lăţime $M$ unităţi  trebuie acoperită perfect (placată) prin utilizarea unor plăci de formă dreptunghiulară de dimensiune $1 x P$ sau $P x 1$, unde $P$ este un număr natural nenul. Suprafaţa dată poate fi privită ca un caroiaj cu $NxM$ pătrăţele egale cu unitatea.
O placare corectă a suprafeţei iniţiale se memorează într-un fişier text folosind următoarele convenţii de codificare:
* pe prima linie se precizează  dimensiunile $N$ şi $M$ ale suprafeţei;

O suprafaţă dreptunghiulară de înălţime $N$ şi lăţime $M$ unităţi trebuie acoperită perfect (placată) prin utilizarea unor plăci de formă dreptunghiulară de dimensiune $1xP$ sau $Px1$, unde $P$ este un număr natural nenul. Suprafaţa dată poate fi privită ca un caroiaj cu $NxM$ pătrăţele egale cu unitatea. O placare corectă a suprafeţei iniţiale se memorează într-un fişier text folosind următoarele convenţii de codificare:
 
* pe prima linie se precizează dimensiunile $N$ şi $M$ ale suprafeţei;

* o placă dreptunghiulară de lăţime $P$ este codificată prin numărul natural $P$, iar o placă de înalţime $P$ se codifică prin numărul întreg $–P$;
* convenim că placa având ambele dimensiuni egale cu unitatea să se codifice cu valoarea $1$;
* pe fiecare din cele $N$ linii ale codificării se află câte un şir de valori întregi reprezentând, în ordine de la stânga la dreapta, codurile plăcilor care se găsesc amplasate începând de la respectiva linie;
* codul $P$ strict mai mare ca $1$ al unei placi orizontale apare o singură dată pe linia corespunzătoare pe care se află placa, iar codul $–P$ al unei plăci verticale va apare o singură dată şi anume pe prima linie de la care placa respectivă este amplasată în jos pe o anumita coloană a suprafeţei;
* dacă pe o anumită linie a suprafeţei nu există astfel de coduri de plăci, atunci pe respectiva linie din fişier este o singură valoare de $0$.

Folosind codificarea unei placări a suprafeţei iniţiale, se poate determina imaginea acestei placări sub forma unui tablou bidimensional $A$, cu $N$ linii şi $M$ coloane, unde {$A{~ij~}$} = valoarea absolută a codului plăcii care se suprapune peste pătrăţelul de pe linia $i$ şi coloana $j$.

h2. Cerinţă
 
Cunoscând codificarea unei placări corecte a suprafeţei date să se obţină imaginea acestei placări (matricea de valori corespunzătoare codificării suprafeţei).
 

h2. Date de intrare

Fişierul de intrare $placare.in$ ...

Fişierul de intrare $placare.in$ va avea pe prima linie valorile naturale $N$ si $M$, separate printr-un spaţiu, unde $N$ este înălţimea suprafeţei, $M$ este lăţimea suprafeţei. Pe fiecare din următoarele $N$ linii se află un şir de valori întregi, separate prin câte un spaţiu, reprezentând codificarea respectivei linii a placării.

h2. Date de ieşire

În fişierul de ieşire $placare.out$ ...

În fişierul de ieşire $placare.out$ se va tipări tabloul bidimensional ce reprezintă imaginea placării, compus din $N$ linii, pe fiecare dintre ele aflându-se $M$ valori naturale separate prin câte un spaţiu, cu semnificaţia din enunţ.

h2. Restricţii

h2. Restricţii şi precizări

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

* $1 ≤ N, M ≤ 300$
* pentru $80%$ din teste $1 ≤ N, M ≤ 100$
* dimensiunea $P$ sau $–P$ a unei plăci este aleasă astfel încât acoperirea obţinută să nu depăşească înălţimea $N$ sau latimea $M$ a suprafeţei.
* datele din fişierul de intrare sunt corecte în sensul că reprezintă codificarea unei acoperiri a zonei dreptunghiulare de dimensiuni $N$ şi $M$.

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

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

|4 4
-4 1 1 1
1 2
2 1
3
| 4 1 1 1
4 1 2 2
4 2 2 1
4 3 3 3
|
 
table(example). |_. placare.in |_. placare.out |
|3 2
-3 -2
0
1
| 3 2
3 2
3 1

|
h3. Explicaţie

...

Pentru primul exemplu, valoarea $-4$ codifică o placă de înălţime $4$ şi laţime $1$ plasată începând din pătratul de coordonate $(1,1)$ şi pînă în pătratul de coordonate $(4,1)$. Valoarea $3$ de pe ultima linie a codificării desemnează o placă de lăţime $3$ şi înălţime $1$, plasată orizontal, începând din pătrăţelul de coordonate $(4,2)$.
 

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

4639