fbpx

Problema #1097 – Placare – Rezolvari PBInfo

de Mihai-Alexandru

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 placă dreptunghiulară de laţime P este codificată prin numărul natural P, iar o placă de înalţime P se codifică prin numărul întreg –P;
  • convenim ca 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 placi 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 Aij = valoarea absolută a codului plăcii care se suprapune peste pătrăţelul de pe linia i şi coloana j.

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).

Date de intrare

Fișierul de intrare placare.in are următoarea structură:

  • pe prima linie valorile naturale N 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.

Date de ieșire

Î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ţ.

Restricții și precizări

  • 1<=N,M<=100 pentru 80% din teste; 100<N,M<=300 pentru 20% din teste
  • 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.

Exemplul 1

placare.in

4 4
-4 1 1 1
1 2
2 1
3

placare.out

4 1 1 1
4 1 2 2
4 2 2 1
4 3 3 3

Explicație

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).

Exemplul 2

placare.in

3 2
-3 -2
0
1

placare.out

3 2
3 2
3 1
#include <bits/stdc++.h>

using namespace std;
ifstream cin("placare.in");
ofstream cout("placare.out");
int n , m, v[301][301];
int main()
{
    int x;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(v[i][j] == 0)
            {
                do
                {
                    cin >> x;
                }while(x == 0);
                if(x > 0)
                    for(int k = 0; k < x; k++)
                        v[i][k + j] = x;
                else
                    for(int k = 0; k < -x; k++)
                        v[i+k][j] = -x;
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cout << v[i][j]<<" ";
        cout << endl;
    }
    return 0;
}
Comentarii

S-ar putea sa iti placa