Вы - -й посетитель этой странички 

Задачи XIII Всероссийской олимпиады по информатике

Решения задач подготовлены Е.В. Андреевой

Задача 1. “Бизнес-классики”

    Поле для игры в бизнес-классики представляет собой прямоугольник, состоящий из 3 ´ N клеток. В некоторых клетках лежит по одному рублю, в остальных — ничего нет. Играющий выбирает для начала игры одну из трех левых клеток и прыгает в нее. За один ход играющий перепрыгивает в одну из клеток, имеющих общую сторону с той, в которой он находится. При этом запрещено прыгать в те клетки, в которых он уже побывал. При очередном прыжке все деньги, собранные к этому моменту, удваиваются, а затем, если в новой клетке лежит рубль, то он прибавляется к имеющейся сумме денег. Считается, что в начале игры денег у играющего нет. Закончить прыжки надо в одной из трех правых клеток поля и при этом заработать как можно больше денег.

Требуется

    Написать программу, которая по известному значению N и расположению рублей в клетках находит такую последовательность прыжков, при которой играющий заработает наибольшее количество денег. Если таких последовательностей несколько, то следует выбрать любую последовательность, количество прыжков в которой минимально.

Входные данные

    В первой строке входного файла с именем CLASS.IN записано натуральное число N (1 £ N £ 80). В каждой из последующих трех строк находится N чисел (0 или 1), описывающих расположение рублей в клетках первой, второй и третьей строки игрового поля соответственно. Единица обозначает наличие рубля в клетке, ноль — его отсутствие. Числа в каждой из этих трех строк входного файла расположены через пробел.

Выходные данные

    Выходной файл с именем CLASS.OUT должен содержать 2 строки. В первой строке должен находиться номер строки игрового поля (1, 2 или 3), с которой играющему следует начать игру. Вторая строка файла должна описывать последовательность прыжков. Каждый прыжок в этой последовательности нужно обозначить одним из следующих символов:
    · U — если в результате прыжка номер строки, на которой находится играющий, уменьшился на 1;
    · D — если номер строки увеличился на 1;
    · L — если номер столбца уменьшился на 1;
    · R — если номер столбца увеличился на 1.
    Символы во второй строке выходного файла должны быть выведены без пробелов.

Пример входного файла

    4
    1 1 1 0
    1 1 1 0
    1 1 1 1

Пример выходного файла для приведенного примера входного файла

    1
    DDRUURDDRUU
   

Решение

    Если, согласно информации о наличии или отсутствии рублей в клетках, искомую последовательность прыжков записать в виде набора нулей и единиц, то станет ясно, что размер выигрыша равен значению полученного двоичного числа. Так, в приведенном примере игрок заработает 111111111100₂ = 4092₁₀ . Отсюда следует, что в большинстве случаев игроку выгодно побывать во всех клетках поля, в этом случае число разрядов двоичного числа будет максимальным, а количество прыжков равно 3N. Меньшее количество прыжков имеет смысл делать лишь если рублей на поле нет совсем (тогда выигрыш будет равен 0 для любой последовательности прыжков, а последовательность прыжков минимальной длины будет состоять из N клеток любой строки) или если первый столбец имеет вид 010 (тогда значение выигрыша выражается двоичным числом длины 3N—1 и игрок может впрыгивать в среднюю клетку, не уменьшая выигрыша). Во всех остальных случаях впрыгивать имеет смысл только в начальную клетку первой или третьей строки, иначе невозможно побывать во всех клетках поля, не нарушая правила игры.
    Осталось определить способ обхода всех клеток поля, который будет соответствовать максимально возможному двоичному числу. В связи с тем что поле имеет всего три строки, каждые из k рядом стоящих столбцов могут быть пройдены одним из двух способов — вертикальной или горизонтальной “змейкой” (решение в примере соответствует прохождению всех столбцов поля вертикальной “змейкой”). А все поле целиком можно обойти, комбинируя эти два способа: например, первые k₁ столбцов — вертикальной “змейкой”, следующие k₂ — горизонтальной, следующие k₃ — опять горизонтальной — и т.д. — см. рис. 1.

