26.04 Прочие прототипы
Ошибка.
Попробуйте повторить позже
У вас есть кастрюля и (не более ) ингредиентов. Каждый ингредиент имеет параметр вещественного числа, называемый значением, а значение -го ингредиента равно (каждое не более ). Когда вы положите в кастрюлю два ингредиента, они исчезнут и в результате образуется новый ингредиент. Значение нового ингредиента будет равно , где и - значения потребленных ингредиентов, и вы можете снова положить этот ингредиент в кастрюлю. После того, как вы составите ингредиенты таким образом раз, у вас получится один ингредиент. В ответе запишите максимально возможную ценность этого ингредиента с точностью до сотых. В первой строке файла находится одно число . В следующих строках файла находится массив целых чисел длины (длина массива это есть количество содержащихся в нем элементов) по одному элементу в строке.
Для получения ответа работает следующий жадный алгоритм: давайте делать каждый следующий новый ингредиент из двух наименьших по значению ингредиентов. Проделаем эту операцию раз и получим ответ
Почему это работает? Рассмотрим ситуацию, в которой мы кладем два ингредиента, которые образовались из двух различных наборов ингредиентов: и со значениями и соответственно, и для определенности . Тогда ценность объединения . Тогда если и , тогда утверждается, что можно поменять последовательность ходов и собрать новый элемент состоящий из объединения наборов, который будет иметь большую (строго говоря конечно неменьшую) ценность. Давайте просто напросто посмотрим на последнюю операцию из которой получился первый набор и не будем её делать, получим два каких то элемента. Пусть значения этих элементов и , и . Тогда мы знаем, что . Теперь у нас есть три элемента со значениями . Отсортируем их. Так как , а значит . Теперь соединим элементы с ценностью и , а потом получившийся с элементом со значением . Итого ценность нового элемента составит вместо .
Очевидно, что разница в значениях есть . Руководствуясь такой логикой можем получить, что каждый ход, это соединение унарного(то есть данного изначально по условию) ингредиента и того, который собран из множества ингредиентов. Тогда чем позже изначальный элемент был смешан, тем на меньшую степень будет поделена его ценность, поэтому чем больше ценность элемента тем позже его следует добавлять
Решение на 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)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!