Polish version    English version  
  O olimpiadzie -> Zadania -> XIII OI 2005/2006


 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

Zadanie: Krążki


Dostępna pamięc: 32MB

Mały Jaś dostał od rodziców na urodziny nową zabawkę, w której skład wchodzą rurka i krążki. Rurka ma nietypowy kształt -- mianowicie jest to połączenie pewnej liczby walców (o takiej samej grubości) z wyciętymi w środku (współosiowo) okrągłymi otworami różnej średnicy. Rurka jest zamknięta od dołu, a otwarta od góry. Na poniższym rysunku przedstawiono przykładową taką rurkę, złożoną z walców, w których wycięto otwory o średnicach kolejno: 5cm, 6cm, 4cm, 3cm, 6cm, 2cm i 3cm.

\includegraphics{kra1}% WIDTH=277 HEIGHT=162
Krążki w zabawce Jasia są walcami o różnych średnicach i takiej samej grubości co walce tworzące rurkę.

Jaś wymyślił sobie następującą zabawę. Mając do dyspozycji pewien zestaw krążków zastanawia się, na jakiej wysokości zatrzymałby się ostatni z nich, gdyby wrzucał je kolejno do rurki centralnie (czyli dokładnie w jej środek). Dla przykładu, gdyby wrzucić do powyższej rurki krążki o średnicach kolejno 3cm, 2cm i 5cm, to otrzymalibyśmy następującą sytuację:

\includegraphics{kra2}% WIDTH=277 HEIGHT=162
Jak widać, każdy kolejny krążek po wrzuceniu spada dopóki się nie zaklinuje (czyli nie oprze się o walec, w którym wycięty jest otwór o mniejszej średnicy niż średnica krążka), albo nie natrafi na przeszkodę w postaci innego krążka lub dna rurki.

Ponieważ zabawa ta jest trudna dla małego Jasia, to ciągle prosi swoich rodziców o pomoc. A jako że rodzice Jasia nie lubią takich zabaw intelektualnych, to poprosili Ciebie -- znajomego programistę -- o napisanie programu, który zamiast nich będzie udzielał odpowiedzi Jasiowi.

Zadanie

Napisz program, który:
  • wczyta ze standardowego wejścia schemat rurki i opis krążków jakie Jaś będzie wrzucał do rurki,
  • wyznaczy głębokość, na jakiej zatrzyma się ostatni wrzucony przez Jasia krążek,
  • wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite nm ( 1$ \le$% WIDTH=16 HEIGHT=30 n, m$ \le$% WIDTH=16 HEIGHT=30 300 000), oddzielone pojedynczym odstępem i oznaczające wysokość rurki Jasia (liczbę walców wchodzących w jej skład) i liczbę krążków, które zamierza wrzucić do rurki. Drugi wiersz wejścia zawiera n liczb całkowitych r1, r2,...rn ( 1$ \le$% WIDTH=16 HEIGHT=30 ri$ \le$% WIDTH=16 HEIGHT=30 1 000 000 000 dla 1$ \le$% WIDTH=16 HEIGHT=30 i$ \le$% WIDTH=16 HEIGHT=30 n) oddzielonych pojedynczymi odstępami i oznaczających średnice otworów wyciętych w kolejnych (od góry) walcach tworzących rurkę. Trzeci wiersz wejścia zawiera m liczb całkowitych k1, k2,..., km ( 1$ \le$% WIDTH=16 HEIGHT=30 kj$ \le$% WIDTH=16 HEIGHT=30 1 000 000 000 dla 1$ \le$% WIDTH=16 HEIGHT=30 j$ \le$% WIDTH=16 HEIGHT=30 m) oddzielonych pojedynczymi odstępami i oznaczających średnice kolejnych krążków, które Jaś zamierza wrzucić do rurki.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą głębokość zatrzymania się ostatniego krążka. Jeżeli krążek ten w ogóle nie wpadnie do rurki, to odpowiedzią powinna być liczba 0.

Przykład

Dla danych wejściowych:
7 3
5 6 4 3 6 2 3
3 2 5
poprawną odpowiedzią jest:
2





Wersja do druku