Project Euler 286

Project Euler 286

题目

Scoring probabilities

Barbara is a mathematician and a basketball player. She has found that the probability of scoring a point when shooting from a distance x is exactly (1xq), where q is a real constant greater than 50.

During each practice run, she takes shots from distances x=1,x=2,,x=50 and, according to her records, she has precisely a 2% chance to score a total of exactly 20 points.

Find q and give your answer rounded to 10 decimal places.

解决方案

N=50,M=20,Q=0.02。如果 q 值确定了,那么可以使用动态规划的思想计算投篮 N 次,命中恰好 M 次的概率。

假设状态 f(i,j)(0iN,0jmin(i,M)) 为已经投篮了 i 次,恰好命中了 j 次的概率,那么不难写出如下状态转移方程:

f(i,j)={0ifi=0f(i1,j)iqelse ifj=0f(i1,j1)(1iq)elseifj=if(i1,j)iq+f(i1,j1)(1iq)else

对于方程最后一行,前一项从 f(i1,j) 时投篮不中转移过来,后一项则从 f(i1,j1) 时投篮命中转移过来。

q=50 时,发现 f(N,M) 约为 0.0412,随着 q 的上升,发现 f(N,M) 下降得很快,因此考虑进行浮点数上的二分:如果 f(N,M)>Q,那么说明 q 太小,否则 q 太大。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
N = 50
M = 20
Q = 0.02
l = N
r = N << 1
for _ in range(100):
q = 0.5 * (l + r)
f = [[0 for i in range(M + 1)] for j in range(N + 1)]
f[0][0] = 1
for i in range(1, N + 1):
rt = 1 - i / q
for j in range(min(i, M) + 1):
if j > 0:
f[i][j] += f[i - 1][j - 1] * rt
if j < i:
f[i][j] += f[i - 1][j] * (1 - rt)
if f[N][M] > Q:
l = q
else:
r = q
ans = l
print("{:.10f}".format(ans))