evo

Evo

3. *Hairpin*. Pentru un sir de simboluri $w$, care poate fi descompus in patru subsiruri $w{~1~}w{~2~}w{~3~}w{~4~}$ (unele dintre cele patru siruri pot fi vide) prin operatia hairpin se obtine: $w{~1~}w{~2~}w{~3~}w{~4~}c(w{~1~})^R^$, daca $w{~2~}=c(w{~4~})^R^$ si lungimea lui $w{~2~}$ este mai mare sau egala cu $1$, sau $c(w{~4~})^R^w{~1~}w{~2~}w{~3~}w{~4~}$, daca $w{~1~}=c(w{~3~})^R^$ si lungimea lui $w{~1~}$ 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 initială 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$.

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.

h2. 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$, în caz contrar.

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.

h2. Restrictii

h3. 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 $gaaattc$. Acesta nu poate fi obtinut prin aplicarea operatiei hairpin asupra sirurilor $acgtcg$ sau $gaaaat$.

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 $w{~1~}=ga$, $w{~2~}=a$, $w{~3~}=aa$, $w{~4~}=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 $w{~1~}=ac$, $w{~2~}=sir vid$, $w{~3~}=gt$, $w{~4~}=cg$, operatia de hairpin adaugand $c(w{~4~})^R^$ la inceputul sirului, si apoi din $cgacgtcg$ obtinem $cgacgtcgtcg$ pentru $w{~1~}=cga$, $w{~2~}=c$, $w{~3~}=gtc$ si $w{~4~}=g$, operatia de hairpin adaugand $c(w{~1~})^R^$ la sfarsitul sirului.
== include(page="template/taskfooter" task_id="evo") ==

2261