Fişierul intrare/ieşire:submatrix.in, submatrix.outSursăONI 2010, clasele 11-12
AutorAndrei GrigoreanAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Submatrix

Miruna a găsit pe fundul mării o matrice cu N linii şi M coloane având elementele numere naturale. Din motive necunoscute, Mirunel, prietenul misterios al Mirunei, vrea să afle care este latura celei mai mari submatrice pătratice care conţine maxim K numere distincte. Submatricea cu colţul stânga-sus (xs, ys) şi colţul dreapta-jos (xd, yd) este formată din toate elementele din matrice având indicele liniei în intervalul [xs, xd] şi indicele coloanei în intervalul [ys, yd].

Cerinţă

Scrieţi un program care să determine latura maximă a unei submatrice care respectă condiţiile lui Mirunel.

Date de intrare

Fişierul de intrare submatrix.in conţine pe prima linie trei numere naturale N, M şi K separate prin câte un singur spaţiu având semnificaţia din enunţ. Pe următoarele N linii se găsesc câte M numere naturale separate prin spaţiu, reprezentând elementele matricei.

Date de ieşire

Fişierul de ieşire submatrix.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând latura unei submatrice cu proprietatea din enunţ.

Restricţii

  • 1 ≤ N, M ≤ 300
  • 1 ≤ K ≤ N * M
  • Pentru 30% din teste 1 ≤ N, M ≤ 30
  • Pentru 70% din teste 1 ≤ N, M ≤ 150
  • Numerele din fişierul de intrare se vor incadra pe 32 de biţi cu semn.

Exemplu

submatrix.insubmatrix.out
5 7 3
6 5 7 3 6 6 7
5 7 5 5 7 3 7
3 3 5 3 5 6 7
7 7 5 5 5 6 7
7 7 6 5 6 3 5
3

Explicatie

O soluţie este submatricea având colţul din stânga-sus pe poziţia (2, 3) şi latura 3, care conţine doar elementele 3, 5 şi 7.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content