Рис.1.

    Пусть мы уже знаем оптимальный способ обхода первого столбца, первых двух столбцов, …, первых k — 1 столбцов. Тогда несложно определить оптимальный способ обхода первых k столбцов, сравнивая результаты следующих комбинаций обхода — обход горизонтальной “змейкой” всех первых k столбцов сверху вниз или снизу вверх или оптимальный обход первого столбца + горизонтальная “змейка” по следующим k — 1 столбцам или оптимальный обход первых двух столбцов + горизонтальная “змейка” по следующим k — 2 столбцам и т.д. Последний из рассматриваемых вариантов представляет собой оптимальный обход первых k — 1 столбцов и вертикальное прохождение k-го столбца. Наилучшая из рассмотренных комбинаций запоминается как оптимальный обход k первых столбцов и используется в дальнейшем. Такой способ решения относится к динамическому программированию.

Задача 2. “Оппозиция”

    В некоторой стране полиция выявила разветвленную сеть оппозиционной партии.
    Партия сильно законспирирована и состоит из рядовых членов и руководителей различных уровней. Во главе партии стоит один главный руководитель — лидер партии. До начала арестов приказ лидера может быть доведен до любого члена партии. Все члены партии пронумерованы от 1 до N.
    Каждый член партии знает только своего вышестоящего руководителя (ровно одного) и своих непосредственных подчиненных (руководитель не знает подчиненных своего подчиненного и наоборот).
    Естественно, что с началом арестов членов партии она распадется на мелкие, не связанные друг с другом группы. Например, с арестом члена партии № 2 (см. рис. 2) партия разваливается на 4 группы.
    Полицмейстер уверяет, что группа, состоящая из менее чем К членов партии, идеологически вырождается и не представляет угрозы для государства.
    Стремясь не уронить престиж страны в глазах мирового общественного мнения, полицмейстер поставил задачу произвести минимальное количество арестов членов партии так, чтобы от нее остались только идеологически вырождающиеся маленькие группы.

Требуется

    Написать программу, которая бы по входным данным, описывающим структуру подпольной партии, выводила количество арестов и номера членов партии, которых нужно арестовать.

Входные данные

    Входной файл с именем ORG.IN содержит три строки. В первой записано число K (1 £ K £ 10 000), во второй строке — число N (1 £ N £ 10 000), определяющее количество членов партии. Третья строка содержит набор из N—1 числа. В этой строке для каждого члена партии, кроме лидера, задается номер его непосредственного руководителя. Номер руководителя всегда меньше, чем номер подчиненного. При этом первое число задает номер руководителя второго члена партии, второе — третьего и так далее. Числа в строке разделяются одним пробелом.

Выходные данные

    Выходной файл с именем ORG.OUT состоит из двух строк. В первую строку необходимо поместить количество арестов, а во вторую — номера членов партии, подлежащих аресту. Эти номера разделяются одним пробелом. При наличии нескольких решений выведите одно из них.

Пример входного файла для структуры партии, представленной на рис. 2

    3
    14
    1 1 2 2 3 2 3 6 6 6 7 4 7

Пример выходного файла для приведенного входного файла

    4
    6 2 7 8

