Fişierul intrare/ieşire:csir.in, csir.outSursăONI 2005
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.incsir.out
4
BBAABAA
ABABAABAAB
ABA
AABABAAB
0
0
1
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content