Задача 64: Олимпиада (XIII Всероссийская олимпиада по информатике)
Оргкомитет Всероссийской олимпиады по
информатике выделил для некоторой области два места для участников.
Однако на олимпиаду поехала делегация из N школьников.
Представители Оргкомитета при встрече на вокзале выдали членам
делегации два бейджа. По Положению об олимпиаде для участия в ней
надо зарегистрироваться во Дворце молодежи, куда можно пройти только
по бейджам.
Для того чтобы все члены делегации проникли во Дворец молодежи, один
из них предложил действовать следующим образом. Двое из членов
делегации проходят с бейджами через пункт контроля, а затем кто-то
из членов этой делегации, уже проникших во Дворец, тайно выносит оба
бейджа назад на улицу. Эта процедура повторяется до тех пор, пока не
пройдут все делегаты от этой области.
Известно, что i-й делегат тратит на проход через пункт контроля ti
секунд, включая выход на улицу. Для прохода одной пары делегатов
требуется время, равное времени прохода менее расторопного из этой
пары.
Для каждого члена делегации время, требуемое для выхода из здания,
такое же, как и для входа.
Требуется
Написать программу, определяющую, за какое наименьшее время и каким
образом все делегаты области смогут проникнуть во Дворец молодежи.
Входные данные
В первой строке входного файла OLYMP.IN задается натуральное число N
(2 <= N <= 1000).
В последующих N строках находятся натуральные числа t1 , t2 , ...,
tN (по одному в строке) - времена прохода членов делегации через
пункт контроля в секундах, 1 <= ti <= 10 000.
Выходные данные
В первой строке выходного файла OLYMP.OUT необходимо выдать
наименьшее возможное время (в секундах), через которое вся делегация
окажется во Дворце молодежи.
В последующих строках указывается какой-нибудь порядок прохода
членов делегации за это наименьшее время, а именно тройки целых
чисел, из которых первые два задают номера членов делегации,
проходящих во Дворец, а третье - номер члена делегации, выносящего
из Дворца два бейджа. В последней строке указываются только два
числа - номера членов делегации, проходящих во Дворец последними.
Все числа разделяются пробелами.
Пример входного файла
3
5
5
10
Пример выходного файла для приведенного примера входного
файла
20
1 2 2
2 3
Решение: предоставлено
Е.В. Андреевой
При решении поставленной задачи можно действовать исходя из двух
разумных соображений. Либо самый быстрый член делегации проводит
через пропускной пункт всех остальных, причем в любом порядке
(назовем этот способ стратегией А), либо два самых медленных члена
делегации проходят во Дворец вместе, а бейджи затем вынесет один из
двух наиболее быстрых школьников, прошедших во Дворец ранее
(стратегия В), после чего задача сводится к той же, но размерностью
на 2 меньше. Используя перестановочный прием, можно проверить, что
любой другой порядок прохода делегации в здание можно улучшить,
заменяя его на комбинацию этих двух стратегий. Остается определить,
в какой комбинации следует применять стратегии А и В в том или ином
случае.
Для определенности отсортируем времена прохода членов делегации
через контроль по неубыванию. Теперь можно говорить, что наиболее
быстрым является первый член делегации, а наиболее медленным -
последний. Так как для стратегии А порядок прохода членов делегации
в паре с первым не важен, а в стратегии В, наоборот, сначала надо
организовать совместный проход двух самых медленных участников, то
выбор начальной стратегии нужно проводить, сравнивая результирующее
время прохода во Дворец двух самых медленных участников в каждом из
двух случаев. В стратегии А это время равно tN + t1 + tN-1 + t1 (два
самых медленных участника окажутся по очереди во Дворце, а самый
быстрый вернется к делегации), а в стратегии В - t2 + t1 + tN + t2
(два самых быстрых участника проходят во дворец, затем первый
возвращается и через контроль идут два самых медленных участника, а
второй возвращается к делегации). В обоих случаях два самых
медленных участника оказываются во Дворце, а остальная делегация -
на улице. Очевидно, что для выбора стратегии нужно найти минимум из
t1 + tN-1 и 2t2 (именно на это время две стратегии и отличаются друг
от друга). После применения лучшей стратегии для провода двух
последних участников та же задача решается уже для N-2-го и N-3-го
участника. Причем заметим, что если на каком-то шаге была выбрана
стратегия А, то только ее и придется использовать в дальнейшем, так
как если t1 + tN-1 < 2t2 , то это же неравенство тем более будет
справедливо и при замене tN-1 на tN-3. Поэтому фактически требуется
лишь определить, когда со стратегии В следует переключиться на
стратегию А.
Далее
ð
