D. Валера и торговые автоматы

Условие

D. Валера и торговые автоматы

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

Сладкоежка Валера хочет получить как можно больше шоколадок, но его бюджет ограничен 200 тугриками. Каждая попытка покупки (одно использование любого автомата) стоит ровно 1 тугрик — плата взимается независимо от того, выдаст ли автомат шоколадку или нет. Валера, пытаясь узнать вероятности выдачи шоколадок у автоматов, встретил охранника Алексея, который поделился с ним важной информацией. Охранник Алексей сообщил, что у 2/5 автоматов вероятности выдачи взяты из равномерного распределения на отрезке [0.2, 0.3], у 2/5 автоматов — из равномерного распределения на отрезке [0.4, 0.5], а у оставшихся — из равномерного распределения на отрезке [0.85, 1].

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

Протокол взаимодействия

Это интерактивная задача. Ваша программа должна сначала вывести номер автомата — число от 0 до 9. Затем система (интерактор) вернёт результат: 1, если шоколадка выпала, или 0, если не выпала. Ваша программа может считать это значение (например, через input()), чтобы использовать в дальнейших вычислениях.

Система оценивания

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

Примечание

В качестве компилятора рекомендуется использовать Python 3.8 (Handbook DS)

Ответ

Это задача многорукого бандита: нужно исследовать автоматы и постепенно чаще выбирать успешные. Простой вариант — Thompson sampling; он не гарантирует больше 75% успехов в каждом случайном прогоне.

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

import random

alpha = [1] * 10
beta = [1] * 10
for _ in range(200):
    machine = max(range(10), key=lambda i: random.betavariate(alpha[i], beta[i]))
    print(machine, flush=True)
    reward = int(input())
    if reward not in (0, 1):
        break
    alpha[machine] += reward
    beta[machine] += 1 - reward

Это базовый алгоритм с равномерным Beta(1,1)-приором, а не точное использование заданной смеси интервалов и количества автоматов каждого типа. Более сильное решение учитывает эту информацию в апостериорном распределении. Код делает не более 200 попыток; из-за случайных выдач гарантировать порог теста нельзя даже для хорошей стратегии.