==Include(page="template/taskheader" task_id="adn")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
ADN
 
 
 
O problema importanta in ultimii ani in biologie a fost gasirea secventei de ADN pentru om. Un lant ADN este format din doua spirale de molecule, fiecare molecula fiind denumita pe scurt A, G, C sau T. Deci un lant ADN poate fi reprezentat ca un sir de caractere din multimea A, G, C si T. Poblema cercetatorilor este ca ei nu pot gasi intreaga secventa ADN cu metode chimice sau biologice dar pot determina sectiuni din ea. Dupa ce au determinat o serie de sectiuni, un sir de molecule care are probabilitatea cea mai mare sa fie apropiat de secventa reala este sirul cel mai scurt de caractere care contine toate sectiunile determinate ca subsecvente !
 
h2. Cerinta
 
Scrieti un program care sa-i ajute pe cercetatori sa determine cel mai scurt sir de caractere care contine toate sectiunile determinate ca subsecvente.
 
h2. Date de Intrare (fisier: adn.in)
 
Fisierul de intrare va contine pe prima linie va contine numarul N de secvente ADN iar pe urmatoarele N linii cate un sir de caractere ce contine numai literele A,G,C si T.
 
h2. Date de Iesire (fisier: adn.out)
 
Fisierul de iesire va contine o singura linie cu cel mai scurt sir ce contine secventele din intrare ca subsecvente.
 
h2. Restrictii
 
S 2 <= N <= 18
 
S Lungimea fiecarui sir este mai mica de 30.001
 
S Daca exista mai multe solutii de lungime minima se va afisa oricare
 
h2. Exemplu
 
adn.in
5
 
GGATATAAAAAC
 
GATAACCGCGCAGTGATGAGA
 
TGATGAGATGGGGATATAAAA
 
AGATAGATGATAACCGCGCAGT
 
ATGGGGATATAAAAACTTTTTT
adn.out
AGATAGATGATAACCGCGCAGTGATGAGATGGGGATATAAAAACTTTTTT
Explicatie
AGATAGATGATAACCGCGCAGT
 
GATAACCGCGCAGTGATGAGA
 
TGATGAGATGGGGATATAAAA
 
ATGGGGATATAAAAACTTTTTT
 
GGATATAAAAAC
 

==Include(page="template/taskheader" task_id="adn")==
 
O problema importanta in ultimii ani in biologie a fost gasirea secventei de ADN pentru om. Un lant ADN este format din doua spirale de molecule, fiecare molecula fiind denumita pe scurt A, G, C sau T. Deci un lant ADN poate fi reprezentat ca un sir de caractere din multimea A, G, C si T. Poblema cercetatorilor este ca ei nu pot gasi intreaga secventa ADN cu metode chimice sau biologice dar pot determina sectiuni din ea. Dupa ce au determinat o serie de sectiuni, un sir de molecule care are probabilitatea cea mai mare sa fie apropiat de secventa reala este sirul cel mai scurt de caractere care contine toate sectiunile determinate ca subsecvente!
 
h2. Cerinta
 
Scrieti un program care sa-i ajute pe cercetatori sa determine cel mai scurt sir de caractere care contine toate sectiunile determinate ca subsecvente.
 
h2. Date de Intrare
 
Fisierul de intrare $adn.in$ va contine pe prima linie va contine numarul $N$ de secvente ADN iar pe urmatoarele $N$ linii cate un sir de caractere ce contine numai literele A,G,C si T.
 
h2. Date de Iesire
 
Fisierul de iesire $adn.out$ va contine o singura linie cu cel mai scurt sir ce contine secventele din intrare ca subsecvente.
 
h2. Restrictii
 
* $2 ≤ N ≤ 18$
* Lungimea fiecarui sir este mai mica de $30.001$
* Daca exista mai multe solutii de lungime minima se va afisa oricare
 
h2. Exemplu
 
table(example). |_. adn.in |_. adn.out |
| 5
GGATATAAAAAC
GATAACCGCGCAGTGATGAGA
TGATGAGATGGGGATATAAAA
AGATAGATGATAACCGCGCAGT
ATGGGGATATAAAAACTTTTTT
| AGATAGATGATAACCGCGCAGTGATGAGATGGGGATATAAAAACTTTTTT |
 
h3. Explicatie
 
p(pre).. AGATAGATGATAACCGCGCAGT
        {*GATAACCGCGCAGT*}GATGAGA
                     {*TGATGAGA*}TGGGGATATAAAA
                            {*ATGGGGATATAAAA*}ACTTTTTT
                                {*GGATATAAAAAC*}
 
==Include(page="template/taskfooter" task_id="adn")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/adn/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="adn")==

216