XII Olimpiada Informatyczna 2004/2005
|
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ć.
Napisz program, który:
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.
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.
Dla danych wejściowych:
4 2 1 2 4
prawidłową odpowiedzią jest:
2W powyższym przykładzie wystarczy rozbić skarbonki numer 1 i 4.