Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie DNA (dna)

DNA

Limit pamięci: 128 MB

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.

Wejście

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 .

Wyjście

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.

Przykład

Dla danych wejściowych:

4
GACT

jednym z poprawnych wyników jest:

1
TCAG

Autor zadania: Jakub Łącki.