# PBinfo #4085 – Patratele – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: deivid ## Enunț Gigel are în fața sa pe o foaie de matematică un desen obținut prin trasarea mai multor linii orizontale și verticale de lungime 1 de-a lungul modelului foii de matematică. Gigel a învăţat de la colegii mai mari un joc, care se joacă în doi: delimitează pe foaia de matematică o zonă dreptunghiulară, apoi, pe rând, trag cu creionul câte o linie pe o latură a unui pătrăţel. Cel care reuşeşte să formeze cele mai multe pătrăţele câştigă. Ochii lui Gigel sunt obişnuiţi să vadă imediat o problemă de matematică, chiar dacă se joacă. Privind desenul de pe foaie el se întreabă: “Oare câte pătrate s-au format din liniile trasate?” În desenul alăturat se vede foaia formată din 3 linii şi 5 coloane, precum şi liniile trasate până la un moment dat. Se pot distinge trei pătrate de latură 1, două pătrate de latură 2 şi un pătrat de latură 3. În problema noastră vom codifica fiecare pătrat de latură 1 de pe foaie cu un număr natural cuprins între 0 şi 15 obținut prin însumarea codificării fiecărei laturi astfel: 1 – dacă latura de sus este trasată 2 – dacă latura din dreapta este trasată 4 – dacă latura de jos este trasată 8 – dacă latura din stânga este trasată Apoi se face suma codificărilor laturilor pentru a afla codificarea fiecărui pătrățel. În acest fel desenul alăturat poate fi codificat printr-un tablou bidimensional de dimensiuni 3 x 5 cu valorile: 9 7 15 13 7 14 15 11 15 11 1 3 12 7 14 Cerința Fiind date dimensiunile n şi m ale foii de matematică, precum şi tabloul bidimensional de dimensiune n x m care conține codificarea foii, să se determine: numărul total de pătrate existente pe foaia de matematică în desenul realizat conform codificării distribuția numărului de pătrate în ordinea strict crescătoare a lungimii laturilor unde poate fi trasată încă o linie astfel încât numărul total de pătrate să crească și să devină maxim posibil Date de intrare Fişierul de intrare patratele.in conţine pe prima linie trei numere naturale n m t, separate prin câte un spaţiu, indicând dimensiunile foii de matematică n x m, respectiv cerinţa care trebuie rezolvată (1, 2 sau 3). Fiecare dintre următoarele n linii conţine câte m numere naturale, fiecare dintre acestea reprezentând codificarea foii de matematică. Date de ieșire Fișierul de ieșire patratele.out va conține următoarele în funcție de cerința cerută: Dacă t = 1, pe prima linie numărul total de pătrate determinat; Dacă t = 2, pe fiecare linie vor fi afișate câte două numere naturale nenule a și b, separate printr-un spaţiu, indicând lungimea laturii pătratelor – a, respectiv numărul de pătrate cu latura de lungimea respectivă – b, în ordinea strict crescătoare a valorilor lui a; Dacă t = 3, prima linie va conține numărul maxim de pătrate, iar linia a doua va conține două valori naturale lin, col și un cuvânt pozitie separate printr-un spațiu, unde lin, col reprezintă coordonatele pătratului de latură 1 unde se trasează linia suplimentară, iar pozitie ∈ {SUS, DREAPTA, JOS, STANGA, NU} (se va afișa NU în cazul în care nu se poate trasa nicio linie – în acest caz cele trei valori numerice afișate vor fi de asemenea 0). Restricții și precizări Numerotarea liniilor și coloanelor foii de matematică începe de la 1 Dacă la cerința t=3 se obțin mai multe poziții de trasare a liniei, se va afișa soluția cu indicele liniei minim, iar în caz de egalitate după linii, se va afișa soluția cu indicele coloanei minim. În cazul în care există mai multe posibilități de trasare a unei linii în același pătrat, pozițiile vor fi luate în ordinea SUS, DREAPTA, JOS, STANGA 1 ≤ n, m ≤ 60 Pentru 30 de puncte, t = 1 Pentru 30 de puncte, t = 2 Pentru 10 puncte, t = 3 și 1 ≤ n, m ≤ 20 Pentru 30 de puncte, t = 3 Exemplul 1: patratele.in 3 5 1 9 7 15 13 7 14 15 11 15 11 1 3 12 7 14 patratele.out 6 Explicație Se rezolvă cerința 1. În total au fost găsite 6 pătrate Exemplul 2: patratele.in 3 5 2 9 7 15 13 7 14 15 11 15 11 1 3 12 7 14 patratele.out 1 3 2 2 3 1 Explicație Se rezolvă cerința 2. 3 pătrate de latură 1 2 pătrate de latură 2 1 pătrat de latură 3 Exemplul 3: patratele.in 3 5 3 9 7 15 13 7 14 15 11 15 11 1 3 12 7 14 patratele.out 9 2 5 JOS Explicație Se rezolvă cerința 3. Dacă se trasează încă o linie la pătratul din linia 2 coloana 5 jos, se mai obțin încă 3 pătrate. Exemplul 4: patratele.in 3 3 3 9 1 3 8 0 2 12 0 0 patratele.out 0 0 0 NU Explicație Se rezolvă cerința 3. Nu se poate adăuga niciun pătrat nou prin trasarea unei singure linii. ## Cod sursă C++ ```cpp /** Autor: Bogdan-Ioan Popa, FMI Universitatea din Bucuresti Scor: 100p **/ #include #define N_MAX 60 using namespace std; ifstream fin("patratele.in"); ofstream fout("patratele.out"); int N, M, t; int A[N_MAX + 5][N_MAX + 5]; int up[N_MAX + 5][N_MAX + 5]; int ri[N_MAX + 5][N_MAX + 5]; int dwn[N_MAX + 5][N_MAX + 5]; int le[N_MAX + 5][N_MAX + 5]; int ans[N_MAX + 5]; int di[] = {-1, 0, 1, 0}; int dj[] = {0, 1, 0, -1}; int dir[] = {2, 3, 0, 1}; int p2[] = {1, 2, 4, 8}; char side[][8] = { "SUS", "DREAPTA", "JOS", "STANGA" }; bool check_side(int conf, int side) { return conf / p2[side] % 2; } void flip_side(int &conf, int side) { if(check_side(conf, side)) { conf -= p2[side]; } else { conf += p2[side]; } } int compute_ans() { memset(ans, 0, sizeof(ans)); memset(le, 0, sizeof(le)); memset(ri, 0, sizeof(ri)); memset(up, 0, sizeof(up)); memset(dwn, 0, sizeof(dwn)); int total_ans = 0; for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { if(check_side(A[i][j], 1)) { up[i][j] = 1 + up[i - 1][j]; } if(check_side(A[i][j], 2)) { le[i][j] = 1 + le[i][j - 1]; } } } for(int i = N; i >= 1; i--) { for(int j = M; j >= 1; j--) { if(check_side(A[i][j], 0)) { ri[i][j] = 1 + ri[i][j + 1]; } if(check_side(A[i][j], 3)) { dwn[i][j] = 1 + dwn[i + 1][j]; } } } for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { int max_k = min(min(dwn[i][j], ri[i][j]), min(N - i + 1, M - j + 1)); for(int k = 1; k <= max_k; k++) { int ii = i + k - 1; int jj = j + k - 1; if(k <= up[ii][jj] && k <= le[ii][jj]) { ans[k]++; total_ans++; } } } } return total_ans; } int main() { fin >> N >> M >> t; for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { fin >> A[i][j]; } } int sol = compute_ans(); if(t == 3) { int max_ans = sol; int ans_i, ans_j, ans_d; bool ok = false; for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { for(int d = 0; d < 4; d++) { if(!check_side(A[i][j], d)) { int ii = i + di[d]; int jj = j + dj[d]; flip_side(A[i][j], d); flip_side(A[ii][jj], dir[d]); int curr = compute_ans(); flip_side(A[i][j], d); flip_side(A[ii][jj], dir[d]); if(max_ans < curr) { ok = true; max_ans = curr; ans_i = i; ans_j = j; ans_d = d; } } } } } if(!ok) { fout << "0\n0 0 NU\n"; } else { fout << max_ans << "\n" << ans_i << " " << ans_j << " " << side[ans_d] << "\n"; } } else { if(t == 1) { fout << sol << "\n"; } else { for(int i = 1; i <= N; i++) { if(ans[i] != 0) { fout << i << " " << ans[i] << "\n"; } } } } return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4085) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4085/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4085/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)