| Fişierul intrare/ieşire: | evo.in, evo.out | Sursă | Baraj ONI 2006 |
| Autor | Florin Manea | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.375 sec | Limită de memorie | 22096 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | evo.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.