Решение

    Описанная в условии задачи структура партии представляет собой дерево. Пусть для некоторого его поддерева справедливо следующее: каждая ветвь данного поддерева в отдельности содержит менее K элементов, а все поддерево в целом — K или более элементов (число элементов в поддереве равно сумме элементов в его ветвях плюс один элемент, соответствующий корневой вершине поддерева). Тогда очевидно, что удаление корневой вершины данного поддерева (то есть арест соответствующего члена партии) решает поставленную задачу в рамках рассмотренного поддерева оптимальным образом.
    Действительно, удаление вершин, не принадлежащих данному поддереву, не может уменьшить избыточное число элементов в нашем поддереве, а удаление иной вершины поддерева, кроме корневой, возможно, и приведет к решению задачи для рассмотренного поддерева, но тогда непосредственный “начальник” неудаленной корневой вершины “идеологически обезвреженного” поддерева будет иметь по крайней мере на одного “подчиненного” больше, что может увеличить общее число удалений вершин (арестов).
    В результате получаем следующий алгоритм решения задачи. Начиная с “листовых” вершин (соответствующих рядовым членам партии, не имеющим подчиненных), подсчитываем для каждой вершины дерева количество элементов в связанном с ней поддереве. Если количество элементов в поддереве оказалось больше или равно K, то его корневая вершина удаляется, данное поддерево исключается из рассмотрения и задача решается для оставшихся элементов дерева. Последним из рассмотренных элементов должна оказаться вершина № 1, обозначающая лидера партии. Так, в приведенном примере данный алгоритм предложит удалить вершины дерева с номерами 7, 6, 2 и 1. Алгоритм является линейным относительно количества членов партии, а его реализация зависит от выбора структуры данных для хранения исходного дерева.

Задача 3. “Телеметрия”

    Для космического корабля сконструирована телеметрическая система, содержащая N (1 £ N £ 1000) групп датчиков. Каждая из этих групп включает P_i (1 < P_i ) датчиков. Группе датчиков соответствует свой канал связи, к которому в конкретный момент времени может быть подключен только один датчик этой группы, который назовем активным.

Рис.3

    С центрального пульта на систему могут подаваться команды управления. Каждая команда управления имеет вид:

номер группы <пробел> + | —

    При этом номер активного датчика в соответствующей группе увеличится или уменьшится на единицу. Попытка установить номер активного датчика в группе вне пределов [1..P_i ] ведет к аварийному останову контроллера.
    В исходном состоянии для каждой из групп известен номер активного датчика.
    Для комплексной проверки корабля требуется проводить съем показаний для всех возможных комбинаций активных датчиков, причем повторять уже использованные ранее комбинации активных датчиков запрещается. Общее количество комбинаций активных датчиков не превосходит 10 000.
    После окончания проверки система должна оказаться в исходном состоянии.

Требуется

    Разработать программу, которая осуществляла бы управление контроллером, реализующее требуемый опрос датчиков.

Входные данные

    Входной файл с именем TELE.IN содержит следующие три строки. Первая строка содержит число N — количество групп датчиков. Вторая строка содержит N чисел P₁ , P₂ , …, P_N , каждое из которых задает количество датчиков в соответствующей группе. Третья строка содержит N исходных номеров активных датчиков в группах. Числа во второй и третьей строках разделены пробелом.

Выходные данные

Выходной файл с именем TELE.OUT должен содержать следующие строки. В первую строку выводится сообщение Yes или No, в зависимости от того, возможно или нет реализовать управление контроллером, осуществляющее требуемую схему съема данных. При выводе сообщения Yes в последующих строках выдается последовательность команд управления. Каждая строка должна содержать по одной команде управления. При этом знак “+” соответствует увеличению на 1, а знак “—” — уменьшению на 1 номера активного датчика в этой группе.

Пример входного файла

    2
    2 3
    2 1

Пример выходного файла, соответствующего приведенному входному файлу

    Yes
    1 —
    2 +
    2 +
    1 +
    2 —
    2 —

Примечание. Будут отдельно оцениваться решения для частных случаев N = 1, N = 2, N = 3.

