custi

Custi

== include(page="template/taskheader" task_id="custi") ==

==Include(page="template/taskheader" task_id="custi")==

Poveste ...
 
h2. Cerinta

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 $1x1$ 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ă.

h2. Restrictii

h2. Date intrare

...

În fişierul $custi.in$ se găsesc:

h2. Date de intrare

* pe prima linie numărul $N$
* pe următoarele linii este dată matricea, cu elementele despărţite printr-un spaţiu (vezi exemplul)

...

h2. Date ieşire

h2. Date de iesire

Fişierul $custi.out$ are structura enunţată mai sus.
 
h2. Restrictii si precizari:
 
* $1 ≤ N ≤ 1000$
* Pentru $20%-30%$ din teste $N ≤ 100$
 
h2. Exemple:
 
table(example). |_. 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 |
 
h3. Explicatii
 
$18$ submatrice de $1x1$
$7$ submatrice $2x2$
$1$ sumatrice $3x3$
$0$ submatrice $4x4$
$0$ sumatrice $5x5$, care conţin numai elemente de $1$

...
h2. Exemplu

==Include(page="template/taskfooter" task_id="custi")==

| custi.in | custi.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="custi") ==

902