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:

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;

* 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;

* $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.

* 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

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