A. Division?

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

Codeforces separates its users into 4 divisions by their rating:

For Division 1: 1900≤rating

For Division 2: 1600≤rating≤1899

For Division 3: 1400≤rating≤1599

For Division 4: rating≤1399

Given a rating, print in which division the rating belongs.

Input

The first line of the input contains an integer t (1≤t≤104) — the number of testcases.

The description of each test consists of one line containing one integer rating (−5000≤rating≤5000).

Output

For each test case, output a single line containing the correct division in the format "Division X&#​34;, where X is an integer between 1 and 4 representing the division for the corresponding rating.

Example

inputCopy

7

-789

1299

1300

1399

1400

1679

2300

outputCopy

Division 4

Division 4

Division 4

Division 4

Division 3

Division 2

Division 1

Note

For test cases 1−4, the corresponding ratings are −789, 1299, 1300, 1399, so all of them are in division 4.

For the fifth test case, the corresponding rating is 1400, so it is in division 3.

For the sixth test case, the corresponding rating is 1679, so it is in division 2.

For the seventh test case, the corresponding rating is 2300, so it is in division 1.

/*
直接判断输出答案
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
void solve()
{
	int n;
    cin>>n;
    if(n<=1399){
        cout<<"Division 4"<<endl;
    }
    else if(n<=1599){
        cout<<"Division 3"<<endl;
    }
    else if(n<=1899){
        cout<<"Division 2"<<endl;
    }
    else{
        cout<<"Division 1"<<endl;
    }
}
signed main()
{
	int __;
	cin>>__;
	//__=1;
	while(__--)solve();
}

B. Triple

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

Given an array a of n elements, print any value that appears at least three times or print -1 if there is no such value.

Input

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

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

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

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

Output

For each test case, print any value that appears at least three times or print -1 if there is no such value.

Example

inputCopy

7

1

1

3

2 2 2

7

2 2 3 3 4 2 2

8

1 4 3 4 3 2 4 1

9

1 1 1 2 2 2 3 3 3

5

1 5 2 4 3

4

4 4 4 4

outputCopy

-1

2

2

4

3

-1

4

Note

In the first test case there is just a single element, so it can't occur at least three times and the answer is -1.

In the second test case, all three elements of the array are equal to 2, so 2 occurs three times, and so the answer is 2.

For the third test case, 2 occurs four times, so the answer is 2.

For the fourth test case, 4 occurs three times, so the answer is 4.

For the fifth test case, 1, 2 and 3 all occur at least three times, so they are all valid outputs.

For the sixth test case, all elements are distinct, so none of them occurs at least three times and the answer is -1.

/*
排序，暴力。考虑到题目给的是t<=1e4 n<=2e5使用vis数组暴力不可行
于是选择先排序然后一个个遍历查找有没有连续出现三个及以上的数字
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int n;
int a[200005];
void solve()
{
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(n<=2){
        cout<<-1<<endl;
        return;
    }
    sort(a+1,a+1+n);
    int flag=0;
    int sum=0,ta,ans;
    ta=a[1];
    for(int i=1;i<=n;i++){
        if(ta==a[i]){
            sum++;
            if(sum==3){
                flag=1;
                ans=ta;
                break;
            }
        }
        else{
            sum=1;
            ta=a[i];
        }
    }
    if(flag){
        cout<<ans<<endl;
    }
    else cout<<-1<<endl;
}
signed main()
{
	int __;
	cin>>__;
	//__=1;
	while(__--)solve();
}

C. Odd/Even Increments

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

Given an array a=[a1,a2,…,an] of n positive integers, you can do operations of two types on it:

Add 1 to every element with an odd index. In other words change the array as follows: a1:=a1+1,a3:=a3+1,a5:=a5+1,….

Add 1 to every element with an even index. In other words change the array as follows: a2:=a2+1,a4:=a4+1,a6:=a6+1,….

Determine if after any number of operations it is possible to make the final array contain only even numbers or only odd numbers. In other words, determine if you can make all elements of the array have the same parity after any number of operations.

Note that you can do operations of both types any number of times (even none). Operations of different types can be performed a different number of times.

Input

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

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

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

Note that after the performed operations the elements in the array can become greater than 103.

Output

Output t lines, each of which contains the answer to the corresponding test case. As an answer, output "YES&#​34; if after any number of operations it is possible to make the final array contain only even numbers or only odd numbers, and "NO&#​34; otherwise.

You can output the answer in any case (for example, the strings "yEs&#​34;, "yes&#​34;, "Yes&#​34; and "YES&#​34; will be recognized as a positive answer).

Example

inputCopy

4

3

1 2 1

4

2 2 2 3

4

2 2 2 2

5

1000 1 1000 1 1000

outputCopy

YES

NO

YES

YES

Note

For the first test case, we can increment the elements with an even index, obtaining the array [1,3,1], which contains only odd numbers, so the answer is "YES&#​34;.

For the second test case, we can show that after performing any number of operations we won't be able to make all elements have the same parity, so the answer is "NO&#​34;.

For the third test case, all elements already have the same parity so the answer is "YES&#​34;.

For the fourth test case, we can perform one operation and increase all elements at odd positions by 1, thus obtaining the array [1001,1,1001,1,1001], and all elements become odd so the answer is "YES&#​34;.

/*
考虑到索引奇数位和偶数位只能同时+1，当能使数组全部为同一奇偶性时，
单独看数组的奇数位和偶数位应当是同一奇偶性，判断即可
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int n;
int a[100];
void solve()
{
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int t1=a[1]&1,flag1=0;
    int t2=a[2]&1,flag2=0;
    for(int i=1;i<=n;i+=2){
        if(t1!=(a[i]&1)){
            flag1=1;
            break;
        }
    }
    for(int i=2;i<=n;i+=2){
        if(t2!=(a[i]&1)){
            flag2=1;
            break;
        }
    }
    if(flag1||flag2){
        cout<<"NO"<<endl;
    }
    else cout<<"YES"<<endl;
}
signed main()
{
	int __;
	cin>>__;
	//__=1;
	while(__--)solve();
}

D. Colorful Stamp

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

A row of n cells is given, all initially white. Using a stamp, you can stamp any two neighboring cells such that one becomes red and the other becomes blue. A stamp can be rotated, i.e. it can be used in both ways: as BR and as RB.

During use, the stamp must completely fit on the given n cells (it cannot be partially outside the cells). The stamp can be applied multiple times to the same cell. Each usage of the stamp recolors both cells that are under the stamp.

For example, one possible sequence of stamps to make the picture BRBBW could be WWWWW→WWRB–––W→BR–––RBW→BRB–––BW. Here W, R, and B represent a white, red, or blue cell, respectively, and the cells that the stamp is used on are marked with an underline.

Given a final picture, is it possible to make it using the stamp zero or more times?

Input

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

The first line of each test case contains an integer n (1≤n≤105) — the length of the picture.

The second line of each test case contains a string s — the picture you need to make. It is guaranteed that the length of s is n and that s only consists of the characters W, R, and B, representing a white, red, or blue cell, respectively.

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

Output

Output t lines, each of which contains the answer to the corresponding test case. As an answer, output "YES&#​34; if it possible to make the picture using the stamp zero or more times, and "NO&#​34; otherwise.

You can output the answer in any case (for example, the strings "yEs&#​34;, "yes&#​34;, "Yes&#​34; and "YES&#​34; will be recognized as a positive answer).

Example

inputCopy

12

5

BRBBW

1

B

2

WB

2

RW

3

BRB

3

RBB

7

WWWWWWW

9

RBWBWRRBW

10

BRBRBRBRRB

12

BBBRWWRRRWBR

10

BRBRBRBRBW

5

RBWBW

outputCopy

YES

NO

NO

NO

YES

YES

YES

NO

YES

NO

YES

NO

Note

The first test case is explained in the statement.

For the second, third, and fourth test cases, it is not possible to stamp a single cell, so the answer is "NO&#​34;.

For the fifth test case, you can use the stamp as follows: WWW→WRB–––→BR–––B.

For the sixth test case, you can use the stamp as follows: WWW→WRB–––→RB–––B.

For the seventh test case, you don't need to use the stamp at all.

/*
观察可以发现，其实在两个W中只有单独的R或B才是不存在的，其他的都可以用不同盖章方式实现
判断即可
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int n;
string s;
void solve()
{
	cin>>n;
    cin>>s;
    int r=0,b=0;
    int len=0;
    for(int i=0;i<n;i++){
        if(s[i]!='w'){
            len=i;break;
        }
    }
    int flag=0;
    //cout<<len<<endl;
    for(int i=len;i<n;i++){
        if(s[i]=='R')r++;
        if(s[i]=='B')b++;
        if(s[i]=='W'){
            if((r==0&&b!=0)||(r!=0&&b==0)){
                flag=1;
                break;
            }
            r=0;
            b=0;
        }
    }
    if((r==0&&b!=0)||(r!=0&&b==0))flag=1;
    //cout<<r<<" "<<b<<endl;
    if(!flag){
        cout<<"YES"<<endl;
    }
    else cout<<"NO"<<endl;

}
signed main()
{
	int __;
	cin>>__;
	//__=1;
	while(__--)solve();
}

E. 2-Letter Strings

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

Given n strings, each of length 2, consisting of lowercase Latin alphabet letters from 'a&#​39; to 'k&#​39;, output the number of pairs of indices (i,j) such that i<j and the i-th string and the j-th string differ in exactly one position.

In other words, count the number of pairs (i,j) (i<j) such that the i-th string and the j-th string have exactly one position p (1≤p≤2) such that sip≠sjp.

The answer may not fit into 32-bit integer type, so you should use 64-bit integers like long long in C++ to avoid integer overflow.

Input

The first line of the input contains a single integer t (1≤t≤100) — 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≤105) — the number of strings.

Then follows n lines, the i-th of which containing a single string si of length 2, consisting of lowercase Latin letters from 'a&#​39; to 'k&#​39;.

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

Output

For each test case, print a single integer — the number of pairs (i,j) (i<j) such that the i-th string and the j-th string have exactly one position p (1≤p≤2) such that sip≠sjp.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

Example

inputCopy

4

6

ab

cb

db

aa

cc

ef

7

aa

bb

cc

ac

ca

bb

aa

4

kk

kk

ab

ab

5

jf

jf

jk

jk

jk

outputCopy

5

6

0

6

Note

For the first test case the pairs that differ in exactly one position are: ("ab&#​34;, "cb&#​34;), ("ab&#​34;, "db&#​34;), ("ab&#​34;, "aa&#​34;), ("cb&#​34;, "db&#​34;) and ("cb&#​34;, "cc&#​34;).

For the second test case the pairs that differ in exactly one position are: ("aa&#​34;, "ac&#​34;), ("aa&#​34;, "ca&#​34;), ("cc&#​34;, "ac&#​34;), ("cc&#​34;, "ca&#​34;), ("ac&#​34;, "aa&#​34;) and ("ca&#​34;, "aa&#​34;).

For the third test case, the are no pairs satisfying the conditions.

/*
对于此题直接将所有字符串存入vis记录每种排列方式个数
然后对于s的每钟字符进行的贡献计算即可
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int n;
string s[100005];
int vis[20][20];
void solve()
{
	cin>>n;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        cin>>s[i];
        vis[s[i][0]-'a'][s[i][1]-'a']++;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int t1=s[i][0]-'a';
        int t2=s[i][1]-'a';
        for(int j=0;j<=15;j++){
            if(t1!=j)ans+=vis[j][t2];
            if(t2!=j)ans+=vis[t1][j];
        }
    }
    cout<<ans/2<<endl;
}
signed main()
{
	int __;
	cin>>__;
	//__=1;
	while(__--)solve();
}

F. Eating Candies

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

There are n candies put from left to right on a table. The candies are numbered from left to right. The i-th candy has weight wi. Alice and Bob eat candies.

Alice can eat any number of candies from the left (she can't skip candies, she eats them in a row).

Bob can eat any number of candies from the right (he can't skip candies, he eats them in a row).

Of course, if Alice ate a candy, Bob can't eat it (and vice versa).

They want to be fair. Their goal is to eat the same total weight of candies. What is the most number of candies they can eat in total?

Input

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

The first line of each test case contains an integer n (1≤n≤2⋅105) — the number of candies on the table.

The second line of each test case contains n integers w1,w2,…,wn (1≤wi≤104) — the weights of candies from left to right.

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

Output

For each test case, print a single integer — the maximum number of candies Alice and Bob can eat in total while satisfying the condition.

Example

inputCopy

4

3

10 20 10

6

2 1 4 2 4 1

5

1 2 4 8 16

9

7 3 20 5 15 1 11 8 10

outputCopy

2

6

0

7

Note

For the first test case, Alice will eat one candy from the left and Bob will eat one candy from the right. There is no better way for them to eat the same total amount of weight. The answer is 2 because they eat two candies in total.

For the second test case, Alice will eat the first three candies from the left (with total weight 7) and Bob will eat the first three candies from the right (with total weight 7). They cannot eat more candies since all the candies have been eaten, so the answer is 6 (because they eat six candies in total).

For the third test case, there is no way Alice and Bob will eat the same non-zero weight so the answer is 0.

For the fourth test case, Alice will eat candies with weights [7,3,20] and Bob will eat candies with weights [10,8,11,1], they each eat 30 weight. There is no better partition so the answer is 7.

/*
有一种方法是使用前缀和后缀和然后对每一个前缀和用二分后缀和方法
计算对于每一个前缀和与它相等的位置，记录最大值，但是复杂度O(nlogn)

我用的是直接贪心从两边尝试吃糖果，谁数量少谁去继续吃，记录其中相等的时候的值
时间复杂度O(n)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int n;
int a[200005];
void solve()
{
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0,l=1,r=n,ma=0,sul=a[1],sur=a[n],al=1,ar=1;
    if(n==1){
        cout<<0<<endl;
        return;
    }
    while(1){
        if(sul==sur){
            ma=al+ar;
            sul+=a[++l];
            al++;
        }
        if(r-l<=1){
            cout<<ma<<endl;
            break;
        }
        if(sul>sur){
            sur+=a[--r];
            ar++;
        }
        else sul+=a[++l],al++;
    }
}
signed main()
{
	int __;
	cin>>__;
	//__=1;
	while(__--)solve();
}

G. Fall Down

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

There is a grid with n rows and m columns, and three types of cells:

An empty cell, denoted with '.&#​39;.

A stone, denoted with '*&#​39;.

An obstacle, denoted with the lowercase Latin letter 'o&#​39;.

All stones fall down until they meet the floor (the bottom row), an obstacle, or other stone which is already immovable. (In other words, all the stones just fall down as long as they can fall.)

Simulate the process. What does the resulting grid look like?

Input

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

The first line of each test case contains two integers n and m (1≤n,m≤50) — the number of rows and the number of columns in the grid, respectively.

Then n lines follow, each containing m characters. Each of these characters is either '.&#​39;, '*&#​39;, or 'o&#​39; — an empty cell, a stone, or an obstacle, respectively.

Output

For each test case, output a grid with n rows and m columns, showing the result of the process.

You don't need to output a new line after each test, it is in the samples just for clarity.

Example

inputCopy

3

6 10

.*.*....*.

.*.......*

...o....o.

.*.*....*.

..........

.o......o*

2 9

...***ooo

.*o.*o.*o

5 5

*****

*....

*****

....*

*****

outputCopy

..........

...*....*.

.*.o....o.

.*........

.*......**

.o.*....o*

....**ooo

.*o**o.*o

.....

*...*

*****

*****

*****

/*
暴力= =，每次遇见o的时候往上统计*个数，并置为.，直到遇见边界或者再遇见o
然后再从原来o的位置上往上置o，注意最后一行边界也要统计
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int n,m;
char mp[52][52];
void solve()
{
	cin>>n>>m;
    for(int i=1;i<=n;i++){
        getchar();
        for(int j=1;j<=m;j++){
            mp[i][j]=getchar();
        }
    }
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='o'||i==n+1){
                int tsum=0;
                for(int k=i-1;k>=1&&mp[k][j]!='o';k--){
                    if(mp[k][j]=='*'){
                        mp[k][j]='.';
                        tsum++;
                    }
                }
                for(int k=i-1;k>=1&&tsum!=0;k--){
                    mp[k][j]='*';
                    tsum--;
                }
            }
        }
    }




    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<mp[i][j];
        }
        cout<<endl;
    }
}
signed main()
{
	int __;
	cin>>__;
	//__=1;
	while(__--)solve();
}

H. Maximal AND

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

Let AND denote the bitwise AND operation, and OR denote the bitwise OR operation.

You are given an array a of length n and a non-negative integer k. You can perform at most k operations on the array of the following type:

Select an index i (1≤i≤n) and replace ai with ai OR 2j where j is any integer between 0 and 30 inclusive. In other words, in an operation you can choose an index i (1≤i≤n) and set the j-th bit of ai to 1 (0≤j≤30).

Output the maximum possible value of a1 AND a2 AND … AND an after performing at most k operations.

Input

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

The first line of each test case contains the integers n and k (1≤n≤2⋅105, 0≤k≤109).

Then a single line follows, containing n integers describing the arrays a (0≤ai<231).

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 line containing the maximum possible AND value of a1 AND a2 AND … AND an after performing at most k operations.

Example

inputCopy

4

3 2

2 1 1

7 0

4 6 6 28 6 6 12

1 30

0

4 4

3 1 3 1

outputCopy

2

4

2147483646

1073741825

Note

For the first test case, we can set the bit 1 (21) of the last 2 elements using the 2 operations, thus obtaining the array [2, 3, 3], which has AND value equal to 2.

For the second test case, we can't perform any operations so the answer is just the AND of the whole array which is 4.

/*
贪心，如果能对某一位全部置位的话应当先给高位置1
然后依次向后推，最后重新计算这种方法的值即可
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int vis[40],vis1[40];
int n,k;
int a[200005];
void solve()
{
	memset(vis,0,sizeof(vis));
    memset(vis1,0,sizeof(vis1));
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        for(int i=1;x!=0;i++){
            if(x&1)vis[i]++;
            x>>=1;
        }
    }
    for(int i=31;i>=1;i--){
        if(vis[i]==n){
            vis1[i]=1;
            continue;
        }
        if(vis[i]+k>=n){
            vis1[i]=1;
            k-=(n-vis[i]);
        }
    }
    int ans=0;
    for(int i=31;i>=1;i--){
        ans<<=1;
        if(vis1[i])ans|=1;
    }
    cout<<ans<<endl;
}
signed main()
{
	int __;
	cin>>__;
	//__=1;
	while(__--)solve();
}