Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | csir.in, csir.out | Sursă | ONI 2005 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Csir
Un sir circular este un sir format numai din caracterele "A" si "B" care are urmatoarele proprietati:
- are lungime 1 ≤ N (nu poate fi sirul vid);
- se considera ca dupa ultimul caracter din sir urmeaza primul caracter din sir.
Aceasta proprietate implica faptul ca orice sir circular are N subsecvente de lungime L ( 1 ≤ L ≤ N ). O subsecventa de lungime L a unui sir circular S este un sir de caractere (obisnuit, nu circular) format din L caractere aflate pe pozitii consecutive in sirul S . De exemplu, sirul circular "ABAAB" are 5 subsecvente de lungime 3: "ABA", "BAA", "AAB", "ABA" si "BAB" (ele nu sunt distincte ca valoare, insa difera ca pozitie de inceput in sirul din care fac parte).
Un csir este un sir circular care are in plus urmatoarea proprietate: pentru orice L ( 1 ≤ L ≤ N )si oricare doua subsecvente de lungime L (sa le numim S1 si S2), numarul de caractere "A" din S1 difera fata de numarul de caractere "A" din S2 cu cel mult 1 (in valoare absoluta).Sa consideram sirul circular "BBAABAA". Acest sir nu este un csir, deoarece exista subsecventele "BBAAB" si "AABAA" (de lungime 5), care contin 2, respectiv 4 caractere "A" (diferenta dintre numarul de caractere "A" este, astfel, 2). De asemenea, sirul $"ABABAABAAB " nu este un csir, deoarece contine subsecvente " AABAA " si " BABAB " pentru care diferenta dintre numarul de caractere " A " este mai mare decat 1 (in valoare absoluta). Sirurile circulare " ABA " si " AABABAAB " sunt, in schimb, csir-uri, deoarece oricare ar fi doua subsecvente S1 si S2 avand aceeasi lungime, diferenta dintre numarul de caractere " A " din S1 si numarul de caractere " A " din S2 este mai mica sau egala cu 1 (in valoare absoluta).
Cerinta
Dandu-se mai multe siruri circulare, determinati daca ele sunt csir-uri.
Date de Intrare
Prima linie a fisierului de intrare csir.in contine numarul intreg S , reprezentand numarul de siruri continute in fisier. Pe fiecare dintre urmatoarele S linii se afla cate un sir circular.
Date de Iesire
In fisierul de iesire csir.out se vor scrie S linii. Pe a K -a linie din acest fisier, se va afisa 1 , daca al K -lea sir din fisierul de intrare este un csir, sau 0 , in caz contrar.
Restrictii si precizari
. 1 <= S <= 20
. Lungimea fiecarui sir circular din fisierul de intrare este cuprinsa intre 1 si 50.000 (inclusiv).
. Sirurile contin numai caracterele " A " si " B " (nu si "a" sau "b").
. Nu se acorda punctaje partiale.
Exemplu
csir.in | csir.out |
4 | |
BBAABAA | |
ABABAABAAB | 1 |
ABA | 1 |
AABABAAB |