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 ABA AABABAAB | 0 0 1 1 |