W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.