Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTWPZ075 - PTwPZ Zabawa z DNA

Zabawa z DNA

Treść

Szalony naukowiec Adalbert zafascynował się ostatnimi czasy biologią molekularną. W szczególności interesują go łańcuchy DNA i to, co w wyniku ich modyfikacji można osiągnąć. Do pracy nad nimi skonstruował specjalną machinę. Posiada ona zasobnik nukleotydów i łańcuchów cząstkowych oraz moduł rozcinająco-klejący. W pojedynczym kroku machina rozcina konstruowany łańcuch, wybiera nukleotyd lub łańcuch cząstkowy z zasobnika i wkleja go w rozcięte miejsce. Dzięki niej Adalbert może skonstruować dowolny łańcuch DNA. Ze względu na to, iż kontrolowane eksperymenty nie przyniosły ciekawych rezultatów, naukowiec postanowił pójść na żywioł i konstruować łańcuchy losowo. Napisał specjalny program generujący ciągi rozkazów dla machiny. Pojedynczy taki rozkaz składa się z dwóch części: wklejanego łańcucha cząstkowego (lub pojedynczego nukleotydu) oraz miejsca jego wklejenia. Tym razem wyniki eksperymentów przeszły oczekiwania samego Adalberta. Niestety wraz z sukcesem pojawił się problem. Naukowiec nie potrafi teraz odtworzyć pełnego kodu łańcucha. To zadanie zlecił swemu zaufanemu asystentowi, czyli Tobie. Napisz program, który dla podanej sekwencji rozkazów wypisze kod wygenerowanego przez machinę łańcucha DNA.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

W pierwszym wierszu zestawu danych znajduje się liczba całkowita n (1<=n<=200000) rozkazów dla machiny. W kolejnych n wierszach podane są rozkazy. Na jeden rozkaz składa się nieujemna liczba całkowita mi oraz ciąg złożony z wielkich liter A, G, C lub T, oddzielone spacją. Ciąg liter odpowiada wstawianemu łańcuchowi cząstkowemu, a liczba mi miejscu jego wklejenia, przy czym rozcięcie następuje bezpośrednio po mi-tym nukleotydzie łańcucha uzyskanego w i - 1 kroku. Wartość mi równa 0 oznacza, że łańcuch cząstkowy jest wstawiany na początek istniejącego. Początkowo, przed pierwszym rozkazem, konstruowany łańcuch jest pusty. Suma długości wszystkich łańcuchów cząstkowych nie przekracza 200000 nukleotydów.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest ciąg liter odpowiadający wygenerowanemu przez machinę łańcuchowi DNA.

Przykład

dane wejściowe:
2
3
0 AAA
2 TT
1 CC
6
0 AAAT
3 CC
1 GG
4 TT
2 AA
0 CC

wynik:
ACCATTA
CCAGAAGATTACCT


Dodane przez:Michael Suchacz
Data dodania:2009-07-26
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:Podlaski Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.