Задача 470
Супер Рамвок

Рассмотрим игру Рамвок:

Пусть t обозначает максимальное количество ходов, которое длится игра. Если t = 0, то игра сразу же завершается. В противном случае, в каждый ход i игрок кидает кубик. После броска, если i < t, игрок может или прекратить игру и получить приз, равный только что выкинутому числу, или перекинуть кубик следующим ходом. Если i = t, тогда кубик нельзя перекинуть и приз должен быть принят игроком. Перед началом игры t выбирается игроком, который затем должен оплатить аванс в размере ct для постоянного c. При c = 0 t может быть выбрано бесконечно большим (с авансом равным 0). Пусть R(d, c) будет ожидаемой чистой прибылью, которую игрок получит от одной оптимально сыгранной игры в Рамвок, используя честный d-гранный кубик, с ценовой постоянной c. Например, R(4, 0.2) = 2.65. Предполагается, что у игрока достаточно денег, чтобы оплатить аванс любого размера.

Теперь рассмотрим игру Супер Рамвок:

В Супер Рамвок игра Рамвок играется несколько раз, но с небольшим дополнением: после каждой игры меняется кубик. Изменение кубика происходит следующим образом: кубик выкидывается один раз, и если на выброшенной грани видно ее значение, оно с нее стирается. Если же грань уже пуста, на нее возвращается ее изначальное значение. После этого изменения кубика можно начать следующую игру Рамвок (в течение которой на каждый ход кубик бросается до тех пор, пока не выпадет непустая грань). Игрок в любой момент знает, какие грани стерты, а какие - нет. Игра в Супер Рамвок заканчивается, когда все грани кубика становятся пустыми.

Пусть S(d, c) будет ожидаемой чистой прибылью, которую игрок получит от одной оптимально сыгранной игры в Супер Рамвок, используя честный d-гранный кубик (изначально на всех гранях видны их значения), с ценовой постоянной c. Например, S(6, 1) = 208.3.

Пусть F(n) = 4≤dn 0≤cn S(d, c).

Рассчитайте F(20), округленное до ближайшего целого.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net