Compaq Computer Romania

Un număr de n celule sensibile sunt așezate în cerc, fiecare comunicând cu cei doi vecini ai săi. O celulă se poate găsi în două stări: excitată sau liniștită. Dacă o celulă este excitată la un moment dat t, atunci ea emite un semnal care ajunge la cele două celule vecine la momentul t + 1. Fiecare celulă este excitată atunci și numai atunci, când la ea ajunge un semnal de la una din celulele vecine. Dacă semnalele ajung deodată din ambele părți, atunci ele se anulează.
     Dându-se o configurație inițială de celule excitate și liniștite, se cere să se determine dacă excitația se menține oricât de mult, sau se va liniști.

Prima linie a fișierului de intrare conține un număr natural m, reprezentând numărul configurațiilor din fișier.
     Fiecare din configurații se precizează pe două linii: pe prima linie se află un număr natural n, reprezentând numărul celulelor din configurație, iar pe a doua se află configurația propriu-zisă.
     O configurație este reprezentată printr-o succesiune de cifre (nedespărțite prin spații) din mulțimea {0, 1}, unde 1 indică faptul că celula este excitată, iar 0 indică faptul că celula este liniștită.

Fișierul de ieșire va conține câte o linie pentru fiecare configurație descrisă în fișierul de intrare. În cazul în care excitația se menține oricât de mult, pe linia corespunzătoare se va scrie șirul de caractere YES. În caz contrar, linia va conține șirul de caractere NO.

· 1 <= m <= 30;
· 1 <= n <= 10000;
· nu se va acorda punctajul corespunzător unui test decât dacă toate cele m răspunsuri sunt corecte; nu se acordă punctaje parțiale.

CELLS.IN
3
12
111111111111
3
110
6
101010

CELLS.OUT
NO
YES
NO

Pentru șirul format din 12 celule (toate fiind excitate), excitația nu se menține decât în primul moment de timp. La al doilea moment, fiecare celulă va primi câte un semnal de la cele două celule vecine, deci aceste semnale se vor anula reciproc. Ca urmare, nici una dintre celule nu va mai fi excitată la al doilea moment de timp, deci excitația nu se va menține.
     Pentru șirul format din 3 celule, dintre care primele două sunt excitate, configurația nu se modifică, deci excitația se va menține oricât de mult. Prima celulă va rămâne excitată deoarece va primi semnal doar de la a doua celulă; a doua celulă va rămâne și ea excitată deoarece va primi semnal doar de la prima celulă; a treia celulă va rămâne liniștită pentru că primește semnal atât de la prima, cât și de la a doua celulă.
     Pentru șirul format din 6 celule dintre care cele de pe pozițiile impare sunt excitate, iar cele de pe pozițiile pare sunt liniștite, excitația se menține, din nou, doar la primul moment de timp. La al doilea moment de timp celulele de pe pozițiile impare nu vor primi nici un semnal de la celulele vecine, iar celule de pe pozițiile pare vor primi câte un semnal de la cele două celule vecine, semnale care se vor anula reciproc. Așadar, în acest moment, nici una dintre celule nu este excitată, deci excitația nu se va menține, ci se va liniști.