Решение

    Эта задача являлась, пожалуй, самой сложной на данной олимпиаде, как по выработке алгоритма решения, так и по его реализации, именно поэтому даже разбор случаев с N £ 3 оценивался жюри достаточно высоко. Решать задачу удобнее всего с помощью рекурсивного спуска, выражая решение для N групп датчиков через перечисление всех состояний для N — 1 групп датчиков и т.д. Для двух групп решение строится явным образом. Заметим, что при N = 1 решения не существует, если данная группа состоит более чем из одного датчика.
    При N > 1 решения не существует, если количество датчиков во всех группах нечетно, то есть произведение чисел P₁ , P₂ , …, P_N нечетно. Так как если нам требуется перебрать все комбинации активных датчиков, то в каждой из групп датчиков количество команд “увеличить номер активного датчика” должно совпадать с количеством команд “уменьшить номер активного датчика”, то есть общее количество команд, равное числу всевозможных комбинаций, должно быть четным. Если же существует хотя бы одна группа с номером i, в которой количество датчиков P_i четно, то решение построить можно. Для удобства далее будем считать, что i = N, а в начальный момент времени активным является первый датчик в каждой из групп, что не снижает общности рассмотрения. Для N = 2 задачу можно переформулировать следующим образом. В прямоугольнике размером P₁ ´ P₂ требуется циклически обойти все точки с целочисленными координатами, построив для этого замкнутую ломаную без самопересечений и самокасаний. Так как по нашему предположению P₂ четно, то решение всегда можно построить следующим образом:

Рис. 4

    Если N = 3, то требуется обойти уже все целочисленные точки прямоугольного параллелепипеда P ₁ ´ P ₂ ´ P₃ . Для этого сначала обойдем все точки (x, y, z) параллелепипеда, за исключением тех, у которых x = 1, в таком порядке: значение z фиксируется, и точки, у которых 1 < x £ P₁ , 1 £ y £ P₂ , z = 1, обходятся “змейкой”, аналогичной приведенной для N = 2, но без возврата в начальную точку. Затем делаем z = 2 и обходим точки “второго уровня” такой же “змейкой”, но в обратном направлении, завершая обход в точке (2, 1, 2), затем переходим в точку (2, 1, 3) и проходим уже “третий уровень” аналогично первому. Так как P₃ четно, то остановимся мы в точке (2, 1, P₃ ). Оттуда перемещаемся в соседнюю точку (1, 1, P₃ ) и “змейкой” же обходим оставшуюся грань z = 1, постепенно спускаясь вниз, и, опять же благодаря четности P₃ , оказываемся в начальной точке (1, 1, 1). Для N > 3 будем поступать подобным же образом. Сначала обойдем все точки N-мерного параллелепипеда, за исключением тех, у которых координата x равна 1, заканчивая обход в точке (2, 1, 1, …, P_N ), а затем возвращаемся в начальную точку, обходя все точки с x = 1.

Задача 4. “Лесной пожар”

    В МЧС поступило сообщение о возможном лесном пожаре в заданном квадрате тайги. Для поиска места возгорания было послано N самолетов. Однако ни один из экипажей пожара не обнаружил.
    Известно, что с самолета видна полоса тайги, границы которой находятся на расстоянии 50 км справа и слева от той линии на поверхности Земли, над которой пролетает самолет (см. рисунок), причем точки, находящиеся на расстоянии ровно 50 км от этой линии, все еще видны. Донесение с каждого самолета содержало информацию о том, в каких двух различных точках (x_b , y_b ) и (x_e , y_e ) самолет входил в заданный квадрат и покидал его соответственно. Между этими точками самолет двигался строго по прямой.

Рис. 5

Требуется

    Написать программу, которая определит, действительно ли весь заданный квадрат тайги был просмотрен с самолетов. Если это не так, то программа должна находить координаты какой-нибудь точки, лежащей внутри или на границе квадрата и не попавшей ни в одну из просмотренных полос.

Входные данные

    Входной файл с именем FIRE.IN состоит из N + 2 строк.
    В первой строке записано натуральное число L — размер заданного квадрата тайги в километрах (0 < L £  1000). Во второй строке — натуральное число N (1 £  N £  100) — количество самолетов. В каждой из последующих N строк записано донесение с самолета — четыре вещественных координаты x_b , y_b , x_e , y_e . Координаты заданы в километрах. Стороны квадрата тайги параллельны осям координат, его левый нижний угол находится в точке с координатами (0, 0), а правый верхний — в точке (L, L).

Выходные данные

    Выходной файл с именем FIRE.OUT должен содержать одну строку. Если заданный квадрат был просмотрен полностью, то эта строка должна состоять из слова OK, написанного заглавными латинскими буквами. В противном случае в этой строке должны быть записаны через пробел координаты x и y какой-либо точки, которая не попала ни в одну из просмотренных полос. Координаты нужно выводить в километрах с ошибкой не более одного метра.

