分数: 300 点
问题陈述
Takahashi 现在正在参加编程竞赛,但他在一个问题中获得了 TLE,答案是 YES or NO.
当他查看提交的详细状态时,有 N 问题中的测试用例,并且代码收到 TLE M 这些案例。
然后,他重写了代码以正确解决每个问题 M 案例 1/2 概率在 1900 毫秒,并正确解决其他每个问题 N-M 案例无一失败 100 毫秒。
现在,他经历了以下过程:
- 提交代码。
- 等待代码完成所有情况的执行。
- 如果代码无法正确解决某些问题 M 案例,请重新提交。
- 重复,直到代码在一次提交中正确解决所有情况。
令代码总执行时间的期望值为 X 毫秒。打印 X (作为整数)。
约束
- 所有输入值均为整数。
- 1 \leq N \leq 100
- 1 \leq M \leq {\rm min}(N, 5)
输入
输入由标准输入按以下格式给出:
N M
输出
打印 X,代码总执行时间的预期值,作为整数。可以证明,在本问题的约束条件下, X 是一个不超过的整数 10^9.
示例输入 1
1 1
示例输出 1
3800
在此输入中,只有一种情况。高桥将重复提交正确解决此案例的代码 1/2 概率在 1900 毫秒。
该代码一次尝试就会成功 1/2 概率,在两次尝试中 1/4 概率,并且在三次尝试中 1/8 概率,等等。
因此,答案是 1900 \times 1/2 + (2 \times 1900) \times 1/4 + (3 \times 1900) \times 1/8 + ... = 3800.
示例输入 2
10 2
示例输出 2
18400
代码将采取 1900 毫秒 2 案例,以及 100 毫秒 10-2=8 案例。代码正确解决所有情况的概率是 1/2 \times 1/2 = 1/4.
示例输入 3
100 5
示例输出 3
608000