Задача к ЕГЭ по информатике на тему «прочие прототипы» №4

У вас есть кастрюля и $N$ (не более $50$ ) ингредиентов. Каждый ингредиент имеет параметр вещественного числа, называемый значением, а значение $i$ -го ингредиента $(1 ≤ i ≤ N )$ равно $vi$ (каждое не более $1000$ ). Когда вы положите в кастрюлю два ингредиента, они исчезнут и в результате образуется новый ингредиент. Значение нового ингредиента будет равно $(x+ y)∕2$ , где $x$ и $y$ — значения потребленных ингредиентов, и вы можете снова положить этот ингредиент в кастрюлю. После того, как вы составите ингредиенты таким образом $N − 1$ раз, у вас получится один ингредиент. В ответе запишите максимально возможную ценность этого ингредиента с точностью до сотых. В первой строке файла $26.txt$ находится одно число $N$ . В следующих $N$ строках файла находится массив целых чисел $v$ длины $N$ (длина массива это есть количество содержащихся в нем элементов) по одному элементу в строке.

Для получения ответа работает следующий жадный алгоритм: давайте делать каждый следующий новый ингредиент из двух наименьших по значению ингредиентов. Проделаем эту операцию $N − 1$ раз и получим ответ

Почему это работает? Рассмотрим ситуацию, в которой мы кладем два ингредиента, которые образовались из двух различных наборов ингредиентов: $[v1,v2,v3...,vn]$ и $[u1,u2,u3,...,um]$ со значениями $a$ и $b$ соответственно, и для определенности $a >= b » class=»math» src=»/images/inform/reshen/reshen-4620-6.svg» width=»auto»>. Тогда ценность объединения <img decoding=$ . Тогда если n > 1 » class=»math» src=»/images/inform/reshen/reshen-4620-8.svg» width=»auto»> и <img alt= 1 » class=»math» src=»/images/inform/reshen/reshen-4620-9.svg» width=»auto»>, тогда утверждается, что можно поменять последовательность ходов и собрать новый элемент состоящий из объединения наборов, который будет иметь большую (строго говоря конечно неменьшую) ценность. Давайте просто напросто посмотрим на последнюю операцию из которой получился первый набор $[vi]$ и не будем её делать, получим два каких то элемента. Пусть значения этих элементов $x$ и $y$ , и $x >= y » class=»math» src=»/images/inform/reshen/reshen-4620-13.svg» width=»auto»>. Тогда мы знаем, что <img decoding=$ . Теперь у нас есть три элемента со значениями $x,y,b$ . Отсортируем их. Так как = 2∗ a » class=»math» src=»/images/inform/reshen/reshen-4620-17.svg» width=»auto»> значит $x >= a >= b » class=»math» src=»/images/inform/reshen/reshen-4620-18.svg» width=»auto»>. Теперь соединим элементы с ценностью <img decoding=$ и $b$ , а потом получившийся с элементом со значением $x$ . Итого ценность нового элемента составит $y∕4+ (x+ b)∕2$ вместо $(x +y)∕4+ b∕2$ .

Очевидно, что разница в значениях есть $x∕2$ . Руководствуясь такой логикой можем получить, что каждый ход, это соединение унарного(то есть данного изначально по условию) ингредиента и того, который собран из множества ингредиентов. Тогда чем позже изначальный элемент был смешан, тем на меньшую степень $2$ будет поделена его ценность, поэтому чем больше ценность элемента тем позже его следует добавлять

Решение на Python:

f = open(’26.txt’)
n = int(f.readline())
a = [int(x) for x in f]
a.sort()
ans = a[0]
for i in range(1, n):
    ans = (ans + a[i]) / 2
print(ans)

Ответ: 911.28