Wyszukiwanie binarne
Materiały
Dla nauczyciela
Dla ucznia
Zadania
Zadanie 1. Znaczki
Bitek i Bajtek zbierają znaczki. Bitek planuje wziąć udział w wystawie połączonej z konkursem na największy zbiór znaczków. Aby zwiększyć swoje szanse na odniesienie spektakularnego sukcesu, postanowił pożyczyć od Bajtka te znaczki, których sam nie posiada. Chciałby teraz wiedzieć, o ile znaczków zwiększy się jego kolekcja.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby naturalne \(n\) ($ 1 \leq n \leq 100 000\() i \(m\) (\) 1 \leq m \leq 10 000 000$), oznaczające odpowiednio liczbę znaczków Bitka oraz znaczków Bajtka. W drugiej linii wejścia znajduje się \(n\) różnych liczb naturalnych mniejszych niż \(10^9\) – typy znaczków Bitka. W trzeciej linii wejścia znajduje się \(m\) różnych liczb naturalnych mniejszych niż \(10^9\) – typy znaczków Bajtka. Możesz założyć, że w Bitek i Bajtek podali każdy posiadany znaczek tylko raz.
Wyjście
W jedynym wierszu wyjścia znajduje się jedna liczba całkowita: liczba znaczków w kolekcji Bajtka, których nie posiada Bitek.
Przykład
| Wejście | Wyjście |
|---|---|
| 6 4 1 2 3 4 5 6 2 4 5 7 |
1 |
Wskazówka
Posortuj pierwsze \(n\) znaczków i wyszukuj binarnie w drugim zbiorze.
Zadanie 2. Tunele
Janek zarządza dużą firmą dostawczą. Właśnie zamierza opracować nowy plan dostaw do swoich kontrahentów. Do wszystkich można dojechać nowo wybudowaną autostradą. Niestety samochody na autostradzie muszą pokonywać również tunele. Każdy z samochodów oraz każdy z tuneli ma określoną wysokość. Aby ciężarówka Janka przejechała pod tunelem, musi być niższa niż wysokość tunelu. Janek zna wysokości ciężarówek i tuneli i zastanawia się, do którego miejsca autostrady dojedzie każde z jego aut.
Wejście
W pierwszej linii wejścia znajduje się dwie liczby całkowite \(a\) i \(b\) (\(1 \leq a, b \leq 500 000\)), odpowiednio ilość tuneli i samochodów. W drugiej linii znajduje się a oddzielonych spacjami liczb całkowitych \(t_1, t_2, \dots, t_a\) (\(1 \leq t_i \leq 1 000 000 000\)), gdzie \(t_i\) oznacza wysokość \(i\)-tego tunelu. W trzeciej linii znajduje się \(b\) oddzielonych spacjami liczb całkowitych \(s_1, s_2, \dots, s_b\) (\(1 \leq s_i \leq 1 000 000 000\)), gdzie \(s_i\) oznacza wysokość \(i\)-tego samochodu.
Wyjście
Pierwszy i jedyny wiersz wyjścia zawiera \(b\) liczb całkowitych \(d_1, d_2, \dots, d_i\), gdzie \(d_i\) oznacza numer ostatniego tunelu, przez który może przejechać \(i\)-ty samochód lub \(0\), jeśli nie może przejechać przez żaden z tuneli.
Przykład
| Wejście | Wyjście |
|---|---|
| 5 3 8 6 5 7 9 4 7 9 |
5 1 0 |
Wskazówka
Przez kolejny tunel może przejechać samochód równy jego wysokości (minus jeden), jeżeli po lewej jego stronie nie znajdzie się żaden niższy tunel.
Zadanie 3. Bierki
Jaś lubi budować trójkąty z bierek. W tym celu trzyma je w worku, z którego wybiera trzy bierki na chybił-trafił. Bierki mogą mieć różne długości i nie zawsze Jaś może zbudować trójkąt, a wtedy wpada w histerię. Mama Jasia ma dość histerycznych napadów synka i dlatego poprosiła Ciebie o pomoc. Należy odrzucić niektóre bierki w taki sposób, aby z pozostałych zawsze dało się ułożyć trójkąt, jednocześnie zostawiając jak najwięcej bierek w worku.
Opracuj program, który:
- wczyta ze standardowego wejścia liczbę bierek w worku oraz ich długości,
- obliczy największą liczbę bierek, którą można pozostawić w worku, tak żeby z każdych trzech z nich można było utworzyć trójkąt,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu zapisano liczbę \(n\) (\(5 \leq n \leq 30 000\)), oznaczającą liczbę bierek w worku. W każdym z \(n\) następnych wierszy zapisano długość jednej bierki. Długość bierki jest liczbą całkowitą z przedziału \([1, 500]\).
Wyjście
W pierwszym wierszu wypisz liczbę bierek, które powinny zostać w worku.
Przykład
| Wejście | Wyjście |
|---|---|
| 10 7 1 2 8 10 6 1 7 9 9 |
7 |
Wskazówka
Na początku posortuj bierki. Dla każdej bierki możesz wyszukiwać binarnie wielkość zbioru wynikowego.