Să considerăm o imagine alb-negru de dimensiune L x L pixeli. Un pixel poate fi alb (codificat cu valoarea 0) sau negru (codificat cu valoarea 1). Imaginile pot fi compresate în diverse moduri. Una dintre cele mai cunoscute scheme de compresie este următoarea:
1. Dacă imaginea este formată atât din pixeli 1, cât şi din pixeli 0, se reţine valoarea 1, care indică faptul că imaginea va fi partiţionată în alte 4 subimagini, aşa cum este descris la pasul 2. Altfel codificăm întreaga imagine ca 00 sau 01 semnificând faptul că întreaga imagine este formată numai din pixeli 0, respectiv numai din pixeli 1.
2. O imagine I este împărţită în 4 subimagini A, B, C, D după cum este ilustrat în figura următoare:
Apoi se aplică din nou pasul 1, pentru fiecare dintre cele 4 subimagini, în ordinea A, B, C, D.
Numărul de biţi (cifre de 0 sau 1) obţinuţi în urma compresiei reprezintă dimensiunea imaginii compresate.
Cerinţă
Dată fiind o imagine, să se determine dimensiunea imaginii compresate.
Date de intrare
Fişierul de intrare imagine.in conţine pe prima linie L (dimensiunea imaginii). Urmăroarele L linii conţin imaginea codificată, fiecare linie conţinând exact L valori 0 sau 1 separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire imagine.out conţine o singură linie pe care se află un număr natural care reprezintă dimensiunea imaginii compresate.
Restricţii
1<=L<=250
Exemple
imagine.in
imagine.out
Explicaţii
4
1 1 1 1
1 1 0 1
0 1 0 0
0 0 1 1
30
Compresia imaginii din exemplul 1 se realizează astfel:
Deoarece după compresare sunt necesari 30 de biţi, dimensiunea imaginii compresate este 30.
