CF1476B Inflation

你有一个商品价格变动的统计数据，用一个长度为 $n$ 的正整数数组 $p_0, p_1, \dots, p_{n-1}$ 表示，其中 $p_0$ 是商品的初始价格，$p_i$ 表示第 $i$ 个月价格的上涨额。 根据这些价格变动，你需要计算每个月的通胀系数，定义为当前月价格上涨额 $p_i$ 与本月开始时价格 $p_0 + p_1 + \dots + p_{i-1}$ 的比值。 你的老板明确要求，每个月的通胀系数不能超过 $k$%，因此你决定适当增加某些 $p_i$ 的值，使得所有 $p_i$ 仍为整数，并且每个月的通胀系数都不超过 $k$%。 你知道，改动越大越容易被发现作弊。因此你需要最小化所有改动的总和。 请问，最少需要增加多少总和，才能使所有通胀系数都不超过 $k$%？

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 100$；$1 \le k \le 100$），分别表示数组 $p$ 的长度和系数 $k$。 每个测试用例的第二行包含 $n$ 个整数 $p_0, p_1, \dots, p_{n-1}$（$1 \le p_i \le 10^9$），表示数组 $p$。

对于每个测试用例，输出一个整数，表示最少需要增加的总和，使得所有通胀系数都不超过 $k$%。

在第一个测试用例中，你可以例如将 $p_0$ 增加 $50$，将 $p_1$ 增加 $49$，得到数组 $[20150, 50, 202, 202]$。此时各月的通胀系数如下： 1. $\frac{50}{20150} \le \frac{1}{100}$； 2. $\frac{202}{20150 + 50} \le \frac{1}{100}$； 3. $\frac{202}{20200 + 202} \le \frac{1}{100}$。 在第二个测试用例中，无需修改数组 $p$，因为通胀系数已经满足要求： 1. $\frac{1}{1} \le \frac{100}{100}$； 2. $\frac{1}{1 + 1} \le \frac{100}{100}$。 由 ChatGPT 4.1 翻译