← 返回题目列表

Codeforces · 1476/B

B. 通货膨胀

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

您有一个产品的价格变化统计数据,以 $$$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$$$ % 所需的最小更改总和。

示例

输入 #1

2
4 1
20100 1 202 202
3 100
1 1 1

输出 #1

99
0

注意

在第一个测试用例中,例如,您可以将 $$$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}$$$;