|
|||||||||
|
Zadanie: ska
Skarbonki
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ć. ZadanieNapisz program, który:
WejścieW 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ścieW 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ładDla danych wejściowych: 4 2 1 2 4 prawidłową odpowiedzią jest: 2W powyższym przykładzie wystarczy rozbić skarbonki numer 1 i 4. Wersja do druku |