VI Olimpiada Informatyczna 1998/99
|
Zadanie: PIE
|
Autor: Wojciech Rytter
|
Etap III, dzień drugi | 22 kwietnia 1999 |
Plik źródłowy: | PIE.??? (np. pas, c, cpp) |
Plik wykonywalny: | PIE.exe |
Plik wejściowy: | PIE.in |
Plik wyjściowy: | PIE.out |
Kod genetyczny pierwotka abstrakcyjnego (Primitivus recurencis) jest ciągiem liczb naturalnych, K=(a_1,...,a_n). Cechą pierwotka nazywamy każdą parę liczb (l,r), które występują kolejno w kodzie genetycznym, tzn. istnieje i takie, że l=a_i, r=a_i+1. U pierwotków nie występują cechy postaci (p,p).
Napisz program, który:
W pierwszym wierszu pliku wejściowego PIE.IN zapisana jest jedna dodatnia liczba całkowita n. Jest to liczba różnych cech pierwotka. W każdym z kolejnych n wierszy znajduje się para liczb naturalnych l i r oddzielonych pojedynczym odstępem, 1 <= l <= 1000, 1 <= r <= 1000. Para (l, r) jest jedną z cech pierwotka. Cechy w pliku wejściowym nie powtarzają się.
Twój program powinien zapisać w pierwszym i jedynym wierszu pliku tekstowego PIE.OUT dokładnie jedną liczbę całkowitą, równą długości najkrótszego kodu genetycznego pierwotka zawierającego cechy z pliku PIE.IN.
Dla pliku wejściowego PIE.IN
12 2 3 3 9 9 6 8 5 5 7 7 6 4 5 5 1 1 4 4 2 2 8 8 6poprawną odpowiedzią jest plik wyjściowy PIE.OUT
15Wszystkie cechy z pliku PIE.IN są zawarte np. w następującym kodzie genetycznym: