Fişierul intrare/ieşire: | custi.in, custi.out | Sursă | info-arena 1.0 |
Autor | Vlad Dumitriu | Adăugată de | |
Timp execuţie pe test | 0.125 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Custi
Directorul închisorii a terminat cu refacerea gardului. Acum lucrează la proiectul "Cuştilor de câini" şi l-a pus tot pe James Blond la partea cu calcule. Însă James se cam grăbeşte şi nu va mai zice toată povestea cu câinii şi cum trebuie să fie cuştile, dar v-a trimis un email cu problema lui insa transformata in ceva mai simplu: dându-se o matrice pătratică de mărime N x N care conţine numai 0 şi 1, se cere determinarea numărului tuturor sub-matricelor de mărime M x M (M ≤ N) care conţin numai elemente de 1. Astfel pentru un anumit test trebuie să afişati N linii, astfel:
Linia 1: câte submatrice de 1×1 cu proprietatea enunţată există.
...
Linia i: câte submatrice de ixi cu proprietatea enuntată există.
..
Linia N: câte submatrice de NxN cu proprietatea enunţată există.
Date intrare
În fişierul custi.in se găsesc:
- pe prima linie numărul N
- pe următoarele linii este dată matricea, cu elementele despărţite printr-un spaţiu (vezi exemplul)
Date ieşire
Fişierul custi.out are structura enunţată mai sus.
Restrictii si precizari:
- 1 ≤ N ≤ 1000
- Pentru 20%-30% din teste N ≤ 100
Exemple:
custi.in | custi.out |
---|---|
5 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 | 18 7 1 0 0 |
Explicatii
18 submatrice de 1×1
7 submatrice 2×2
1 sumatrice 3×3
0 submatrice 4×4
0 sumatrice 5×5, care conţin numai elemente de 1