|
||||
| Zadanie: KrążkiDostę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. 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ę: 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.
ZadanieNapisz program, który:
WejściePierwszy wiersz wejścia zawiera dwie liczby całkowite n i m ( 1n, m300 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 ( 1ri1 000 000 000 dla 1in) 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 ( 1kj1 000 000 000 dla 1jm) oddzielonych pojedynczymi odstępami i oznaczających średnice kolejnych krążków, które Jaś zamierza wrzucić do rurki.
WyjściePierwszy 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ładDla danych wejściowych:7 3 5 6 4 3 6 2 3 3 2 5poprawną odpowiedzią jest: 2 Wersja do druku |