Codeforces Round #802(Div. 2)A~D

Problem - A - Codeforces

You are given a table a of size n×m. We will consider the table rows numbered from top to bottom from 1 to n, and the columns numbered from left to right from 1 to m. We will denote a cell that is in the i-th row and in the j-th column as (i,j). In the cell (i,j) there is written a number (i−1)⋅m+j, that is aij=(i−1)⋅m+j.

A turtle initially stands in the cell (1,1) and it wants to come to the cell (n,m). From the cell (i,j) it can in one step go to one of the cells (i+1,j) or (i,j+1), if it exists. A path is a sequence of cells in which for every two adjacent in the sequence cells the following satisfies: the turtle can reach from the first cell to the second cell in one step. A cost of a path is the sum of numbers that are written in the cells of the path.

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-pAemaVxs-1656142330529)(https://espresso.codeforces.com/9857613b5dbdfcc9e89d5add1183537c52368425.png)]

For example, with n=2 and m=3 the table will look as shown above. The turtle can take the following path: (1,1)→(1,2)→(1,3)→(2,3). The cost of such way is equal to a11+a12+a13+a23=12. On the other hand, the paths (1,1)→(1,2)→(2,2)→(2,1) and (1,1)→(1,3) are incorrect, because in the first path the turtle can’t make a step (2,2)→(2,1), and in the second path it can’t make a step (1,1)→(1,3).

You are asked to tell the turtle a minimal possible cost of a path from the cell (1,1) to the cell (n,m). Please note that the cells (1,1) and (n,m) are a part of the way.

Input

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

A single line of each test case contains two integers n and m (1≤n,m≤104) — the number of rows and columns of the table a respectively.

Output

For each test case output a single integer — a minimal possible cost of a path from the cell (1,1) to the cell (n,m).

Example

input

7
1 1
2 3
3 2
7 1
1 10
5 5
10000 10000

output

1
12
13
28
55
85
500099995000

Problem analysis

The title is to give you a n*m Matrix , You can only go right or down at a time , How much is the lowest price for you to walk from top left to bottom right .

The lowest price is to go right first and then go down , The price is a The first item is 1 The tolerance is 1 Before the arithmetic sequence of m Xiang He add The first item is m, The tolerance is m Before the arithmetic sequence of n Xiang He Subtract one m.

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        cout << (m * (m + 1) / 2) + ((n * m * n + m * n) / 2) - m << endl;
    }
    return 0;
}

Problem - B - Codeforces

During a daily walk Alina noticed a long number written on the ground. Now Alina wants to find some positive number of same length without leading zeroes, such that the sum of these two numbers is a palindrome.

Recall that a number is called a palindrome, if it reads the same right to left and left to right. For example, numbers 121,66,98989121,66,98989 are palindromes, and 103,239,1241103,239,1241 are not palindromes.

Alina understands that a valid number always exist. Help her find one!

Input

The first line of input data contains an integer tt (1≤t≤1001≤t≤100) — the number of test cases. Next, descriptions of tt test cases follow.

The first line of each test case contains a single integer nn (2≤n≤1000002≤n≤100000) — the length of the number that is written on the ground.

The second line of contains the positive nn-digit integer without leading zeroes — the number itself.

It is guaranteed that the sum of the values nn over all test cases does not exceed 100000100000.

Output

For each of tt test cases print an answer — a positive nn-digit integer without leading zeros, such that the sum of the input integer and this number is a palindrome.

We can show that at least one number satisfying the constraints exists. If there are multiple solutions, you can output any of them.

Example

input

3
2
99
4
1023
3
385

output

32
8646
604

Problem analysis

The title is to give you a length of n Number of numbers , Let you find a number with the same length , To add these two numbers is a palindrome number .

Let's use a length of n It's all about it 9 Subtract the number he gives from the number he gives . Because there can be no leading zeros , If the first number is 9, Then we use a length of n+1 Is full of 1 Subtract the number it gives from the number it gives . A high-precision subtraction .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

vector<int> sub(vector<int>& A, vector<int>& B)
{
    vector<int>C;
    int t = 0;
    for (int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if (i < B.size())t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0)t = 1;
        else t = 0;
    }
    while (C.size() > 1 && !C.back())
        C.pop_back();
    return C;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        int n;
        cin >> n >> s;
        vector<int>a(n);
        for (int i = 0; i < n; i++)
        {
            a[i] = s[i] - '0';
        }
        
        vector<int>b(n,9);
        if (a[0] == 9)
        {
            b.assign(n + 1, 1);
        }
        reverse(a.begin(), a.end());
        auto c = sub(b, a);
        for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
        cout << endl;
    }
    return 0;
}

Problem - C - Codeforces

Little Leon lives in the forest. He has recently noticed that some trees near his favourite path are withering, while the other ones are overhydrated so he decided to learn how to control the level of the soil moisture to save the trees.

