Polish version    English version  
  O olimpiadzie -> Zadania -> VI OI 1998/1999


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VI Olimpiada Informatyczna 1998/99

Zadanie: PIE
Autor: Wojciech Rytter
Pierwotek abstrakcyjny

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).

Zadanie

Napisz program, który:

  • wczyta listę cech z pliku tekstowego PIE.IN,
  • obliczy najmniejszą długość najkrótszego kodu genetycznego pierwotka zawierającego podane cechy,
  • zapisze wynik w pliku tekstowym PIE.OUT.

Wejście

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ę.

Wyjście

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.

Przykład

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 6
poprawną odpowiedzią jest plik wyjściowy PIE.OUT
15
Wszystkie cechy z pliku PIE.IN są zawarte np. w następującym kodzie genetycznym:
(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)




Wersja do druku