| Fişierul intrare/ieşire: | zip.in, zip.out | Sursă | Grigore Moisil 2008, clasele 11-12 |
| Autor | Csaba Patcas | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zip
Un student oarecare, la o facultate oarecare are de scris ca tema de casa la o materie oarecare un program de arhivare. Studentul si-a propus sa implementeze urmatorul algoritm:
- Continutul fisierului de arhivat se imparte in M bucati avand exact K octeti
- Pentru doua bucati consecutive se determina cea mai lunga secventa de octeti de la sfarsitul primei bucati, care apare si la inceputul celei de-a doua bucati
- Arhivarea propriu-zisa se realizeaza prin scrierea bucatilor in fisier astfel incat secventele care apar si la sfarsitul bucatii curente si la inceputul bucatii urmatoare sa apara o singura data
Din cauza unei erori in program intre bucatile fisierului s-au strecurat si alte bucati, tot de lungime K, iar ordinea bucatilor s-a schimbat si ea. De asemenea, daca au existat bucati identice in fisierul initial, este posibil ca acestea sa apara de mai putine ori, in urma erorii.
Cerinta
Arhivati fisierului initial, stiind ca acesta este format din bucatile care conduc la o arhivare optima in sensul ca fisierul rezultat dupa arhivare are lungime minima.
Date de intrare
Pe prima linie a fisierului de intrare zip.in se afla trei numere naturale: N (numarul total al bucatilor care au fost obtinute de catre programul studentului), M (numarul bucatilor in fisierul initial) si K (lungimea in octeti a bucatilor). Cele trei numere sunt separate prin cate un spatiu. Pe urmatoarele N linii se afla cate K caractere, formand bucatile obtinute de catre student.
Date de iesire
In fisierul de iesire zip.out se va scrie lungimea fisierului arhivat.
Restrictii
- 1 ≤ M ≤ N ≤ 100
- 1 ≤ K ≤ 100
Exemplu
| zip.in | zip.out |
|---|---|
| 5 2 4 rado dora arad oboa aaaa | 5 |
Explicatie
Fisierul initial a fost format din bucatile arad si rado. Cea mai lunga secventa care satisface conditiile este rad, deci forma arhivata a fisierului va fi arado, avand cinci octeti.
