In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Szalony naukowiec Bajtazar chciałby stworzyć nowy gatunek zwierząt. W tym celu postanowił zmodyfikować kod DNA myszy bajtockiej.
Kod DNA to ciąg znaków składający się z liter A, C, G oraz T.
Plan Bajtazara jest następujący.
Weźmie on DNA myszy i na jego podstawie stworzy nowy kod o tej samej długości, który będzie jak najmniej podobny do kodu myszy.
Podobieństwo dwóch kodów DNA to długość ich najdłuższego wspólnego podciągu.
Najdłuższy wspólny podciąg dwóch słów i
to najdłuższe słowo, które można uzyskać z każdego ze słów
,
przez usuwanie liter.
(Zwróć uwagę, że dwa słowa mogą mieć wiele najdłuższych wspólnych podciągów, na przykład
najdłuższe wspólne podciągi słów CACCA i CAAC to CAA oraz CAC.)
Napisz program, który wyznaczy szukany kod DNA.
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (
) oznaczającą długość kodu DNA myszy bajtockiej.
W drugim wierszu znajduje się kod DNA myszy w postaci ciągu
wielkich liter należących do zbioru
.
Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą - podobieństwo kodu myszy bajtockiej oraz kodu znalezionego przez Twój program.
W drugim wierszu należy wypisać ciąg składający się z liter A, C, G lub T.
Powinien być to kod DNA, który jest jak najmniej podobny do kodu podanego na wejściu.
Jeśli istnieje wiele poprawnych odpowiedzi, Twój program może wypisać dowolną z nich.
Dla danych wejściowych:
4 GACT
jednym z poprawnych wyników jest:
1 TCAG
Autor zadania: Jakub Łącki.