Wyszukiwanie binarne po wyniku
Materiały
Dla nauczyciela
Dla ucznia
Wyszukiwanie binarne po wyniku (MAIN2)
Zadania
Zadanie 1. Zawody wędkarskie
Jasio organizuje zawody wędkarskie. Dokonał właśnie przeglądu wszystkich \(n\) stanowisk, jakimi dysponuje. Stanowiska umiejscowione są w linii prostej nad jeziorem w odległościach \(x_1, x_2, \dots, x_n\) od początku jeziora. W czasie konkursu zawodnicy nie mogą sobie nawzajem przeszkadzać. Dlatego Jaś chciałby teraz tak rozmieścić w wędkarzy, aby najmniejsza odległość pomiędzy dwoma najbliższymi z nich była jak największa. Pomóż znaleźć Jasiowi taki rozkład wędkarzy.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite: \(n\) oraz \(w\) (\(2 \leq w \leq n \leq 10^6\)). W kolejnej linii znajduje się \(n\) liczb całkowitych \(x_i\) (\(0 \leq x_i \leq 10^9\), \(x_i − 1 < x_i\)). Każda z wartości oznacza odpowiednio odległość \(i\)-tego stanowiska od początku jeziora.
Wyjście
Jedna liczba całkowita wyznaczająca najlepszą możliwą odległość pomiędzy dwoma najbliższymi stanowiskami.
Przykład
| Wejście | Wyjście |
|---|---|
| 6 3 2 5 10 13 18 19 |
8 |
Wskazówka
Zapisz odległości pomiędzy kolejnymi stanowiskami zamiast odległości od początku jeziora.
Zadanie 2. Marchewki
Bitomir zasadził na swoim polu marchewki. Każda marchewka jest oddalona od innej marchewki o jeden bitometr (jednostka długości w Bajtocji) w poziomie i w pionie. Bitomir chce zakupić specjalny zbierak do marchewek. Zbierak zamontowany jest na długim ramieniu i potrafi zebrać wszystkie marchewki w promieniu swojego działania. Bitomir zastanawia się teraz, jakiej długości ramię (w bitometrach) musi posiadać zbierak, by jednorazowo zebrał co najmniej m marchewek. Cena zbieraka zależy od długości ramienia. Bitomir chce zakupić jak najtańsze urządzenie. Pomóż mu wyznaczyć najlepszy zbierak!
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowita \(m\) (\(2 \leq m \leq 5 \cdot 10^{12}\)), oznaczająca liczbę marchewek, którą chcemy jednorazowo zebrać.
Wyjście
Na wyjściu powinna znaleźć się jedna liczba całkowita oznaczająca minimalną długość ramienia zbieraka.
Przykład
| Wejście | Wyjście |
|---|---|
| 13 | 2 |
Wskazówka
W każdym kwadracie o boku \(2r\) obliczamy liczbę marchewek wewnątrz koła o promieniu \(r\).