There are n trees growing near the path, the current levels of moisture of each tree are denoted by the array a1,a2,…,an. Leon has learned three abilities which will help him to dry and water the soil.

Choose a position i and decrease the level of moisture of the trees 1,2,…,i by 1.
Choose a position i and decrease the level of moisture of the trees i,i+1,…,n by 1.
Increase the level of moisture of all trees by 1.
Leon wants to know the minimum number of actions he needs to perform to make the moisture of each tree equal to 0.

Input

The first line contains a single integer t (1≤t≤2⋅104) — the number of test cases. The description of t test cases follows.

The first line of each test case contains a single integer n (1≤n≤200000).

The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109) — the initial levels of trees moisture.

It is guaranteed that the sum of n over all test cases doesn’t exceed 200000.

Output

For each test case output a single integer — the minimum number of actions. It can be shown that the answer exists.

Example

input

4
3
-2 -2 -2
3
10 4 7
4
4 -4 4 -4
5
1 -2 3 -4 5

output

2
13
36
33

Problem analysis

The title says to give you an array , You can put the front i All elements -1, Or the back i All elements -1, Or all +1, Ask how many steps it takes you to make it all 0.

See all the same , First think of the differential array , Just turn the difference group into 0, That is, all are 0 了 . Then convert these three operations , Namely ：

First element -1, The first i Elements +1;

The first i Elements -1;

First element +1;

Then we can traverse the difference group from end to end , According to its positive and negative conditions, see what operation can turn it all into 0, Just record the times of use on the way .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector <int> a(n), b(n);
        for (int i = 0; i < n; i++)cin >> a[i];
        b[0] = a[0];
        for (int i = 1; i < n; i++)
        {
            b[i] = a[i] - a[i - 1];
        }
        int res = 0;
        for (int i = n - 1; i > 0; i--)
        {
            if (b[i] > 0)
            {
                res += b[i];
            }
            else
            {
                res += abs(b[i]);
                b[0] += b[i];
            }
        }
        cout << res + abs(b[0]) << endl;
    }
    return 0;
}

Problem - D - Codeforces

Recently in Divanovo, a huge river locks system was built. There are now n locks, the i-th of them has the volume of vi liters, so that it can contain any amount of water between 0 and vi liters. Each lock has a pipe attached to it. When the pipe is open, 1 liter of water enters the lock every second.

The locks system is built in a way to immediately transfer all water exceeding the volume of the lock i to the lock i+1. If the lock i+1 is also full, water will be transferred further. Water exceeding the volume of the last lock pours out to the river.

Note that the volume of the i-th lock may be greater than the volume of the i+1-th lock.

To make all locks work, you need to completely fill each one of them. The mayor of Divanovo is interested in q independent queries. For each query, suppose that initially all locks are empty and all pipes are closed. Then, some pipes are opened simultaneously. For the j-th query the mayor asks you to calculate the minimum number of pipes to open so that all locks are filled no later than after tj seconds.

Please help the mayor to solve this tricky problem and answer his queries.

Input

The first lines contains one integer n (1≤n≤200000) — the number of locks.

The second lines contains n integers v1,v2,…,vn (1≤vi≤109)) — volumes of the locks.

The third line contains one integer q (1≤q≤200000) — the number of queries.

Each of the next q lines contains one integer tj (1≤tj≤109) — the number of seconds you have to fill all the locks in the query j.

Output

Print q integers. The j-th of them should be equal to the minimum number of pipes to turn on so that after tj seconds all of the locks are filled. If it is impossible to fill all of the locks in given time, print −1.

Examples

input

5
4 1 5 4 1
6
1
6
2
3
4
5

output

-1
3
-1
-1
4
3

Problem analysis

The title is for you n A container , The volume of each container is a[i], They have a tap on each head , After opening 1 One unit of water can be added to the container below in seconds , If the container below is full , Water will enter the next container , Then there is m Questions , Give you a time every time , Ask if you can fill all the containers within the specified time , If possible , Use at least a few taps , If not, output -1.

You can know , Try to turn on the faucet in front of you , Even if it is currently full, it can be added to the back , Then we can assume that every tap is on , Then calculate the minimum time it takes to fill each container , If you give less time to ask questions , Then it must be -1. Then we can find out the number of faucets in two , Fill all containers , Then the tap should be able to flow out within the time he gives （a[0]+a[1]+……a[n-1]) Unit water , We just need to calculate how many taps we can turn on to meet it .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, mn = -1, res = 0;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        res += a[i];
        int x = res / (i+1);
        if (res % (i+1) != 0)x++;
        mn = max(mn, x);
    }
    cin >> m;
    while (m--)
    {
        int x;
        cin >> x;
 
        if (x < mn)
        {
            cout << -1 << endl;
            continue;
        }
        int l = 0, r = n + 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (x * mid >= res)r = mid;
            else l = mid + 1;
        }
        if (l == n + 1)cout << -1 << endl;
        else cout << l << endl;
    }
    return 0;
}