Пример входного файла

    245
    1
    26.1 0 193.568 245

Пример выходного файла для приведенного примера входного файла

155.123 100

    Примечание. Будут отдельно оцениваться решения, сделанные в предположении, что каждый самолет летел параллельно одной из сторон квадрата.

Решение

    Несмотря на то, что ширина каждой из полос составляет 100 км, непросмотренный участок может быть как угодно малым, то есть его размер по каждой из координат может быть менее одного метра. Поэтому искомый результат следует трактовать так: в окрестности найденной при решении точки должна действительно находиться по крайней мере одна непросмотренная точка, и каждая из координат этой непросмотренной точки должна отличаться не более чем на один метр от координат найденной точки. Поиск такой точки можно осуществлять следующим образом. Рассмотрим набор отрезков, который состоит из четырех сторон квадрата и 2N отрезков, образованных в результате пересечения границ полос с квадратом. Найдем все попарные пересечения этих 2N + 4 отрезков. Если непросмотренная точка существует, то она находится в окрестности одной из найденных точек пересечения.
    Рассмотрим 4 угла, образованные в результате пересечения двух отрезков, обозначив точку их пересечения A (если хотя бы один из отрезков является стороной квадрата, то рассматривать следует лишь углы, лежащие внутри квадрата). Для каждого из углов найдем точки пересечения их биссектрис с ближайшим отрезком, не проходящим через точку A, обозначим их B₁ , B₂ , B₃ , B₄ (см. рис. 6). Тогда, для того чтобы проверить, не является ли один из рассматриваемых углов в некоторой окрестности точки A непросмотренным с самолетов, достаточно проверить принадлежность полосам середин отрезков [A; B_i ], i = 1..4. Причем, если в точке A пересекаются более чем 2 отрезка, то опять же достаточно рассматривать лишь попарные их пересечения, так как если непокрытый угол в окрестности точки A существует, то он образован в результате пересечения какой-либо пары отрезков и предложенный выше способ анализа углов позволит обнаружить точку, непокрытую полосами. Если же непросмотренных областей нет в окрестности ни одной из точек пересечения отрезков, то их нет вообще.

    Задачу можно решать и численно. Проверим, не покрыты ли все 4 вершины квадрата одной из полос или не является ли одна из вершин квадрата непросмотренной ни из одного самолета. В любом из этих двух случаев задача решена (квадрат просмотрен полностью с одного самолета в первом случае и непросмотренная точка найдена — во втором). В противном случае делим исходный квадрат на 4 части (разделив пополам каждую из сторон) и анализируем вершины каждого из этих четырех квадратов, и т.д. Причем квадраты, все четыре вершины которых покрыты одной и той же полосой, из дальнейшего рассмотрения исключаются. В результате либо будет найдена непокрытая точка, либо размер квадрата достигнет величины, которой можно пренебречь в сравнении с машинной точностью вычислений, и тогда его можно считать просмотренным. Данный метод будет особенно эффективным, если исключить из рассмотрения касания полос, то есть считать две и более касающихся полосы за одну и ту же полосу (что по условию задачи является верным).

Задача 5. “Замок”

    В замке Stonehandge юный принц не поладил со своей гувернанткой в комнате, где они завтракали. Для избежания наказания принц решил спрятаться в одной из комнат замка. Двигаясь из комнаты в комнату, принц обязательно закрывал на ключ дверь, через которую он прошел, после чего ни он, ни гувернантка не могли воспользоваться этой дверью. Через любую комнату (в том числе и через ту, в которой находится гувернантка) принц может проходить несколько раз, если это позволяют еще не запертые им двери. Изначально все двери замка не заперты.
    Между двумя комнатами замка не более одной двери. Общее количество дверей не превосходит 5000.
    Гувернантка начинает искать принца только после того, как он спрятался. Избежать наказания принц может только в том случае, если гувернантка, проходя через оставшиеся незапертыми двери, не сумеет попасть в комнату, где он спрятался.

