Pierwotek abstrakcyjny
Limit pamięci: 32 MB
Kod genetyczny pierwotka abstrakcyjnego (Primitivus recurencis) jest ciągiem liczb naturalnych, . Cechą pierwotka nazywamy każdą parę liczb , które występują kolejno w kodzie genetycznym, tzn. istnieje takie, że , . U pierwotków nie występują cechy postaci .
Zadanie
Napisz program, który:
- wczyta listę cech ze standardowego wejścia,
- obliczy najmniejszą długość najkrótszego kodu genetycznego pierwotka zawierającego podane cechy,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia liczba całkowita . Jest to liczba różnych cech pierwotka. W każdym z kolejnych wierszy znajduje się para liczb naturalnych i oddzielonych pojedynczym odstępem, , . Para jest jedną z cech pierwotka. Cechy w danych wejściowych nie powtarzają się.
Wyjście
Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia dokładnie jedną liczbę całkowitą, równą długości najkrótszego kodu genetycznego pierwotka zawierającego cechy podane na wejściu.
Przykład
Dla danych wejściowych:
12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6
poprawną odpowiedzią jest:
15
Wszystkie cechy z przykładu są zawarte np. w następującym kodzie genetycznym: (8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6).
Autor zadania: Wojciech Rytter.