Яндекс.Алгоритм 2011: Квалификация 2 |
---|
Закончено |
Недавно Вася разрабатывал новый алгоритм по оптимизации приема клиентского потока и рассматривал следующую задачу.
Пусть в очереди к кассе стоят n человек, причем, каждый характеризуется положительным целым числом ai — временем обработки этого клиента. Особенность же данной конкретной кассы в том, что она способна принять двух клиентов одновременно, причем время обработки двух клиентов со временами ai и aj равно max(ai, aj). Обратите внимание, что обработка — это непрерываемый процесс, и поэтому, если два человека одновременно обслуживаются в кассе, то это значит, что они одновременно начали обрабатываться, и одновременно закончат (возможно, что одному из них придется подождать).
Вася в своем алгоритме использовал гениальную эвристику — пока в очереди больше одного человека на обработку посылаются одновременно какие-то два человека из первых трех, стоящих в начале очереди. В случае, если в очереди остается единственный клиент номер i, то он проходит в кассу, и его обслуживание занимает ai времени. Заметим, что общее количество фаз обработки будет всегда равно ⌈n / 2⌉ (операция ⌈x⌉ означает округление вверх до ближайшего целого числа).
Вася считает, что этот метод поможет справиться со столь ненавистными всем очередями, и поэтому попросил Вас разработать программу, которая определит минимальное время, за которое обработается вся очередь с помощью этого алгоритма.
В первой строке входного файла содержится единственное число n (1 ≤ n ≤ 1000) — количество людей в последовательности. Во второй строке через пробел записаны целые числа a1, a2, ..., an (1 ≤ ai ≤ 106). Люди занумерованы начиная от кассы к концу очереди.
В первую строку выведите единственное число — минимальное время, за которое будут обработаны все n человек. Далее в ⌈n / 2⌉ строках выведите порядок, в котором будут обрабатываться клиенты. Каждая строка (кроме, возможно, последней) должна содержать два числа через пробел — номера клиентов, которые на текущем шаге пройдут на обработку. Если n — нечетно, то последняя строка должна содержать единственное число — номер последнего обработанного человека в очереди. Клиенты нумеруются начиная с 1, числа в строках разрешается выводить в любом порядке.
4
1 2 3 4
6
1 2
3 4
5
2 4 3 1 4
8
1 3
2 5
4
Название |
---|