Sortowanie (Część 1)
Materiały
Dla nauczyciela
Dla ucznia
Zadania
Zadanie 1. Latarnie
Nie każdy lubi chodzić nocą ulicami, na których latarnie dają zbyt mało światła. Ciemności boi się również pan Integer. Wzdłuż ulicy, na której mieszka, postawiono \(k\) latarni. Pan Integer uważa, że jest ich stanowczo za mało. Albo za słabo świecą. Ponieważ zaplanowano właśnie wymianę wszystkich żarówek na nowe (energooszczędne), pan Integer postanowił zwrócić się do miejscowego zarządu dróg z nietypową prośbą. Chciałby, aby każda latarnia świeciła światłem z odpowiednią jasnością co najmniej o promieniu \(r\) tak, aby cała ulica była oświetlona. Nie chce przy tym narażać miasta na dodatkowe koszty, dlatego chce wyznaczyć \(r\) tak, by było jak najmniejsze. Pomożesz mu?
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite \(d\) oraz \(k\) – odpowiednio długość ulicy, na której mieszka pan Integer oraz liczba latarni (\(1 \leq k \leq d \leq 10^6\)). W kolejnej linii znajduje się \(k\) liczb całkowitych \(x_i\) – odległości \(i\)-tej latarni od początku ulicy (\(0 \leq x_i \leq d\)). Latanie mogą stać w dowolnym miejscu ulicy. W jednym miejscu znajduje się tylko jedna latarnia.
Wyjście
Minimalny promień światła \(r\), dla którego każdy punkt ulicy zostanie rozświetlony. Wynik wypisz z dokładnością do jednego miejsca po przecinku.
Przykład
| Wejście | Wyjście |
|---|---|
| 10 3 1 5 9 |
4.0 |
Wskazówka
Posortuj latarnie, a następnie znajdź dwie sąsiednie latarnie najbardziej oddalone od siebie.
Zadanie 2. Najczęściej występujący
Wyznacz najpopularniejszy element ciągu, to znaczy taki, który występuje w nim największą liczbę razy. W przypadku, gdy w ciągu jest więcej niż jeden najpopularniejszy element, podaj największy z nich.
Wejście
W jednej linii znajduje się ciąg liczb całkowitych zakończony liczbą \(0\). Liczb jest nie więcej niż \(1000000\), ich wartość mieści się w przedziale \([-10^{18}, 10^{18}]\).
Wyjście
Najpopularniejszy element ciągu.
Przykład
| Wejście | Wyjście |
|---|---|
| 1 2 -5 7 1 3 3 7 3 1 0 | 3 |
Wskazówka
Posortuj liczby i idąc od lewej, zliczaj te same wartości.
Zadanie 3. Ciąg Farey'a
Ciąg Farey’a dla liczby naturalnej \(N\) (\(N > 1\)) to ciąg ułamków, których licznik i mianownik są liczbami naturalnymi nieprzekraczającymi liczby \(N\) oraz licznik nie jest większy od mianownika. Ułamki powinny być skrócone, posortowane rosnąco i nie mogą się powtarzać. Oto przykład ciągu Farey’a dla \(N = 4\):
\(\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}\)
Napisz program, który czyta liczbę \(N\) i wypisuje odpowiadający jej ciąg Farey’a.
Wejście
Pierwszy i jedyny wiersz danych zawiera jedną liczbę naturalną \(N\) (\(3 \leq N \leq 1000\)).
Wyjście
Program powinien wypisać w jednym wierszu ciąg ułamków zapisanych przy użyciu znaku „/” (np. „1/2”) oddzielonych pojedynczymi odstępami, stanowiącymi ciąg Farey’a dla liczby \(N\).
Przykład
| Wejście | Wyjście |
|---|---|
| 4 | 0/1 1/4 1/3 1/2 2/3 3/4 1/1 |
Wskazówka
Do obliczenia wartości nieskracalnych ułamków przyda się __gcd z STL.