Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | map.in, map.out | Sursă | PACO 2006 |
| Autor | Sorin Stancu-Mara | Adăugată de | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Map
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
Max Damage, pentru a nu se pierde in calatoriile sale doreste sa isi faca o harta. Pentru a nu fi citita de oricine, el o codifica sub forma unei matrice cu N linii si M coloane. Pentru ca scrie urat, se duce la un prieten care are un tipar si il roaga sa ii tipareasca harta. Tiparul, fiind mai vechi, este stricat si tipareste harta de doua ori pe aceeasi foaie, dar cu o deplasare (spre dreapta).
Apare politia si Max fuge cu foaia prost tiparita. Ajuns la ascunzatoare el vede catastrofa: portiunea unde cele doua imprimari s-au suprapus se intampla sa coincida, astfel ca nu isi poate da seama unde se termina una si unde incepe cealalta. El vrea acum un program care, primind o astfel de matrice, sa returneze cea mai mica dimensiune a matricei originale astfel incat, suprapusa de doua ori cu o deplasare corecta spre dreapta, sa se obtina cea finala
Cerinta
Ajutati-l pe Max sa rezolve si aceasta problema zdrobitoare.
Date de Intrare
Prima linie din fisierul map.in va contine numerele M si N, reprezetand dimensiunea matricei. Urmatoarele M linii vor contine cate N litere mici ale alfabetului englez (matricea prost tiparita).
Date de Iesire
Fiserul map.out va contine pe prima linie o singura valoare, reprezentand dimensiunea orizontala minima a matricei originale.
Restrictii si observatii
- 1 <= N, M <= 2000
Exemple
| map.in | map.out | Explicatii |
|---|---|---|
| 3 5 anana arara mamam | 3 |
ana
ara
mam
suprapusa de doua ori se obtine:
anana
arara
mamam |