Требуется

    Написать программу, которая определяет, сможет ли принц спрятаться от гувернантки, и если укрыться удается, то предлагает ему любой из возможных путей спасения.

Входные данные

    Во входном файле CASTLE.IN содержится план замка.
    В первой строке входного файла находится натуральное число N (1 < N < 1000) — количество комнат.
    Во второй строке входного файла содержится натуральное число K (1 £ K £ N) — номер комнаты, в которой принц и гувернантка завтракали.
    В последующих N строках содержатся списки смежных комнат: в i-й строке перечислены через пробел номера комнат, смежных с i-й комнатой. Каждая такая строка заканчивается нулем.

Выходные данные

    Выходной файл с именем CASTLE.OUT должен содержать следующую информацию. Если принц не сможет избежать наказания, в единственной строке файла выводится сообщение No. В противном случае в первой строке файла выводится сообщение Yes, во второй строке — количество дверей, закрытых принцем, а в третьей строке — последовательность номеров комнат, разделенных пробелами, в которых побывал принц.

Пример входного файла

    4
    1
    2 4 0
    4 1 3 0
    2 4 0
    1 2 3 0

Пример выходного файла для приведенного примера входного файла

    Yes
    3
    1 4 2 3

    Примечание. Будут отдельно оцениваться решения для частного случая N £ 100.

Решение

    Несмотря на то что условие задачи легко переформулировать в терминах теории графов, ее решение не сводится полностью ни к одному из стандартных алгоритмов на графах, а основано на здравом смысле. Во первых, следует исключить из рассмотрения комнаты, до которых невозможно добраться из комнаты, в которой принц завтракал с гувернанткой, т.е. выделить компоненту связности графа, например, с помощью ее обхода в глубину или в ширину. Если выделенная компонента связности графа состоит только из начальной комнаты или содержит эйлеров цикл, то есть комнаты возможно обойти, обязательно проходя через каждую из дверей ровно один раз (при этом в любой из комнат можно бывать сколько угодно раз), то спрятаться в таком замке невозможно. Согласно известной теореме, несложно проверить, обладает ли граф таким свойством — необходимым и достаточным условием наличия эйлерова цикла в графе является условие четности степеней всех его вершин, то есть в каждой из комнат, включая начальную, должно быть четное число дверей.
    В противном случае в замке спрятаться можно. Если в начальной комнате нечетное число дверей, то двигаться принцу можно в произвольном направлении либо до тех пор, пока он не окажется в комнате, все двери в которую уже заперты, либо пока принц не вернется в комнату, с которой он начал движение, и в ней незапертой останется ровно одна дверь. Тогда ему следует войти в эту дверь, и изолированной окажется уже гувернантка, что также является для принца спасительным вариантом. Если же в начальной комнате четное число дверей, то принцу следует сначала добраться до любой из комнат, количество дверей в которой нечетно, затем пройти по всем существующим циклам, которые начинаются и заканчиваются в этой комнате. В результате либо принц уже окажется запертым в такой комнате, либо по крайней мере одна из оставшихся двух, четырех и т.д. дверей уже не будет связана с начальной комнатой. Когда принц пройдет через нее и запрет ее за собой, гувернантка добраться до него уже не сможет. Если бы такой двери не существовало, то есть из всех оставшихся незапертыми дверей все еще можно было бы вернуться в исходную комнату, то это означало бы наличие по крайней мере еще одного цикла. Таким образом, задача решена для всех случаев.

