stea

Gigel a primit sarcina de a confectiona steluta ce va impodobi varful pomului de Craciun de la scoala. Pentru aceasta si-a pregatit o coala de hartie argintie, in forma de triunghi echilateral. Coala are un model foarte frumos. Este impartita in n benzi. Fiecare banda are ca model alte triunghiuri echilaterale mici, (avand lungimea laturii de 1 cm), asezate alternativ (primul cu varful in sus, al doilea cu varful in jos, etc), ca în figura.
Cand sa se apuce de lucru - dezastru! Sora sa mai mica decupase din coala sa cateva triunghiuri mici. Singura solutie pe care o are Gigel este de a decupa din coala sa o zona in forma de triunghi echilateral de arie cat mai mare, care sa nu contina gauri.

Cerinta

Sa se determine numarul de triunghiuri echilaterale mici din care este constituita cea mai mare zona in forma de triunghi echilateral care nu contine gauri (maxim posibil).

Date de intrare

Fisierul de intrare stea.in contine pe prima linie un numar natural n care reprezinta numarul de benzi ale triunghiului. Urmatoarele n linii contin informatii despre aspectul colii de hartie. Pe linia i+1 se afla o secventa de caractere ce reprezinta a i-a banda din coala de hartie. Caracterele din secventa pot fi # (ceea ce semnifica faptul ca triunghiul mic corespunzator a fost decupat) sau - (ceea ce inseamna ca triunghiul mic corespunzator nu a fost decupat) sau spatiu (folosite la inceputul fiecarei linii, pentru a pastra aspectul triunghiular al colii).

Date de iesire

Fisierul de iesire stea.out contine o singura linie, pe care se afla un numar natural, reprezentand numarul de triunghiuri echilaterale mici din care este constituita cea mai mare zona in forma de triunghi echilateral care nu conține gauri.

Restrictii

  • 1 <= n <= 100

Exemple

stea.in stea.out stea.in stea.out

5
#-##----#
 -----#-
  ---#-
   -#-
    -

9 4
#-#-#--
 #---#
  ##-
   -
4

Timp maxim de executie: 0.2 secunde/test

Marinel Serban
Liceul de Informatica "Gr. C. Moisil" Iasi
marinel_serban@yahoo.com