Fișierul intrare/ieșire	patratele1.in, patratele1.out	Sursă	Augmentare problema patratele
Autor	Marinel Șerban	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1.7 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Patratele1 (baraj gimnaziu)

Notă: aceasta este problema patratele cu limite mărite pentru n și m.

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

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ă

În acest fel desenul alăturat poate fi codificat printr-un tablou bidimensional de dimensiuni 3 × 5 cu valorile:

Cerințe

Fiind date dimensiunile n și m ale foii de matematică, precum și tabloul bidimensional de dimensiune n × m care conține codificarea foii, să se determine:

1. numărul total de pătrate existente pe foaia de matematică în desenul realizat conform codificării
2. distribuția numărului de pătrate în ordinea strict crescătoare a lungimii laturilor
3. 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 patratele1.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 × 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 patratele1.out va conține următoarele, în funcție de cerința cerută:

1. Dacă t = 1, pe prima linie numărul total de pătrate determinat;
2. 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;
3. Dacă t = 3, prima linie va conține numărul maxim de pătrate, iar linia a doua va conține 2 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ă;
• 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 3 valori numerice afișate vor fi de asemenea 0).

Restricții

• 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 ≤ 700

Exemple