Fişierul intrare/ieşire:evo.in, evo.outSursăBaraj ONI 2006
AutorFlorin ManeaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.375 secLimită de memorie22096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Evo

Este binecunoscut faptul ca informatia genetica a unui organism poate fi codificata sub forma unui sir format din simboluri din multimea {g, a, t, c}. Pornind de la aceasta codificare, biologii au identificat 3 operatii asupra sirurilor de simboluri, operatii care pot modela evolutia anumitor organisme.

1. Complementaritate. Simbolul a este complementarul lui t (si reciproc), iar simbolul c este complementarul lui g (si reciproc). Pentru un simbol x vom nota cu c(x) complementarul sau. Prin extensie, daca w este un sir de simboluri din multimea {a, c, g, t} notam cu c(w) sirul obtinut prin complementarea simbolurilor lui w. De exemplu, pentru w=aaactg, avem c(w)=tttgac.
2. Oglindire. Vom nota prin wR sirul obtinut prin oglindirea lui w. De exemplu, pentru w=aaagatat, wR=tatagaaa.
3. Hairpin. Pentru un sir de simboluri w, care poate fi descompus in patru subsiruri w1w2w3w4 (unele dintre cele patru siruri pot fi vide) prin operatia hairpin se obtine: w1w2w3w4c(w1)R, daca w2=c(w4)R si lungimea lui w2 este mai mare sau egala cu 1, sau c(w4)Rw1w2w3w4, daca w1=c(w3)R si lungimea lui w1 este mai mare sau egala cu 1. 
Daca ambele conditii sunt verificate, oricare dintre cele doua siruri se poate obtine.

In gradina Acolor a fost descoperita o specie de omizi cu simt artistic. Informatia genetica a omizilor este codificata printr-o multime S formata din n siruri de simboluri din multimea {a, c, g, t}. Multimea S este denumita multime initiala. In evolutia omizilor, informatia genetica initiala a suferit o serie de modificari. Pentru omizi, toate aceste modificari pot fi descrise prin aplicarea operatiei hairpin de un numar arbitrar de ori asupra sirurilor din multimea initiala S.

Date fiind cele n siruri din multimea initiala S si o succesiune de m siruri de simboluri, sa se decida care dintre cele m siruri poate reprezenta codul genetic al unei omizi, cod obtinut prin aplicarea unor operatii hairpin.

Date de intrare

Fisierul de intrare evo.in contine n+m+2 linii. Pe prima linie este scris numarul natural n reprezentand numarul de siruri din multimea initiala S. Urmeaza n linii, pe fiecare linie fiind scris un sir din multimea S. Pe linia n+2 este scris numarul natural m, reprezentand numarul de siruri care trebuie sa fie analizate. Pe urmatoarele m linii sunt scrise cele m siruri care trebuie analizate, cate un sir pe o linie.

Date de iesire

Fisierul de iesire evo.out va contine m linii, cate una pentru fiecare sir de analizat. Pe linia i se va scrie cuvantul da, daca al i-lea sir dintre cele m siruri de analizat poate fi codul genetic al unei omizi, respectiv cuvantul nu, in caz contrar.

Restrictii

  • 0 < n < 5
  • 0 < m < 1001
  • Lungimea unui sir din multimea initiala S este mai mica decat 101.
  • Lungimea totala a sirurilor de analizat este mai mica decat 16001.
  • Lungimea fiecarui sir de analizat este mai mica decat 4001.
  • In 55% din teste lungimea maxima a unui sir de analizat este 700.

Exemplu

evo.inevo.out
2
acgtcg
gaaaat
4
gaaaat
gaaaatcc
gaaaattc
cgacgtcgtcg
da
nu
da
da

Explicatie

Primul sir de analizat este gaaaat. Acesta poate fi obtinut din gaaaat fara a aplica vreo operatie hairpin.
Al doilea sir de analizat este gaaatcc. Acesta nu poate fi obtinut prin aplicarea operatiei hairpin asupra sirurilor acgtcg sau gaaaat.
Al treilea sir de analizat este gaaaattc. Acesta se obtine aplicand operatia hairpin o singura data asupra sirului gaaaat (considerand w1=ga, w2=a, w3=aa, w4=t).
Al patrulea sir de analizat este cgacgtcgtcg. Acesta se poate obtine din acgtcg aplicand de doua ori operatia hairpin (din acgtcg obtinem cgacgtcg pentru w1=ac, w2=sir vid, w3=gt, w4=cg, operatia de hairpin adaugand c(w4)R la inceputul sirului, si apoi din cgacgtcg obtinem cgacgtcgtcg pentru w1=cga, w2=c, w3=gtc si w4=g, operatia de hairpin adaugand c(w1)R la sfarsitul sirului.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content