PROBLEMA 7:                     JOCUL VIETII 1D
DEADLINE:                       Duminica, 7 martie 1999
TIMP DE IMPLEMENTARE:           2 ore
PUNCTAJ:                        90 dexteri
                                (nu e din cauza inflatiei; mi se pare
                                o problema intr-adevar dura)
DOMENIU:                        N/A :)

Multe multumiri lui Viorel Canja, de la care am aflat atat problema,
cat si solutia!

O colonie este formata din N celule asezate pe un cerc; unele celule
sunt vii si altele moarte. Definim evolutia cu o generatie a coloniei
ca fiind procesul prin care toate celulele isi schimba simultan starea
conform urmatoarelor reguli:

1) Intre doua celule moarte nu poate exista o celula vie.
2) Intre doua celule vii, orice celula vie se sufoca si moare.
3) Intre o celula moarta si una vie, o celula supravietuieste (sau
daca era moarta, una noua se naste in loc).

Lamurire: Starea unei celule din generatia cu numarul k depinde
exclusiv de starile celulelor vecine ei din generatia k-1.

De exemplu, codificand cu 0 o celula moarta si cu 1 o celula vie, iata
cum evolueaza colonia 1001011 (N=7). Subliniem ca prima celula este
vecina cu ultima, colonia avand forma circulara.

1001011 ==> 1110010 ==> 1011100 ==> 0010111 ==> ...
 Gen. 0      Gen. 1      Gen. 2      Gen. 3

Spunem ca o colonie se stabilizeaza daca exista o generatie S>=0
incepand de la care nici o celula nu isi mai schimba starea, adica
aspectul coloniei este acelasi la generatiile S, S+1, S+2, ...
Dandu-se o colonie cu N celule, sa se spuna daca ea se stabilizeaza si
daca da, care este valoarea minima pentru S (valoarea minima in sensul
ca generatia S-1 este diferita de generatia S).

DATELE DE INTRARE: Fisierul COLONIE.IN contine pe prima linie numarul
de celule, N<=100. Pe a doua linie fisierul contine o secventa de N
caractere 0 (reprezentand celule moarte) si 1 (reprezentand celule
vii), corespunzatoare generatiei 0. Caracterele NU sunt despartite
prin spatii.

DATELE DE IESIRE: Fisierul COLONIE.OUT contine pe prima linie
mesajul DA sau NU, dupa cum colonia se stabilizeaza sau nu. Daca
raspunsul este DA, pe linia a doua se va tipari valoarea lui S.

EXEMPLE:

COLONIE.IN              COLONIE.OUT
4                       DA             // Pentru ca 1110 ==> 1010 ==>
1110                    2              // ==> 0000 ==> 0000 ==> ...

COLONIE.IN              COLONIE.OUT
5                       NU
11110

TIMP DE RULARE: 0.0002(7) ore.
COMPLEXITATE RECOMANDATA: O(N^3).