У вас есть статистика роста цен некоторого товара в виде массива из $$$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$$$ %.
2 4 1 20100 1 202 202 3 100 1 1 1
99 0
В первом наборе входных данных, вы можете, например, увеличить $$$p_0$$$ на $$$50$$$ и $$$p_1$$$ на $$$49$$$ и получить массив $$$[20150, 50, 202, 202]$$$. Тогда у вас получатся следующие коэффициенты инфляции:
Во втором наборе, вам не нужно модифицировать массив $$$p$$$, так как все коэффициенты инфляции уже подходят:
Название |
---|