B. Inflation-Educational Codeforces Round 103 (Rated for Div. 2)

Problem - 1476B - Codeforces

B. Inflation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You have a statistic of price changes for one product represented as an array of nn positive integers p0,p1,…,pn−1p0,p1,…,pn−1, where p0p0 is the initial price of the product and pipi is how the price was increased during the ii-th month.

Using these price changes you are asked to calculate the inflation coefficients for each month as the ratio of current price increase pipi to the price at the start of this month (p0+p1+⋯+pi−1)(p0+p1+⋯+pi−1).

Your boss said you clearly that the inflation coefficients must not exceed kk %, so you decided to increase some values pipi in such a way, that all pipi remain integers and the inflation coefficients for each month don't exceed kk %.

You know, that the bigger changes — the more obvious cheating. That's why you need to minimize the total sum of changes.

What's the minimum total sum of changes you need to make all inflation coefficients not more than kk %?

Input

The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains two integers nn and kk (2≤n≤1002≤n≤100; 1≤k≤1001≤k≤100) — the length of array pp and coefficient kk.

The second line of each test case contains nn integers p0,p1,…,pn−1p0,p1,…,pn−1 (1≤pi≤1091≤pi≤109) — the array pp.

Output

For each test case, print the minimum total sum of changes you need to make all inflation coefficients not more than kk %.

Example

input

Copy

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

output

Copy

99
0

Note

In the first test case, you can, for example, increase p0p0 by 5050 and p1p1 by 4949 and get array [20150,50,202,202][20150,50,202,202]. Then you get the next inflation coefficients:

1. 5020150≤11005020150≤1100;
2. 20220150+50≤110020220150+50≤1100;
3. 20220200+202≤110020220200+202≤1100;

In the second test case, you don't need to modify array pp, since the inflation coefficients are already good:

1. 11≤10010011≤100100;
2. 11+1≤10010011+1≤100100;

=========================================================================

常规做法肯定是线性推一遍，大于k了就增加分母，这种方法没有什么不对的，但是本题必须加正整数，而正因为这样，模数不为零的存在让我们频繁多加1，最终导致了答案总是不那么精确。

为了减少加1的次数，我们统一将加数加在p1上，枚举前缀和计算最大加数即可，这里顶多会加1,。

# include<iostream>
 
using namespace std;
 
typedef long long int  ll;
 
ll  p[1000];
ll sum[1000];
 
int main ()
{
 
    int t;
 
    cin>>t;
 
    while(t--)
    {
        int n;
        cin>>n;
        ll k;
 
        cin>>k;
 
        for(int i=1;i<=n;i++)
        {
            cin>>p[i];
 
            sum[i]=sum[i-1]+p[i];
 
        }
 
        ll ans=0;
 
 
        for(int i=2;i<=n;i++)
        {
            if(k*sum[i-1]<100*p[i])
            {
                ll t=100*p[i]-k*sum[i-1];
 
                ll d=t/k;
                if(t%k)
                    d++;
 
                ans=max(ans,d);
 
            }
        }
 
        cout<<ans<<endl;
 
 
    }
 
    return 0;
 
}