クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-7 Millionaire（2008 APAC local onsites C）」(p.123)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-7 Millionaire（2008 APAC local onsites C）」(p.123)
のコードをPythonで書き直したものとなっています。

入力


M\,X\\P

入力例1



1 500000
0.5

入力例2



3 600000
0.75


解答

MAX_M = 15

# 入力
M, X = map(int,input().split())
P = float(input())

dp = [[0] * ((1 << MAX_M) + 1) for _ in range(2)]

n = 1 << M

prv = dp[0]
nxt = dp[1]
prv[n] = 1

for r in range(M):
    for i in range(n + 1):
        jub = min(i, n - i)
        t = 0
        for j in range(jub + 1):
            t = max(t, P * prv[i + j] + (1 - P) * prv[i - j])
        nxt[i] = t
    prv, nxt = nxt, prv

i = X * n // 1000000
print(prv[i])