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

Problem - A - Codeforces

There is an array a with n−1 integers. Let x be the bitwise XOR of all elements of the array. The number x is added to the end of the array a (now it has length n), and then the elements are shuffled.

You are given the newly formed array a. What is x? If there are multiple possible values of x, you can output any of them.

Input

The input consists of multiple test cases. The first line contains an 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 an integer n (2≤n≤100) — the number of integers in the resulting array a.

The second line of each test case contains n integers a1,a2,…,an (0≤ai≤127) — the elements of the newly formed array a.

Additional constraint on the input: the array a is made by the process described in the statement; that is, some value of x exists.

Output

For each test case, output a single integer — the value of x, as described in the statement. If there are multiple possible values of x, output any of them.

Example

input

4
4
4 3 2 5
5
6 1 10 7 10
6
6 6 6 6 6 6
3
100 100 0

output

3
7
6
0

Problem analysis

The title is that there is a length of n Array of , This array can have n-1 The number goes on xor Get the remaining number after operation , Let you find out which number in the array is .

Length only 100, Directly enumerate all the numbers in the array , See if you can get this number after other number XOR operations .

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;

void solve()
{
    int n;
    cin >> n;
    vector<int>a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        int x = 0;
        for (int j = 0; j < n; j++)
        {
            if (j != i)x ^= a[j];
        }
        if (x == a[i])
        {
            cout << a[i] << endl;
            return;
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Problem - B - Codeforces

There are n piles of sand where the i-th pile has ai blocks of sand. The i-th pile is called too tall if 1<iai−1+ai+1. That is, a pile is too tall if it has more sand than its two neighbours combined. (Note that piles on the ends of the array cannot be too tall.)

You are given an integer k. An operation consists of picking k consecutive piles of sand and adding one unit of sand to them all. Formally, pick 1≤l,r≤n such that r−l+1=k. Then for all l≤i≤r, update ai←ai+1.

What is the maximum number of piles that can simultaneously be too tall after some (possibly zero) operations?

Input

The input consists of multiple test cases. The first line contains an 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 two integers n and k (3≤n≤2⋅105; 1≤k≤n) — the number of piles of sand and the size of the operation, respectively.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the sizes of the piles.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, output a single integer — the maximum number of piles that are simultaneously too tall after some (possibly zero) operations.

Example

input

3
5 2
2 9 2 4 1
4 4
1 3 2 1
3 1
1 3 1

output

2
0
1

Problem analysis

The title is to give you an array a, call a[i]>a[i-1]+a[i+1] The element of is the mountain , And then there's an operation , You can choose one with a length of k The range of , Put all the elements in this interval +1, Ask how many peak elements can be in the array after any operation .

If k be equal to 1, We can turn any element into a mountain , But at most there can be （n-1)/2 A mountain , Because the two sides of each mountain element are definitely not mountain elements .

If k Greater than 1, Then we can't turn a non peak element into a peak element , Because if an element itself is not a mountain element , It indicates that this value is not greater than the sum of the elements on both sides , If k Greater than 1, Then we can only increase one of the two neighbors , Or increase neighbors and this element at the same time , This will not increase a[i] Make it larger than a[i-1]+a[i+1]. So if k Greater than 1, Then the original array has several mountain elements , Just a few mountain elements .

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;

void solve()
{
    int n, k, res = 0;
    cin >> n >> k;
    vector<int>a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    if (k == 1)
    {
        cout << (n - 1) / 2 << endl;
        return;
    }
    for (int i = 1; i < n - 1; i++)
    {
        if (a[i] > a[i - 1] + a[i + 1])res++;
    }
    cout << res << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Problem - C - Codeforces

You are given an array a of length n. The array is called 3SUM-closed if for all distinct indices i, j, k, the sum ai+aj+ak is an element of the array. More formally, a is 3SUM-closed if for all integers 1≤i<j<k≤n, there exists some integer 1≤l≤n such that ai+aj+ak=al.

Determine if a is 3SUM-closed.

Input

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

The first line of each test case contains an integer n (3≤n≤2⋅105) — the length of the array.

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

It is guaranteed that the sum of n across all test cases does not exceed 2⋅105.

Output

For each test case, output “YES” (without quotes) if a is 3SUM-closed 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

4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4

output

YES
NO
YES
NO

Problem analysis

The title is to give you a length of n Array of a, As long as any three elements of this array add up, it can be an element of this array , This array is called 3sum closed , Ask you if this array is 3sum Closed .

When the array is all 0, He is satisfied .

When an array is not except for a number 0, Other numbers are 0 when , He is satisfied .

When the array except two numbers is not 0, Other numbers are 0, And these two numbers add up to 0 when , He is satisfied .

When the array has no 0 when , We need to discuss the situation ：

​ When there are three positive numbers in the array , Then add three positive numbers together to get a larger positive number , This is definitely not enough .

​ When there are three negative numbers in the array , Then add the three negative numbers together to get a smaller negative number , This is definitely not enough .

​ So , There cannot be three positive numbers or three negative numbers in the array , That is, the array is at most 4 Elements can be right , If you exceed this number, you may be wrong , For convenience , We directly use a three-tier for Cycle to judge whether the conditions are met .

The rest are not satisfied .

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;

void solve()
{
    int n;
    cin >> n ;
    vector<int>v(n),ans;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        
        if (v[i] != 0)
        {
            ans.push_back(v[i]);
        }
    }
    
    if (ans.size() <= 1)cout << "YES" << endl;
    else if (ans.size() == 2)
    {
        if (ans[0] + ans[1] == 0)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    else if (n < 10)
    {
        map<int, int>mymap;
        for (int i = 0; i < n; i++)
        {
            mymap[v[i]] = 1;
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if (i != j && j != k && i != k)
                    {
                        if (mymap[v[i] + v[j] + v[k]] == 0)
                        {
                            cout << "NO" << endl;
                            return;
                        }
                    }
                }
            }
            
        }
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}