Короче задача на русском:-)
Перевод.
Пока еще путешествия и жизнь в космосе вопрос будущего, и нет причины начать планирование сейчас. Хотя кто раньше встал – того и тапки:-) мы хотим алгоритм, который наилучшим образом выберет расположение заправочных станций в космосе. Вкратце нужен алгоритм располагающий заправочные станции в наибольшей близости от жилых домов.
Более формально, каждый дом в космосе будет представлен тремя координатами (x,y,z). Мы собираемся построить k заправок(выбрать k (x,y,z) координат). Мы хотим построить заправки таким образом, чтобы сумма расстояний от домов до ближайшей заправки была минимальной.
Например, если дома в точках (1,1,1) , (2,2,2), (3,3,3) и (1,2,3),и мы должны построить две заправки. Одна может быть в (1.5, 1.5, 1.5) и вторая в (2,2.5,3). Расстояние от каждого из первых двух домов к ближайшей заправке(1.5,1.5,1.5) есть 0.87.Вторые два дома ближе ко второй заправке, расстояние 1.12. Сумма расстояний будет 3.97.
Вам будет дано до 500 000 точек, представляющих дома. Вы должны расположить до 100 заправок. Ваш результат будет базироваться на сумме расстояний и времени выполнения алгоритма. Для каждого тестового случая, ваше улучшение будет средним улучшением расстояния по сравнению с средним расстоянием от единичной заправки расположенной в координатах (500, 500, 500). Ваш результат будет это улучшение деленное на кубический корень умноженное на штраф - 1% вычтенный за каждую секунду выполнения алгоритма. Таким образом, если ваше среднее расстояние на 20 меньше , чем базовое среднее расстояние, k=8 и выполнение заняло 4 секунды, ваш результат будет 20/(8)1/3*0.96=9.6. Для вычислений конечного результата ваши индивидуальные тестовые случаи будут сложены и разделены на 100.
Вы должны написать метод, аргументами которого будут три вектора x,y,z и целое k. Вы должны вернуть вектор строк, каждый элемент, которого представляет заправку и отформатирован как “x y z”.
Все тестовые случаи будут генерированы следующим образом(если другое не указано, все случайные величины распределены равномерно и все границы включаются):
1. Число точек случайно выбрано от 100 до 500 000.
2. Случайное целое от 1 до 100 представляет число городов.
3. Центр города выбирается для каждого города. Каждый центр расположен случайным образом в отрезке координат от 0 до 1000.
4. Для каждого города, отклонение выбирается от 10 до 200.
5. Для каждой из N точек сопоставлен город выбранный случайно.
6. Используя центр города как центр Гауссова распределения с выбранным отклонением, координаты точек генерируются.
7. k выбирается случайно от 2 до 100.
Далее без перевода
Definition
Class: CentrallyLocated
Method: Place
Parameters: vector <double>, vector <double>, vector <double>, int
Returns: vector <string>
Method signature: vector <string> place(vector <double> x, vector <double> y, vector <double> z, int k)
(be sure your methodis public)
Замечания.
- Временный лимит для каждого тестового случая 50 сеекунд.
- Все вычисления будут проделаны, используя Java – double. Строки будут конвертированы, используя Double.parseDouble функцию. Любой формат, который работает с этой функцией разрешен.
- Минимальный счет для тестового случая – 0. Если ваше решение отрицательно, Вы получите 0.
- Будет 75 тестовых случаев.
- Предел памяти 1GB, предел многопоточности 32 потока.
- Гауссово распределение по трём измерениям – это просто независимые Гауссовы распределения для каждого из измерений. Таким образом для генерации точки, каждая из координат генерируется отдельно.
Ну, вот и все – далее примеры результатов – 9 штук, объём закачки около 63M.
Для участия в соревновании нужно иметь 18 лет. Шлите решения в приват – поделимся;-)