UniLecs #149_1. Pit-stops
UniLecsЗадача: на кольцевом треке расположены N пит-стопов. Если у спорткара случилась поломка или закончилось топливо, то пилот может доехать до ближайшего пит-стопа (можно сдать назад до питстопа, если он находится ближе всех).
Необходимо определить максимально возможное расстояние до ближайшего питстопа в случае поломки или нехватки топлива.
Входные данные: pitstops[] - массив позиций пит-стопов, Dist - общая дистанция трека.
Вывод: максимально возможное расстояние до ближайшего пит-стопа.
Пример: pitstops = [4.5, 0.5, 2, 1], Общая дистанция трека = 5.
Answer = 1.25
Реализация:
- @akolosov364, JS, Rust: 1.1 балла
Наибольшее расстояние до ближайшего питстопа будет наибольшее растояние между двумя питстопами пополам, т.к. трасса круговая стоит добавить ещё 1 точку, а именно расстояние между первым и последним питстопом и произвести расчет.
https://gist.github.com/KolosovAO/1796cf880f0bb1d78990638b6c22996a
Test JS: https://repl.it/@AlieksieiKoloso/task149
Test Rust: https://repl.it/@AlieksieiKoloso/task149rust
2. @jinxonik, Ruby: (1 + 3*0.5 + 17*0.1) = 4.2 балла
Краткое описание методов:
1. Сортировка, перебор значений с получением разницы (на первой итерации вычисляется разница между последним пит-стопом первого круга и первым второго круга). 1 - прямая сортировка, 1A - обратная сортировка (другое вычисление на 1-й итерации), 1B - прямая сортировка + обратный перебор индексов (downto).
2. Сортировка, добавление первого пит-стопа второго круга в массив (чтобы не вычислять "по ходу", как в методе №1), перебор соседних пар с получением разницы. 2° - each_cons, 2°A - inject, 2°B - обычный цикл.
2¹. Обратная сортировка, корректировка (чтобы первый пит-стоп был на старте), перебор соседних пар с получением разницы. Без добавления доп. элемента в массив. 2¹ - each_cons, 2¹A - inject, 2¹B - обычный цикл.
2². Сортировка, корректировка (чтобы последний пит-стоп был на фишине), перебор с получением разницы. Также без добавления доп. элемента в массив. 2² - each_cons, 2²A - inject, 2²B - обычный цикл.
3. Добавление первого пит-стопа второго круга в массив, перебор всех пар с вычислением разницы между пит-стопами. Без сортировки. 3 - combination, 3A - permutation, 3B - вложенные циклы.
4°. Поэтапное вычитание двух максимальных элементов с последующим их удалением из массива. 4° - вычитание максимальных элементов, 4°A - вычитание минимальных элементов, 4°B - вычитание и максимальных, и минимальных элементов.
4¹. Поэтапное вычитание двух максимальных элементов без удаления их из массива.
4¹ - вычитание максимальных элементов, 4¹A - вычитание минимальных элементов, 4¹B - вычитание и максимальных, и минимальных элементов.
https://gist.github.com/jin-x/44faa9c2c806f3f80018abd083527d46
3. @kirillmotrichkin, Python: 1 балл
Сортируем массив, потом проходим по массиву и ищем самый большой интервал, а потом не забываем про интервал "через старт".
https://gist.github.com/superkiria/a559d8547a13840e475c35f5aaf65f6b
Test: https://repl.it/@superkiria/unilecs149
4. @egormasharskii, С++: 1 балл
Сортируем по координате, а потом обходим все пары последовательных остановок и находим максимальное расстояние. Не забываем поделить его пополам.
https://gist.github.com/myegor/826cf00f182b0be09dcedbebb36981f8
Test: http://cpp.sh/4nl2l
5. Антон, Rust, C, С++, C#, Haskell, Go, Python: 1 + 0.5 + 6*0.1 = 2.1 балла
Т. о., чтобы найти глобальный максимум расстояния до ближайшего пит-стопа, нужно выбрать максимальную дистанцию между соседними пит-стопами и взять от неё половину. Немного более внимательного отношения требует последняя позиция, т. к. следующий пит-стоп для неё — первый в списке.
Rust: https://gist.github.com/AnthonyMikh/80c54a75422d1268d795e10315594ceb
Test Rust: https://gist.github.com/AnthonyMikh/80c54a75422d1268d795e10315594ceb
https://gist.github.com/AnthonyMikh/d92a13887690910aea9d5acd0e7ec51e
Test (C): https://repl.it/repls/DarkPristineEnterprise
Test (C++): https://repl.it/repls/ComposedWeakSpreadsheets
Test (C#): https://repl.it/repls/PeruMountainousFtpclient
Test (Go): https://goplay.space/#_86P_twlOHv
Test (Haskell): https://repl.it/repls/OpulentSilentDehardwarization
Test (Python): https://repl.it/repls/TimelyFuzzyOutcome
6. @voodoo_woodpecker, VBA, JS, Python, R: 1 + 2*0.5 + 3*0.1 = 2.3 балла
Первый метод -- самое простое решение, сортируем список питстопов и идём по нему. Рассчитываем растояния между соседними питстопами и запоминаем максимальное. Возвращаем 1/2 этого расстояния, так как можно двигаться и вперёд и назад.
Второй метод -- вместо сортировки списка создаём список сортированых индексов, то есть позиция i в списке показывает на i по величине элемент массива. Например список [1,3,2] -> индексы сортированного списка [0,2,1]. Далее аналогично проходжим по массиву и вычисляем расстояния, выбирая максимальное.
Третий метод -- без использования сортировки. Вынимаем из списка питстопов минимальный питстоп и рассчитываем расстояние между ним и предыдущим питстопом, запоминаем максимальное.
https://gist.github.com/MikePeleah/b8c68103682347fb807d03c75ba95bb0