Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | poveste.in, poveste.out | Sursă | Algoritmiada 2015, Runda 2 |
| Autor | Adrian Budau, Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Poveste
Facultatea de Automatică şi Numărătoare s-a hotărât să producă un robot, pe numele său AutoMitică, care să treacă Testul Turing. Deoarece acest test presupune ca robotul să fie capabil de un minim de analiză literară, cercetătorii l-au învăţat astăzi despre stilul narativ circular. Mai exact, AutoMitică este capabil să citească "literatură" care ia forma unei matrice binare de dimensiuni A x B. Fiecare dintre cele B coloane reprezintă o pagină pentru Automitică, iar acesta le citeşte în ordine de la stânga la dreapta, în ordine crescătoare a indicilor coloanelor. Deoarece AutoMitică nu este foarte talentat, el poate recunoaşte circularitatea unei poveşti doar dacă prima pagină este literalmente identică cu ultima pagină a poveştii. Cercetătorii din facultate au o matrice binară de dimensiuni N x M şi ar dori să decupeze o submatrice de arie cât mai mare, care are proprietatea de circularitate (i.e, prima coloană este identică cu ultima).
Date de intrare
Fişierul de intrare poveste.in va conţine pe prima sa linie valorea T semnificând numărul de teste din fişier. Vor urma T teste care respectă următorul format: prima linie va conţine valorile N M reprezentând numărul de linii respectiv numărul de coloane ale matricei. Urmează N linii fiecare conţinând câte M caractere 0 sau 1, neseparate prin whitespace.
Date de ieşire
În fişierul de ieşire poveste.out se vor afla T linii cu câte o singură valoare, reprezentând răspunsul pentru testul respectiv.
Restricţii
- 1 ≤ T ≤ 5
- 1 ≤ N, M ≤ 1000
- Testele 1 şi 2 respectă N, M <= 60
- Testele 3 şi 4 respectă N, M <= 400
- Testele 5, 6 şi 7 respectă N, M <= 650
Exemplu
| poveste.in | poveste.out |
|---|---|
| 1 3 4 1011 0001 1000 | 6 |
Explicaţie
Se poate decupa matricea de 2 × 3 cu colţul stânga sus în (0, 0).
