AT_arc085_a.[ABC078C] HSI

高桥君正在参加一场编程竞赛，需要解答一些只需要回答“YES”或“NO”的问题，但他因为程序超时（TLE）未能通过。

查看提交详情后，发现一共有 $N$ 个测试用例，其中有 $M$ 个用例发生了 TLE。

于是，高桥君将程序改写如下：对于 $M$ 个会TLE的用例，每个用例执行时间为 $1900$ ms，且每个用例以 $1/2$ 的概率正确；剩下的 $N-M$ 个用例，每个执行时间为 $100$ ms，并且总是正确。

高桥君接下来的操作如下：

• 提交该程序。
• 等待所有测试用例执行完毕。
• 如果 $M$ 个用例中有任意一个未通过，则重新提交程序。
• 上述流程一直重复，直到有一次所有用例全部通过。

设在整个过程中，程序的运行时间总和的期望值为 $X$ ms。请输出 $X$。

注意：$X$ 需要输出为整数。

输入为一行，包括两个整数：

$N\ M$

输出程序运行时间总和的期望值 $X$，输出为一个整数。可以证明，在本题限制条件下，$X$ 是不超过 $10^9$ 的整数。

约束条件

• 输入均为整数
• $1 \leq N \leq 100$
• $1 \leq M \leq \min(N, 5)$

样例解释1

本例中只有 $1$ 个测试用例，这个用例会超时，每次执行用时 $1900$ ms，且只有 $1/2$ 的概率正确。因此第一次就全部通过的概率为 $1/2$，第二次才全部通过的概率为 $1/4$，第三次才全部通过的概率为 $1/8$，依此类推。因此答案为 $1900 \times 1/2 + (2 \times 1900) \times 1/4 + (3 \times 1900) \times 1/8 + \cdots = 3800$。

样例解释2

有 $2$ 个用例需要 $1900$ ms 的执行时间，其余 $10-2=8$ 个用例各需 $100$ ms。所有用例全部通过的概率为 $1/2 \times 1/2 = 1/4$。

由 ChatGPT 5 翻译