== include(page="template/taskheader" task_id="evo") ==
Poveste si cerinta...
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 $w^R^$ sirul obtinut prin oglindirea lui $w$. De exemplu, pentru $w=aaagatat$, $w^R^=tatagaaa$.
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 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 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.
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$, in caz contrar.
h2. 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$.
h2. Exemplu
table(example). |_. evo.in |_. evo.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|2
acgtcg
gaaaat
4
gaaaat
gaaaatcc
gaaaattc
cgacgtcgtcg
|da
nu
da
da
|
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 $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") ==
