Polish version    English version  
  XVIII OI 2010/2011


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
Terminarz
Zadania
II Etap
Przepisy
Wyniki I etapu
Wyniki II etapu
Dla zawodników
Przydatne zasoby
 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: sam

Samochodziki

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

Alternatywne formaty: PostScript | PDF

Jasio jest trzylatkiem i bardzo lubi bawić się samochodzikami. Jasio ma n różnych samochodzików. Wszystkie samochodziki leżą na wysokiej półce, do której Jasio nie dosięga. W pokoju jest mało miejsca, więc na podłodze może znajdować się jednocześnie co najwyżej k samochodzików.

Jasio bawi się jednym z samochodzików leżących na podłodze. Oprócz Jasia w pokoju cały czas przebywa mama. Gdy Jasio chce się bawić jakimś innym samochodzikiem i jeśli ten samochodzik jest na podłodze, to sięga po niego. Jeśli jednak samochodzik znajduje się na półce, to musi mu go podać mama. Mama podając Jasiowi jeden samochodzik, może przy okazji zabrać z podłogi dowolnie wybrany przez siebie inny samochodzik i odłożyć go na półkę (tak, aby na podłodze nie brakło miejsca).

Mama bardzo dobrze zna swoje dziecko i wie dokładnie, którymi samochodzikami Jasio będzie chciał się bawić. Dysponując tą wiedzą mama chce zminimalizować liczbę przypadków, gdy musi podawać Jasiowi samochodzik z półki. W tym celu musi bardzo rozważnie odkładać samochodziki na półkę.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia ciąg kolejnych samochodzików, którymi będzie chciał się bawić Jasio,
  • obliczy minimalną liczbę przypadków zdejmowania przez mamę samochodzików z półki,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite: n, k, p (1 <= k <= n <= 100.000, 1 <= p <= 500.000), pooddzielane pojedynczymi odstępami. Są to kolejno: łączna liczba samochodzików, liczba samochodzików mogących jednocześnie znajdować się na podłodze oraz długość ciągu samochodzików, którymi będzie chciał się bawić Jasio. W kolejnych p wierszach znajduje się po jednej liczbie całkowitej. Są to numery kolejnych samochodzików, którymi będzie chciał się bawić Jasio (samochodziki są ponumerowane od 1 do n ). 

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą - minimalną liczbę przypadków podania samochodzika z półki przez mamę.

Przykład

Dla danych wejściowych:

3 2 7
1
2
3
1
3
1
2

prawidłową odpowiedzią jest:

4



Wersja do druku