Решение задачи #25. Python Яндекс CodeRun, Коммерческий калькулятор

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Коммерческий калькулятор.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берёт с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в евро равна 5% от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдётся вычисление суммы чисел (тем самым оказывается нарушен классический принцип «от перестановки мест слагаемых сумма не меняется»).

Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в 1.05 €), потом результат с 12 (1.65 €), и затем с 13 (2.3 €), то всего мы заплатим 5 €, если же сначала отдельно сложить 10 и 11 (1.05 €), потом 12 и 13 (1.25 €) и, наконец, сложить между собой два полученных числа (2.3 €), то в итоге мы заплатим лишь 4.6 €. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.

Решение:

Python

import sys
import heapq

def main():
    """
    Читаем число N из стандартного потока ввода.
    """
    n = int(input())

    """
    Читаем N натуральных чисел из стандартного потока ввода и добавляем их в очередь с приоритетом (min-heap).
    """
    numbers = [int(x) for x in input().split()]
    heapq.heapify(numbers)

    """
    Вычисляем минимальную стоимость нахождения суммы N чисел.
    """
    total_cost = 0
    while len(numbers) > 1:
        # Берем два минимальных числа из очереди с приоритетом.
        a = heapq.heappop(numbers)
        b = heapq.heappop(numbers)

        # Складываем их и добавляем результат обратно в очередь с приоритетом.
        c = a + b
        heapq.heappush(numbers, c)

        # Вычисляем стоимость операции и добавляем ее к общей стоимости.
        cost = c * 0.05
        total_cost += cost

    """
    Выводим минимальную стоимость с двумя знаками после десятичной точки.
    """
    print(f"{total_cost:.2f}")

if __name__ == "__main__":
    main()
	

Объяснение кода

Импорт heapq и sys:
Импортируем необходимые модули. Хотя в данном случае sys не используется, он был указан в исходном коде.

Функция main():
Чтение входных данных:
n = int(input()): Считывает количество чисел.
numbers = [int(x) for x in input().split()]: Считывает числа и преобразует их в список целых чисел с помощью списочного включения.

Создание кучи:
heapq.heapify(numbers): Преобразует список numbers в кучу (min-heap). Теперь наименьший элемент всегда находится в numbers[0].

Цикл сложения:
while len(numbers) > 1:: Цикл выполняется, пока в куче больше одного элемента.
a = heapq.heappop(numbers): Извлекает наименьший элемент из кучи.
b = heapq.heappop(numbers): Извлекает следующий наименьший элемент из кучи.

c = a + b: Складывает два извлеченных числа.

heapq.heappush(numbers, c): Добавляет результат сложения c обратно в кучу, поддерживая структуру кучи.

cost = c * 0.05: Вычисляет стоимость операции.

total_cost += cost: Добавляет стоимость к общей стоимости.

Вывод результата:
print(f"{total_cost:.2f}"): Выводит итоговую стоимость с двумя знаками после запятой, используя f-строки для форматирования.

Источник решения: hdhai.com