Polish version    English version  
  Historia OI -> XII OI 2004/2005


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 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