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

Задача

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

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

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

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

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

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

Тесты

Входные данные Выходные данные
$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, которого не в языке программирования Java. Для решения данной задачи числа на доске будут ключами, а их номера будем записывать в строку. Для задания такого «multimap» будем считывать с входного потока числа и смотреть есть ли в нашей карте такой ключ, если есть, то к строке добавляем ещё символ справа, если нет, то за в строку вставляем номер числа. Затем в цикле, пока не один элемент в «multimap» будем выбирать первые два элемента. Для выбираем первый ключ с помощью функции map.firstKey(), находим значение по ключу, проверяем длину полученной строки, если она равна $1$, то запоминаем символ строки и удаляем элемент с «multimap», иначе запоминаем первый символ строки и удаляем его из строки, записывая в «multimap» элемент с измененной строкой. Аналогично получаем следующее значение. Переводим символы в числа и выводим их номера элементов, которые были изъяты из «multimap» и находим среднее число. Добавляем в «multimap» пару, где первое значение — это найденное средние двух чисел, а второе — номер(добавление данного элемента осуществляется аналогично заполнению, т.е. если ключ уже есть в «multimap», то добавляем к значению справа номер). В конце концов мы получим, что в «multimap» будет всего одна пара и цикл остановит свою работу. Задача решена. Однако она не проходит по времени.

Ссылки

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *