== include(page="template/taskheader" task_id="harta4") ==
Poveste şi cerinţă...
De-a lungul timpului, Secţiunea Unu a adunat numeroase fotografii din satelit, acestea fiind nişte hărţi a diferitelor locaţii în care diverse organizaţii teroriste îşi desfăşoară activitatea.
Birkhoff a constatat că toate aceste hărţi ocupă foarte mult spaţiu pe serverele Secţiunii, aşa că s-a hotărât să le comprime. Pentru a fi imposibil de decomprimat de cineva din afara Secţiunii, Birkhoff a inventat un sistem de decomprimare propriu.
O hartă decomprimată este stocată sub forma a două numere naturale $N$ şi $M$, reprezentând dimensiunea hărţii (numărul de linii respectiv numărul de coloane) şi o matrice de numere naturale cu $N$ linii şi $M$ coloane.
O hartă comprimată este stocată sub forma a două numere naturale $N$ şi $M$, reprezentând dimensiunea hărţii (numărul de linii respectiv numărul de coloane) şi un şir de numere naturale şi litere.
Conţinutul hărţii este codificat complet prin şirul de numere naturale şi litere. Astfel, se disting trei cazuri:
* codificarea începe cu un număr natural $K$, caz în care matricea hărţii are în toate celulele sale numărul $K$;
* codificarea începe cu litera "O", urmată de un număr natural (numit în continuare $L$) şi de descrierea a două alte hărţi, caz în care matricea hărţii a fost împărţită într-o sub-matrice superioară (de $L$ linii şi $M$ coloane) şi o sub-matrice inferioară (de $N - L$ linii şi $M$ coloane) iar cele două descrieri din codificare corespund respectiv celor două sub-matrice;
* codificarea începe cu litera "V", urmată de un număr natural (numit în continuare $C$) şi de descrierea a două alte hărţi, caz în care matricea hărţii a fost împărţită într-o sub-matrice stângă (de $N$ linii şi $C$ coloane) şi o sub-matrice dreaptă (de $N$ linii şi $M - C$ coloane) iar cele două descrieri din codificare corespund respectiv celor două sub-matrice.
Putem scrie cele de mai sus mai succint, astfel:
* Cod{~mat(N, M)~} -> K
* Cod{~mat(N, M)~} -> "O", L, Cod{~sup(L, M)~}, Cod{~inf(N - L, M)~}
* Cod{~mat(N, M)~} -> "V", C, Cod{~st(N, C)~}, Cod{~dr(N, M - C)~}
Se impun restricţiile:
* $1 ≤ L ≤ N$
* $1 ≤ C ≤ M$
V-aţi oferit să-l ajutaţi pe Birkhoff, aşa că va trebui, pentru o hartă pe care v-a pus-o la dispoziţie, să-i spuneţi care este lungimea minimă a unui şir care o comprimă fără pierdere de calitate.
h2. Date de intrare
Fişierul de intrare $harta4.in$ ...
Fişierul de intrare $harta4.in$ conţine pe prima linie două numere naturale $N$ şi $M$. Pe fiecare din următoarele $N$ linii se află câte $M$ numere naturale, reprezentând harta pe care Birkhoff v-a pus-o la dispoziţie.
h2. Date de ieşire
În fişierul de ieşire $harta4.out$ ...
În fişierul de ieşire $harta4.out$ se va găsi un singur număr natural, reprezentând lungimea minimă a unui şir care comprimă harta dată fără pierdere de calitate.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 30$
* Elementele matricei vor fi numere naturale, cuprinse între $1$ şi $100$.
h2. Exemplu
table(example). |_. harta4.in |_. harta4.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 3
10 10 20
10 10 20
20 20 20
| 7
|
h3. Explicaţie
...
Matricea dată poate fi codificată optim prin şirul:
$O, 2, V, 2, 10, 20, 20$, de lungime $7$.
Pentru clarificare, putem paranteza şirul: $(O, 2, (V, 2, (10), (20)), (20))$.
== include(page="template/taskfooter" task_id="harta4") ==
