У вас есть статистика роста цен некоторого товара в виде массива из \(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\) %?
Выходные данные
Для каждого набора входных данных выведите наименьшую сумму изменений, которые сделают все коэффициенты инфляции не превосходящими \(k\) %.
Примечание
В первом наборе входных данных, вы можете, например, увеличить \(p_0\) на \(50\) и \(p_1\) на \(49\) и получить массив \([20150, 50, 202, 202]\). Тогда у вас получатся следующие коэффициенты инфляции:
- \(\frac{50}{20150} \le \frac{1}{100}\);
- \(\frac{202}{20150 + 50} \le \frac{1}{100}\);
- \(\frac{202}{20200 + 202} \le \frac{1}{100}\);
Во втором наборе, вам не нужно модифицировать массив \(p\), так как все коэффициенты инфляции уже подходят:
- \(\frac{1}{1} \le \frac{100}{100}\);
- \(\frac{1}{1 + 1} \le \frac{100}{100}\);
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 1
20100 1 202 202
3 100
1 1 1
|
99
0
|