Rezolvare PBinfo #4085

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.