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

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


Timp maxim de executie/test:
0.4 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Populatia planetei Algorithm este amenintata de virusi extrem de periculosi. Din fericire biologii de pe planeta au reusit sa analizeze structura genetica a virusilor si sa obtina o descriere completa a modului lor de evolutie. Astfel, nucleotidele ce compun structura ADN a unui virus pot fi notate cu cifrele de la 0 la 9 (0,1,2,3,4,5,6,7,8,9). Dintre acestea, unele sunt adulte si nu mai pot evolua (nu mai pot fi transformate), pe cand altele sunt inca tinere si mai pot evolua (mai pot fi transformate in alte nucleotide). Structura virusului este reprezentata de un sir de cifre (nucleotide) citit de la stanga catre dreapta.

Evolutia este o succesiune de pasi, fiecare dintre ei putand fi descris formal astfel: o nucleotida tinara se transforma in (este inlocuita de) alte doua nucleotide oarecare, sau in (de) exact o nucleotida adulta. Aceste transformari sunt determinate de niste reguli cunoscute de forma: “C se transforma in X Y” sau “C se transforma in X”; aceste reguli se pot traduce astfel: in sirul de cifre care reprezinta structura virusului, nucleotida C este stearsa, iar in locul sau sunt introduse nucleotidele XY (in aceasta ordine, X la stanga lui Y), respectiv de nucleotida X. S-a observat ca un sir de cifre reprezinta structura un virus daca si numai daca el poate fi obtinut prin aplicarea suucesiva a regulilor de evolutie asupra nucleotidei 0; orice alt sir reprezinta un alt organism. De asemenea este cunoscut faptul ca un virus a carui structura ADN contine doar nucleotide adulte este mai putin periculos ca un virus a carui structura ADN contine si nucleotide tinere.

Cerinta

Dandu-se lista nucleotidelor considerate adulte, regulile de evolutie si un sir care reprezinta structura ADN a unui organism, se cere sa se spuna daca acel sir poate reprezenta structura unui virus, caz in care trebuie precizat daca acest virus este format doar din nucleotide adulte sau daca are in componenta si nucleotide tinere.

Date de intrare

Fisierul de intrare contine pe prima linie un numar natural m care reprezinta numarul de nucleotide tinere. Pe cea de a doua linie se afla un sir de m cifre separate prin spatiu c1, c2, ..., cm care reprezinta cifrele care identifica nucleotidele tinere. Pe linia a treia se afla un numar natural n reprezentand numarul de reguli de evolutie ce urmeaza a fi descrise in fisier. Pe fiecare dintre urmatoarele n linii se afla cate un triplet sub forma
c11 c12 c13
c21 c22 c23
...
cn1 cn2 cn3

Daca regula j este de primul tip (i.e. o nucleotida tanara se poate transforma in alte doua nucleotide oarecare) atunci toate cele trei valori cj1, cj2 si cj3 sunt cifre care reprezinta nucleotide, cu semnificatia ca nucleotida cj1 se transforma in nucleotidele cj2 si cj3. Daca regula j este de al doilea tip (i.e. o nucleotida tinara se poate transforma in exact o nucleotida adulta) atunci cj1 si cj2 sunt cifre care reprezinta nucleotide (cu semnificatia ca nucleotida cj1 se transforma in nucleotida adulta cj2), iar cj3 este –1. Cele trei numere din fiecare triplet sunt separate prin spatiu.

Pe urmatoarea linie in fisierul de intrare se afla un numar natural k care reprezinta numarul de organisme a caror structura trebuie analizata. Pe urmatoarele k linii se afla k siruri de cifre, fiecare pe o linie noua; cele k siruri reprezinta structura a k organisme.

Date de iesire

Pentru fiecare dintre cele k siruri din fisierul de intrare, trebuie sa se afiseze, pe rand nou mesajul not a virus (in cazul in care sirul respectiv nu reprezinta structura unui virus), an adult virus (in cazul in care sirul respectiv reprezinta structura unui virus adult), a young virus (in cazul in care sirul respectiv reprezinta structura unui virus ce contine nucleotide tinere).

Restrictii si precizari

  • 1 <= m <= 9
  • 1 <= n <= 10
  • 1 <= k <= 20
  • Lungimea fiecarui sir dintre cele k este mai mica de 100 de cifre.
  • Nu este obligatoriu ca structura ADN a unui organism sa contina toate cele 10 cifre cu care pot fi reprezentate nucleotidele.
  • Datele sunt considerate valide.

Exemplu

bio.in

bio.out

3
0 1 2
5
0 1 2
1 1 1
2 2 2
1 3 -1
2 4 -1
5
33344444
33443344
11102222
3331444444
333533556

an adult virus
not a virus
not a virus
a young virus
not a virus


prep. Florin Manea
Facultatea de Matematica si Informatica, Universitatea din Bucuresti
Contact: flmanea@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, metro
De acelaşi autor: joc1, evo
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor