| Fişierul intrare/ieşire: | omogene.in, omogene.out | Sursă | ONI 2016, clasa a 9-a |
| Autor | Dan Pracsiu | Adăugată de |  Alexandru Valeanu •AlexandruValeanu |
| Timp execuţie pe test | 0.65 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | omogene.out |
|---|---|
| 2 4 0 1 2 0 1 2 0 1 | 6 |
| omogene.in | omogene.out |
|---|---|
| 3 3 0 1 2 0 2 2 0 1 1 | 3 |
