Fişierul intrare/ieşire:poveste.in, poveste.outSursăAlgoritmiada 2015, Runda 2
AutorAdrian Budau, Eugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inpoveste.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?