Задача 6. “Олимпиада”

    Оргкомитет Всероссийской олимпиады по информатике выделил для некоторой области два места для участников. Однако на олимпиаду поехала делегация из N школьников.
    Представители Оргкомитета при встрече на вокзале выдали членам делегации два бейджа. По Положению об олимпиаде для участия в ней надо зарегистрироваться во Дворце молодежи, куда можно пройти только по бейджам.
    Для того чтобы все члены делегации проникли во Дворец молодежи, один из них предложил действовать следующим образом. Двое из членов делегации проходят с бейджами через пункт контроля, а затем кто-то из членов этой делегации, уже проникших во Дворец, тайно выносит оба бейджа назад на улицу. Эта процедура повторяется до тех пор, пока не пройдут все делегаты от этой области.
    Известно, что i-й делегат тратит на проход через пункт контроля t_i секунд, включая выход на улицу. Для прохода одной пары делегатов требуется время, равное времени прохода менее расторопного из этой пары.
    Для каждого члена делегации время, требуемое для выхода из здания, такое же, как и для входа.

Требуется

    Написать программу, определяющую, за какое наименьшее время и каким образом все делегаты области смогут проникнуть во Дворец молодежи.

Входные данные

    В первой строке входного файла OLYMP.IN задается натуральное число N (2 £ N £ 1000).
    В последующих N строках находятся натуральные числа t₁ , t₂ , ..., t_N (по одному в строке) — времена прохода членов делегации через пункт контроля в секундах, 1 £ t_i £ 10 000.

Выходные данные

    В первой строке выходного файла OLYMP.OUT необходимо выдать наименьшее возможное время (в секундах), через которое вся делегация окажется во Дворце молодежи.
    В последующих строках указывается какой-нибудь порядок прохода членов делегации за это наименьшее время, а именно тройки целых чисел, из которых первые два задают номера членов делегации, проходящих во Дворец, а третье — номер члена делегации, выносящего из Дворца два бейджа. В последней строке указываются только два числа — номера членов делегации, проходящих во Дворец последними. Все числа разделяются пробелами.

Пример входного файла

    3
    5
    5
    10

Пример выходного файла для приведенного примера входного файла

    20
    1  2  2
    2  3

Решение

    При решении поставленной задачи можно действовать исходя из двух разумных соображений. Либо самый быстрый член делегации проводит через пропускной пункт всех остальных, причем в любом порядке (назовем этот способ стратегией А), либо два самых медленных члена делегации проходят во Дворец вместе, а бейджи затем вынесет один из двух наиболее быстрых школьников, прошедших во Дворец ранее (стратегия В), после чего задача сводится к той же, но размерностью на 2 меньше. Используя перестановочный прием, можно проверить, что любой другой порядок прохода делегации в здание можно улучшить, заменяя его на комбинацию этих двух стратегий. Остается определить, в какой комбинации следует применять стратегии А и В в том или ином случае.
    Для определенности отсортируем времена прохода членов делегации через контроль по неубыванию. Теперь можно говорить, что наиболее быстрым является первый член делегации, а наиболее медленным — последний. Так как для стратегии А порядок прохода членов делегации в паре с первым не важен, а в стратегии В, наоборот, сначала надо организовать совместный проход двух самых медленных участников, то выбор начальной стратегии нужно проводить, сравнивая результирующее время прохода во Дворец двух самых медленных участников в каждом из двух случаев. В стратегии А это время равно t_N + t₁ + t_N—1 + t₁ (два самых медленных участника окажутся по очереди во Дворце, а самый быстрый вернется к делегации), а в стратегии В — t₂ + t₁ + t_N + t₂ (два самых быстрых участника проходят во дворец, затем первый возвращается и через контроль идут два самых медленных участника, а второй возвращается к делегации). В обоих случаях два самых медленных участника оказываются во Дворце, а остальная делегация — на улице. Очевидно, что для выбора стратегии нужно найти минимум из t₁ + t_N—1 и 2t₂ (именно на это время две стратегии и отличаются друг от друга). После применения лучшей стратегии для провода двух последних участников та же задача решается уже для N—2-го и N—3-го участника. Причем заметим, что если на каком-то шаге была выбрана стратегия А, то только ее и придется использовать в дальнейшем, так как если t₁ + t _N—1  < 2t₂ , то это же неравенство тем более будет справедливо и при замене t_N—1 на t_N—3 . Поэтому фактически требуется лишь определить, когда со стратегии В следует переключиться на стратегию А.