JAG Spring Contest 2015

提交地址

Overview:

做 ASC 42 的 B 題的時候遇到的問題。。。ASC 42 的題目是:
初始有 m 元錢,目標是恰好擁有 n 元錢
每輪你可以壓至多當前你所擁有的錢數進行賭博,p 的概率翻倍,q 的概率失去賭注。
至多進行 t 個回合,問最優策略下達到目標的概率。
(t <= 300, p < 50。)

YY 了一下結論,假設當前有 m 元錢,每次壓 min(m, n-m) 就可以了。
加之題目限制很強,模擬 DP 一下就出來了。在 camp 群里遂問了一下 p >= 50 的情況下結論還成立嗎。。
果然有完整版的題目。

ゆっくり読んでください ...