Polish version    English version  
  O olimpiadzie -> Zadania


 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
XII Olimpiada Informatyczna 2004/2005

Zadanie: ska

Skarbonki

Zawody I stopnia  
Plik źródłowy: ska.xxx (xxx=pas,c,cpp)
Limit pamięci: 32 MB

Alternatywne formaty: PostScript | PDF

Smok Bajtazar ma N skarbonek. Każdą skarbonkę można otworzyć jej kluczem lub rozbić młotkiem. Bajtazar powrzucał klucze do pewnych skarbonek, pamięta przy tym który do której. Bajtazar zamierza kupić samochód i potrzebuje dostać się do wszystkich skarbonek. Chce jednak zniszczyć jak najmniej z nich. Pomóż Bajtazarowi ustalić ile skarbonek musi rozbić.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia liczbę skarbonek i rozmieszczenie odpowiadających im kluczy,
  • obliczy minimalną liczbę skarbonek, które trzeba rozbić, aby dostać się do wszystkich skarbonek,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita N (1 <= N <= 1.000.000) - tyle skarbonek posiada smok. Skarbonki (jak również odpowiadające im klucze) są ponumerowane od 1 do N. Dalej na wejściu mamy N wierszy: w i+1-szym wierszu zapisana jest jedna liczba całkowita - numer skarbonki, w której znajduje się i-ty klucz.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą - minimalną liczbę skarbonek, które trzeba rozbić, aby dostać się do wszystkich skarbonek. 

Przykład

Dla danych wejściowych:

4
2
1
2
4

prawidłową odpowiedzią jest:

2
W powyższym przykładzie wystarczy rozbić skarbonki numer 1 i 4.


Wersja do druku