Custi

custi

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

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

==Include(page="template/raw")==

Poveste ...

Directorul inchisorii a terminat cu refacerea gardului si acum lucreaza la proiectul "Custilor de caini", si l-a pus tot pe James Blond la partea cu calcule. Insa James se cam grabeste si nu va mai zice toata povestea cu cainii si cum trebuie sa fie custhile, dar va trimis un email cu problema lui insa transformata in ceva mai simplu, partea din e-mail care contine exact problema arata cam asa:
Danduse o matrice patratica $NXN$ care contine numai $0$ si {$1$}, se cere determinarea numarului tuturor sub-matricelor $MXM$ ({$M ≤ N$}) care contine numai elemente de {$1$}. Astfel pentru un anumit test trebuie sa afisati $N$ linii, astfel:

h2. Cerinta

Linia {$1$}: cate submatrici de $1 X 1$ cu proprietatea enuntzata exista

...

linia {$i$}: cate submatrici de $i X i$ cu proprietatea enuntzata exista
...
linia {$N$}: cate submatrici de $N X N$ cu proprietatea enuntzata exista
 
Mentiune: sub-matricele se pot suprapune cu altele
 
h2. Date intrare
 
In fiserul $custi.in$ se gasesc:
* pe prima linie numarul $N$
* pe urmatoarele linii e data matricea cu elementele despartite printr-un spatiu(vezi exemplu) cate $N$ valori pe linie

h2. Restrictii

h2. Date iesire

...

Fiserul $custi.out$ are structura enuntzata mai sus.

h2. Date de intrare

h2. Restrictii si precizari:

...

* $N<1001$
* Pt $20%-30%$ din teste $N<101$

h2. Date de iesire

Exemple:

...

table(example). |_. custi.in |_. custi.out |_. Explicatii |
| 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
| Exista:
18 submatrici de 1X1
7 submatrici 2X2
1 sumatrice 3X3
0 submatrici 4X4
0 sumatrici 5X5,  care contin numai elemente de 1 |

h2. Exemplu
| custi.in | custi.out |
| linia1
linia2
linia3
| linia1
linia2
|

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

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