Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2362. Эстафета
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 22/10/2017 | Заочный онлайн-тур отборочных командных соревнований школьников Челябинской области (E) |
Ограничения: время – 500ms/1000ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для каждого спортсмена известно время прохождения первого этапа эстафеты 4x100м, когда он стартует с места,
и время прохождения остальных этапов (2-го, 3-го и 4-го), когда спортсмен уже бежит при передаче палочки.
Напишите программу, которая выберет четырех спортсменов и порядок расстановки их на этапы эстафеты,
обеспечивающий минимальное суммарное время прохождения эстафеты.
Первая строка ввода содержит одно целое число `N` (`4\ ≤\ N\ ≤\ 500`) – количество спортсменов, из которых нужно
выбрать четырех бегунов. Далее следует `N` строк, в каждой строке содержится уникальное имя спортсмена
(текст из прописных
латинских букв длиной от 2 до 20 символов) и два вещественных числа – время прохождения первого этапа `a_i` и
время прохождения последующих этапов `b_i` (`8\ ≤\ b_i\ ≤\ a_i\ <\ 20`). Все числа даны с двумя десятичными знаками.
В первой строке вывести минимальное суммарное время прохождения эстафеты с точностью `10^{-2}`.
В следующих четырех строках
вывести имена спортсменов в порядке их расстановки по этапам эстафеты. Если существует несколько
минимальных вариантов, то можно вывести любой из них.
Пример ввода
6 IVANOV 9.90 8.85 PETROV 9.69 8.72 FOMIN 9.58 8.43 EGOROV 9.78 8.93 MISHIN 9.88 8.92 NIKOLAEV 9.72 8.61
Пример вывода
35.54 EGOROV FOMIN NIKOLAEV PETROV
