Codeforces Round #800 (Div. 2)A~C

Problem - A - Codeforces

Define the score of some binary string TT as the absolute difference between the number of zeroes and ones in it. (for example, T=T= 010001 contains 44 zeroes and 22 ones, so the score of TT is |4−2|=2|4−2|=2).
Define the creepiness of some binary string SS as the maximum score among all of its prefixes (for example, the creepiness of S=S= 01001 is equal to 22 because the score of the prefix S[1…4]S[1…4] is 22 and the rest of the prefixes have a score of 22 or less).
Given two integers aa and bb, construct a binary string consisting of aa zeroes and bb ones with the minimum possible creepiness.

Input

The first line contains a single integer tt (1≤t≤1000)(1≤t≤1000) — the number of test cases. The description of the test cases follows.
The only line of each test case contains two integers aa and bb (1≤a,b≤1001≤a,b≤100) — the numbers of zeroes and ones correspondingly.

Output

For each test case, print a binary string consisting of aa zeroes and bb ones with the minimum possible creepiness. If there are multiple answers, print any of them.

Example

input

5
1 1
1 2
5 2
4 5
3 7

output

10
011
0011000
101010101
0001111111

Problem analysis

The question is , A string consists only of 01 form , The score of this string is 0 The number of and 1 The difference in the number of , The threat degree of this string is the maximum score of all its substrings , Here you are. a individual 0 and b individual 1, Make a string , Keep his threat to a minimum .

Just put 01 Output alternately , Put the extra at the end of the output .

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 a, b;
        cin >> a >> b;
        if (a > b)
        {
            for (int i = 0; i < b; i++)cout << "01";
            for (int i = 0; i < a - b; i++)cout << 0;
        }
        else
        {
            for (int i = 0; i < a; i++)cout << "10";
            for (int i = 0; i < b - a; i++)cout << 1;
        }
        cout << endl;
    }

    return 0;
}

Problem - B - Codeforces

Let’s call a binary string T of length m indexed from 1 to m paranoid if we can obtain a string of length 1 by performing the following two kinds of operations m−1 times in any order :

Select any substring of T that is equal to 01, and then replace it with 1.
Select any substring of T that is equal to 10, and then replace it with 0.
For example, if T= 001, we can select the substring [T2T3] and perform the first operation. So we obtain T= 01.

You are given a binary string S of length n indexed from 1 to n. Find the number of pairs of integers (l,r) 1≤l≤r≤n such that S[l…r] (the substring of S from l to r) is a paranoid string.

Input

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

The first line of each test case contains a single integer n (1≤n≤2⋅105) — the size of S.

The second line of each test case contains a binary string S of n characters S1S2…Sn. (Si= 0 or Si= 1 for each 1≤i≤n)

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

Output

For each test case, output the number of pairs of integers (l,r) 1≤l≤r≤n such that S[l…r] (the substring of S from l to r) is a paranoid string.

Example

input

5
1
1
2
01
3
100
4
1001
5
11111

output

1
3
4
8
5

Problem analysis

The hint is to give you a string , Only by 0 and 1 form , There are two operations , You can put a substring “01” become “1”,“10” become “0”, Ask how many substrings of this string can be changed into one character through these two operations .

It can be seen that , As long as the end is “11” or “00” It is impossible for a string to become a character . We just need to find the substring that ends with these two , Then subtract the special number of substrings from all the substrings .

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;
        string s;
        cin >> n >> s;
        int res = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (s[i] == '0' && s[i + 1] == '0')res += i+1;
            if (s[i] == '1' && s[i + 1] == '1')res += i+1;
        }
        cout << n * (n + 1) / 2 - res << endl;
    }

    return 0;
}

Problem - C - Codeforces

We have an array of length n. Initially, each element is equal to 0 and there is a pointer located on the first element.

We can do the following two kinds of operations any number of times (possibly zero) in any order:

If the pointer is not on the last element, increase the element the pointer is currently on by 1. Then move it to the next element.
If the pointer is not on the first element, decrease the element the pointer is currently on by 1. Then move it to the previous element.
But there is one additional rule. After we are done, the pointer has to be on the first element.

You are given an array a. Determine whether it’s possible to obtain a after some operations or not.

Input

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

The first line of each test case contains a single integer n (1≤n≤2⋅105) — the size of array a.

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

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

Output

For each test case, print “Yes” (without quotes) if it’s possible to obtain a after some operations, and “No” (without quotes) otherwise.

You can output “Yes” and “No” in any case (for example, strings “yEs”, “yes” and “Yes” will be recognized as a positive response).

Example

input

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

output

No
Yes
No
No
Yes
Yes
Yes

Problem analysis

The title is that there is a length of n Array of , At first, the elements were all 0, Then there are two operations , If the current pointer is not in the last element , Then you can make this element +1 Move back to the back , If not in the first element , You can make this element -1 Move backward and forward . Give you an array a, Ask if you can change this initial array into a, And then the pointer should point to the first element .

First of all, we can know , The last one is not 0 Elements must be negative , Because you have to subtract 1, And want to add 1 You need to go back , But the last one is not 0 The element is obviously not going backwards , Only forward , Then it can't be negative ; Similarly, you can know that the first element can only be a positive number .

Then we can also know , If a number goes forward , It must be the following number -1 了 , If a number wants to increase, the corresponding subsequent number must decrease , And because the pointer finally stops in the first place , It is equivalent to that the number of times to go left and right is the same , That is, the sum of the entire array should be 0, If it is expressed as a prefix and, it is from the beginning to the last non 0 The prefix sum of numbers is 0, The prefix sum of other positions cannot be less than or equal to 0, If it is less than 0, Then this position can't go back to the first position . If it is equal to 0, Then he can't walk backwards .

So the conclusion is ： The first element of the array must be a positive number , The last number is not 0 Number must be negative , Prefix and except to the last non 0 The prefix sum of the number position is 0, The prefix sum of the previous position must be greater than 0.

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, res = 0;
        cin >> n;
        vector<int>v(n);
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
        }
        while (!v.empty() && v.back() == 0)v.pop_back();
        n = v.size();
        bool flag = true;
        for (int i = 0; i < n; i++)
        {
            res += v[i];
            if (i != n - 1 && res <= 0)
            {
                flag = false;
                break;
            }
        }
        if (res != 0)
        {
            flag = false;
        }
        if (!flag)cout << "No" << endl;
        else cout << "Yes" << endl;
    }

    return 0;
}