Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | harta4.in, harta4.out | Sursă | Tabăra ICHB 2012, Ziua 1, Grupa 2 |
| Autor | Dan Constantin Spatarel | Adăugată de |  Dan-Constantin Spatarel •spatarel |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Harta4
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ăţ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:
- Codmat(N, M) -> K
- Codmat(N, M) -> "O", L, Codsup(L, M), Codinf(N - L, M)
- Codmat(N, M) -> "V", C, Codst(N, C), Coddr(N, M - C)
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.
Date de intrare
Fişierul de intrare harta4.in ...
Date de ieşire
În fişierul de ieşire harta4.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| harta4.in | harta4.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
