← 返回题目列表

AtCoder · arc085_a

C. 恒生指数

中文机器翻译题面 查看原题

分数: 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