Fişierul intrare/ieşire:omogene.in, omogene.outSursăONI 2016, clasa a 9-a
AutorDan PracsiuAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test1.3 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Omogene

Se consideră o matrice cu L linii şi C coloane care memorează doar valori din mulţimea {0,1,2}. O submatrice nevidă (formată din cel puţin o linie şi cel puţin o coloană) a acestei matrici o numim omogenă dacă numărul valorilor de 0 este egal cu numărul de valori de 1 şi egal cu numărul valorilor de 2.
De exemplu, în matricea
0 1 2 0
1 2 0 1
sunt şase submatrici omogene, acestea fiind:
0 1 2 | 1 2 0 | 0 1 2 | 1 2 0 | 1 2 0 | 2 0 1
1 2 0 | 2 0 1 |

Submatricile a treia şi a patra sunt formate din prima linie a matricei iniţială, iar submatricile a cincea şi a şasea sunt formate din a doua linie.

Cerinţă

Să se determine câte submatrici nevide omogene există.

Date de intrare

Fişierul omogene.in conţine pe prima linie numerele naturale L şi C. Pe următoarele L linii se află câte C numere naturale separate prin spaţii reprezentând câte o linie din matrice.

Date de ieşire

Fişierul omogene.out va conţine pe prima linie un singur număr natural reprezentând numărul submatricilor nevide omogene.

Restricţii

  • 2 ≤ L ≤ C ≤ 5.000
  • 4 ≤ L * C ≤ 65.536
  • Atenţie: o submatrice este formată dintr-o secvenţă continuă de linii şi coloane. De exemplu, dacă se aleg dintr-o matrice liniile 1, 2 şi 5, atunci acestea nu formează o submatrice.
  • Numărul submatricilor omogene va fi mai mic decât 2*109.
  • Întreaga matrice poate fi o submatrice omogenă.

Exemplu

omogene.inomogene.out
2 4
0 1 2 0
1 2 0 1
6
omogene.inomogene.out
3 3
0 1 2
0 2 2
0 1 1
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?