e-olymp 1477. Наибольшее среднее

Задача

На доске выписаны $n$ целых чисел. Все они пронумерованы от $1$ до $n.$ Разрешается выбрать два произвольных числа, вытереть оба с доски и написать новое число, равное их среднему арифметическому. Новое число получает номер $n + 1.$ После этого снова выбираются два числа и вместо них записывается их среднее арифметическое, которому дается номер $n + 2$ и т.д. Так продолжается до тех пор, пока на доске не останется только одно число. Чем больше будет это число, тем более успешной считается последовательность действий.

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

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

В первой строке записано целое число $n$ $(1 \leqslant n \leqslant 10^5).$ Во второй строке задаются $n$ целых чисел, которые были первоначально записаны на доске. Все числа лежат в диапазоне от $-10000$ до $10000.$

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

Выведите $n — 1$ строку, в каждой из которых должны быть записаны по два целых числа, определяющие номера тех чисел, которые выбираются на соответствующем шаге.

Тесты

Входные данные Выходные данные
$3$
$7\;2\;4$
$2\;3$
$1\;4$
$4$
$6\;2\;7\;1$
$2\;4$
$1\;5$
$3\;6$
$4$
$12\;4\;7\;2$
$2\;4$
$3\;5$
$1\;6$
$5$
$234\;2\;5\;54\;5$
$2\;3$
$5\;6$
$4\;7$
$1\;8$

Код программы

Решение задачи

Для решения задачи создаем multimap, затем циклом вводим туда пары, где первое значение — это число с потока, а второе — его номер. После этого мы сохраняем первые два значения из multimap, выводим их номера и находим среднее число. Добавляем в multimap пару, где первое значение — это найденное средние двух чисел, а второе — номер. В конце концов мы получим, что в multimap будет всего одна пара и цикл остановит свою работу. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images: