Решение задачи #31. Python Яндекс CodeRun, Увлекательная игра

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

Условие задачи:
Петя и Маша играют в увлекательную игру. Маша загадывает число от 1 до n, записывает его на чистый тетрадный лист, кладёт в конверт и запечатывает. После этого Петя пытается это число отгадать. Он может задавать любые вопросы про это число: «Верно ли, что это число равно трем?», «Верно ли, что это число — число Фибоначчи?», «Верно ли, что это число простое?» и так далее. Получив ответ «да», Петя отдает Маше a конфет, а в случае ответа «нет» — b конфет.

В какой-то момент Петя произносит сакраментальную фразу: «Я знаю, что это за число». После этого они распечатывают конверт в присутствии свидетелей, убеждаются в Петиной правоте, и Маша получает внушительную порцию конфет, а Петя — моральное удовлетворение.

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

Формат ввода (input):
Входной файл содержит три целых числа: n (1≤n≤10001≤n≤1000), a и b (0≤a,b≤1060≤a,b≤106)

Формат вывода (Output):
Выведите одно число — минимальное количество конфет, которое должен иметь Петя, чтобы отгадать Машино число в худшем случае.

Решение:

Python

import sys

def main():
    """
    Функция для решения задачи о минимальном количестве конфет.
    """
    # Чтение входных данных: n, a, b
    n, a, b = map(int, sys.stdin.read().split())

    # Создаем массив dp, где dp[i] — минимальное количество конфет,
    # необходимое для угадывания числа из i вариантов в худшем случае.
    dp = [0] * (n + 1)

    # Базовый случай: если есть только одно число, то конфет не нужно.
    dp[1] = 0

    # Заполняем массив dp для всех значений от 2 до n.
    for i in range(2, n + 1):
        # Инициализируем dp[i] как максимально возможное значение.
        dp[i] = float('inf')

        # Перебираем все возможные вопросы Пети.
        for j in range(1, i):
            # Если Петя задает вопрос, разделяющий множество чисел на две группы:
            # - группа размера j (ответ "да"),
            # - группа размера i - j (ответ "нет").
            # Тогда в худшем случае потребуется max(dp[j], dp[i - j]) конфет
            # плюс стоимость ответа "да" или "нет".
            cost_yes = dp[j] + a  # Стоимость, если ответ "да"
            cost_no = dp[i - j] + b  # Стоимость, если ответ "нет"

            # В худшем случае выбираем максимальную из двух стоимостей.
            worst_case_cost = max(cost_yes, cost_no)

            # Минимизируем общую стоимость для i чисел.
            dp[i] = min(dp[i], worst_case_cost)

    # Выводим минимальное количество конфет для n чисел.
    print(dp[n])


if __name__ == "__main__":
    main()
	

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

Постановка задачи и идея решения:
Задача заключается в том, чтобы определить минимальное количество конфет, которые потребуются Пете для гарантированного угадывания числа, загаданного Машей, при условии, что он может задавать вопросы, делящие множество чисел на две группы. Каждый вопрос имеет "стоимость" в зависимости от ответа ("да" или "нет").

Основная идея решения заключается в использовании динамического программирования . Мы строим массив dp, где dp[i] обозначает минимальное количество конфет, необходимых для угадывания числа из i возможных вариантов.

Базовый случай:
Если есть только одно число (i = 1), то Петя уже знает ответ, и ему не нужно задавать никаких вопросов. Таким образом, dp[1] = 0.

Рекуррентное соотношение:
Для каждого числа i > 1 мы перебираем все возможные способы разделения множества чисел на две группы:

Группа размера j (ответ "да"),
Группа размера i - j (ответ "нет").
Стоимость для каждого разделения вычисляется как:

cost_yes = dp[j] + a — если ответ "да",
cost_no = dp[i - j] + b — если ответ "нет".
В худшем случае выбирается максимальная из этих двух стоимостей:
worst_case_cost = max(cost_yes, cost_no)

Мы минимизируем эту стоимость по всем возможным разделениям:
dp[i] = min(dp[i], worst_case_cost)

Вычислительная сложность:
Внешний цикл проходит по всем значениям от 2 до n (итераций: O(n)).
Внутренний цикл перебирает все возможные разделения для текущего i (итераций: O(i)).
Таким образом, общая сложность алгоритма составляет O(n^2) , что приемлемо для ограничений задачи (n ≤ 1000).

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