.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » csir

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
csir


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
16MB / 1MB

Un şir circular este un şir format numai din caracterele ″A″ şi ″B″ care are următoarele proprietăţi:
- are lungime N >= 1 (nu poate fi şirul vid);
- se consideră că după ultimul caracter din şir urmează primul caracter din şir.
Această proprietate implică faptul că orice şir circular are N subsecvenţe de lungime L (1 <= L <= N).
O subsecvenţă de lungime L a unui şir circular S este un şir de caractere (obişnuit, nu circular) format din L caractere aflate pe poziţii consecutive în şirul S. De exemplu, şirul circular ″ABAAB″ are 5 subsecvenţe de lungime 3 : ″ABA″, ″BAA″, ″AAB″, ″ABA″ şi ″BAB″ (ele nu sunt distincte ca valoare, însă diferă ca poziţie de început în şirul din care fac parte).
Un cşir este un şir circular care are în plus următoarea proprietate: pentru orice L (1 <= L <= N) şi oricare două subsecvenţe de lungime L (să le numim S1 şi S2), numărul de caractere ″A″ din S1 diferă faţă de numărul de caractere ″A″ din S2 cu cel mult 1 (în valoare absolută).
Să considerăm şirul circular ″BBAABAA″. Acest şir nu este un cşir, deoarece există subsecvenţele ″BBAAB″ şi ″AABAA″ (de lungime 5), care conţin 2, respectiv 4 caractere ″A″ (diferenţa dintre numărul de caractere ″A″ este, astfel, 2). De asemenea, şirul ″ABABAABAAB″ nu este un cşir, deoarece conţine subsecvenţe ″AABAA″ şi ″BABAB″ pentru care diferenţa dintre numărul de caractere ″A″ este mai mare decât 1 (în valoare absolută).
Şirurile circulare ″ABA″ şi ″AABABAAB″ sunt, în schimb, cşir-uri, deoarece oricare ar fi două subsecvenţe S1 şi S2 având aceeaşi lungime, diferenţa dintre numărul de caractere ″A″ din S1 şi numărul de caractere ″A″ din S2 este mai mică sau egală cu 1 (în valoare absolută).

Cerinţă

Dându-se mai multe şiruri circulare, determinaţi dacă ele sunt cşir-uri.

Date de intrare

Prima linie a fişierului de intrare csir.in conţine numărul întreg S, reprezentând numărul de şiruri conţinute în fişier. Pe fiecare dintre următoarele S linii se află câte un şir circular.

Date de ieşire

În fişierul de ieşire csir.out se vor scrie S linii. Pe a K-a linie din acest fişier, se va afişa 1, dacă al K-lea şir din fişierul de intrare este un cşir, sau 0, în caz contrar.

Restricţii

1 <= S <= 20
Lungimea fiecărui şir circular din fişierul de intrare este cuprinsă între 1 şi 50000 (inclusiv).
Şirurile conţin numai caracterele ″A″ şi ″B″ (nu şi ″a″ sau ″b″).
Nu se acordă punctaje parţiale.

Exemple

csir.incsir.out
4 BBAABAA ABABAABAAB ABA AABABAAB 0 0 1 1

autor: Mugurel Ionuţ Andreica
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2005: baschet, ingerasi, numar1, prieteni, robinson, aritma, cezar, cuburi2, joc8, bifo, joc9, pal, romeo, seceta, antena, avere, joc11, paianjen, suma2, vizibil, masina3, lsort, patrat, ziduri, anticip, bsir, evantai, galax, spion, texan
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, string, poligon1, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, module, gxor
Despre şiruri de caractere: scp, ab, sl, nrcuv, rv, kpal, chimie, reteta, replace, grad, index, cod, text, decript, spam, complex, cifre, anagrame, balbe, criptmat, mesaj, maxim, astre, sablon, formule, ed, balls, vocale, prop, bacan, novel, bitslang, text2, ref, scor2, convert, cod2, compress, pstring, sub, rima, program1, sms, circular, randuri, cezar, bifo, joc9, pal, bare, joc12, fractie, cod3, tunel, top, ratina, cifru1, limbaj, adun, ecuatii, dir, paritate, virus, sir6, mesaj2, text1, sirul, ogorul, rez, sablon1, anag, sir8, seti, secvsir, dp, cuvant, strings, antipatie, fractie1, links, ordonare, text3, concat, codif, cheie, alfabetar, cuvinte2, comp, litere, mxl, mesaj3, expresie2, grad2, antic, zuma, expeval, combcuv, lgdrum, subtitrare, compresie, zigzag, azeval, fraze, subsecvente, showroom, rebus1, agenda, opmult, betisoare, reziston, clase, vot2, ecp, smiley, charlie, cript, scadere, spioni1, sablon3, expand, culori3, virgule
Despre recursivitate: tren, mere, chimie, sarpe, soldati, formule, infinit, compress, ploaia, cartoane, sub, metro, windows, lacuri, apel, maxq, pav, joc11, paianjen, suma2, monkey, lsort, imagine, dir, desert, echitabil, rez, logic, gradina, links, dreptunghiuri, expresie1, cumpanit, reziston, antitero, sablon3
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, flori2, cntgcd, 2sah, matcnt, nmult
Chestionare recomandate
surse trimise | ajutor