【Codeforces】Codeforces Round 664 (Div. 2)

A. Boboniu Likes to Color Balls

Boboniu gives you

r red balls,
g green balls,
b blue balls,
w white balls.

He allows you to do the following operation as many times as you want:

Pick a red ball, a green ball, and a blue ball and then change their color to white.
You should answer if it’s possible to arrange all the balls into a palindrome after several (possibly zero) number of described operations.

Input
The first line contains one integer T (1≤T≤100) denoting the number of test cases.

For each of the next T cases, the first line contains four integers r, g, b and w (0≤r,g,b,w≤10^9).

Output
For each test case, print “Yes” if it’s possible to arrange all the balls into a palindrome after doing several (possibly zero) number of described operations. Otherwise, print “No”.

Example
input

4
0 1 1 1
8 1 9 3
0 0 0 0
1000000000 1000000000 1000000000 1000000000

output

No
Yes
Yes
Yes

Note
In the first test case, you’re not able to do any operation and you can never arrange three balls of distinct colors into a palindrome.

In the second test case, after doing one operation, changing (8,1,9,3) to (7,0,8,6), one of those possible palindromes may be “rrrwwwbbbbrbbbbwwwrrr”.

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. For example, “rggbwbggr”, “b”, “gg” are palindromes while “rgbb”, “gbbgr” are not. Notice that an empty word, phrase, or sequence is palindrome.

题意: 给你四种球 ,每种球 r ,g ,b ,w 个 ,并且允许将 1 个 r ,1 个 g ,1 个 b ,替换为 3 个 w ,问能否将这些球排成一列 ,使其形成回文串 .

解: 注意到当 r ,g ,b ,w 的个数全是偶数时 ,可以构成回文 ,当有三个为偶数一个为奇数时显然也可以 .题给予的操作可以把 r ,g ,b ,w 的个数在奇偶间替换 .当有两个偶两个奇时 ,操作一遍后依旧是两偶两奇 ,则不行 .当一偶三奇时 ,操作一遍变为三偶一奇,则可行 .只需特判不能操作时是否可行即可 ,如案例中 0 1 1 1 一偶三奇无法进行操作则不行 .

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 309
#define mss 17
#define mod 1000000007
using namespace std;
// Notice the data size
// Notice the input and output 

LL n,m,k,te;
LL p[MS],tot; 

int main() {
	//ios::sync_with_stdio(false);
	cin >> te;
	while(te--){
		LL r,g,b,w,ou = 0,ji = 0;
		cin >> r >> g >> b >> w;
		LL t = min(r,min(g,b));
		if(r&1) ji++;
		else ou++;
		if(g&1) ji++;
		else ou++;
		if(b&1) ji++;
		else ou++;
		if(w&1) ji++;
		else ou++;
		if(ji<=1){
			printf("YES\n");
		}
		else{
			if(t == 0 || ji == 2) printf("NO\n");
			else if(ji>=3) printf("YES\n");
		}
	}
	
	
	return 0; 
}
 

B. Boboniu Plays Chess

Boboniu likes playing chess with his employees. As we know, no employee can beat the boss in the chess game, so Boboniu has never lost in any round.

You are a new applicant for his company. Boboniu will test you with the following chess question:

Consider a n×m grid (rows are numbered from 1 to n, and columns are numbered from 1 to m). You have a chess piece, and it stands at some cell (Sx,Sy) which is not on the border (i.e. 2≤Sx≤n−1 and 2≤Sy≤m−1).

From the cell (x,y), you can move your chess piece to (x,y′) (1≤y′≤m,y′≠y) or (x′,y) (1≤x′≤n,x′≠x). In other words, the chess piece moves as a rook. From the cell, you can move to any cell on the same row or column.

Your goal is to visit each cell exactly once. Can you find a solution?

Note that cells on the path between two adjacent cells in your route are not counted as visited, and it is not required to return to the starting point.

Input
The only line of the input contains four integers n, m, Sx and Sy (3≤n,m≤100, 2≤Sx≤n−1, 2≤Sy≤m−1) — the number of rows, the number of columns, and the initial position of your chess piece, respectively.

Output
You should print n⋅m lines.

The i-th line should contain two integers xi and yi (1≤xi≤n, 1≤yi≤m), denoting the i-th cell that you visited. You should print exactly nm pairs (xi,yi), they should cover all possible pairs (xi,yi), such that 1≤xi≤n, 1≤yi≤m.

We can show that under these constraints there always exists a solution. If there are multiple answers, print any.

Examples

input

3 3 2 2

output

2 2
1 2
1 3
2 3
3 3
3 2
3 1
2 1
1 1

input

3 4 2 2

output

2 2
2 1
2 3
2 4
1 4
3 4
3 3
3 2
3 1
1 1
1 2
1 3

Note
Possible routes for two examples:

题意: 有 n*m 的一个棋盘 ,你扮演象棋棋子的 “车” ,拥有 “车” 的行走规则 ,给定初始位置 ,求只允许访问每个点一次 ,输出访问的先后顺序 .(象棋种有起子落子 ,“车” 的落子的位置称为 “访问” ,经过的路径上不算 “访问” ) .

解: 设初始位置在行 x 列 y 处 ,则先把第 x 行先左后右访问一遍 ,最后抵达 x 行 m 列处 .从该点先向下 “蛇形” 访问 ,形如字母 “S” ,直到最后 n 行 ,再回到 x-1 行向上 “蛇形” 访问即可 .

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 309
#define mss 17
#define mod 1000000007
using namespace std;
// Notice the data size
// Notice the input and output 

LL n,m,k,te;
LL p[MS],tot; 

int main() {
	//ios::sync_with_stdio(false);
	int x,y;
	cin >> n >> m >> x >> y;
	for(int i=y;i>=1;i--){
		printf("%d %d\n",x,i);
	}
	for(int i=y+1;i<=m;i++){
		printf("%d %d\n",x,i);
	}
	int flag = 1;
	for(int i=x+1;i<=n;i++){
		if((i-x)%2==1){
			for(int j=m;j>=1;j--){
				printf("%d %d\n",i,j);
			}
			flag = -1;
		}
		else{
			for(int j=1;j<=m;j++){
				printf("%d %d\n",i,j);
			}
			flag = 1;
		}
	}
	for(int i=x-1;i>=1;i--){
		if(flag == 1){
			for(int j=m;j>=1;j--){
				printf("%d %d\n",i,j);
			}
			flag = -1;
		}
		else{
			for(int j=1;j<=m;j++){
				printf("%d %d\n",i,j);
			}
			flag = 1;
		}
	}
	
	
	return 0; 
}

C. Boboniu and Bit Operations

Boboniu likes bit operations. He wants to play a game with you.

Boboniu gives you two sequences of non-negative integers a1,a2,…,an and b1,b2,…,bm.

For each i (1≤i≤n), you’re asked to choose a j (1≤j≤m) and let ci=ai&bj, where & denotes the bitwise AND operation. Note that you can pick the same j for different i’s.

Find the minimum possible c1|c2|…|cn, where | denotes the bitwise OR operation.

Input
The first line contains two integers n and m (1≤n,m≤200).

The next line contains n integers a1,a2,…,an (0≤ai<2^9).

The next line contains m integers b1,b2,…,bm (0≤bi<2^9).

Output
Print one integer: the minimum possible c1|c2|…|cn.

Examples

input

4 2
2 6 4 0
2 4

output

2

input

7 6
1 9 1 9 8 1 0
1 1 4 5 1 4

output

0

input

8 5
179 261 432 162 82 43 10 38
379 357 202 184 197

output

147

Note
For the first example, we have c1=a1&b2=0, c2=a2&b1=2, c3=a3&b1=0, c4=a4&b1=0.Thus c1|c2|c3|c4=2, and this is the minimal answer we can get.

题意: 给定两个长度分别为 n ,m 的数组 a ,b ,对于每一个 ai (1≤i≤n) ,都要选择一个 bj (1≤j≤m) ,使得 ci = ai & bi ,求 c1 | c2 | ··· | cn 的最小值.

解: 注意到数据小于 2^9 ,则最后答案不超过 2^9 ,对于每一个 ai 都有 m 种选择方案 ,从小到大枚举答案ans ,若 a1 分别与 m 个 b数组中的元素匹配后的结果中有 ans 的子集 (将 “010” 作为 “110” 的子集) ,则继续询问 a2 … 若未找到子集 ,则询问 ans+1 …

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 309
#define mss 17
#define mod 1000000007
using namespace std;
// Notice the data size
// Notice the input and output 

int n,m,k,te;
int a[MS],b[MS],tot; 

int find(int x,int y){ // x是否是y的子集
	for(int i=0;i<10;i++){
		if( ((x>>i)&1) && !((y>>i)&1) ){
			return 0;
		}
	}
	return 1;
}

int main() {
	//ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=m;i++) cin >> b[i];
	int ans,flag,fl;
	for(ans = 0;ans < 512;ans++){
		flag = 0; // 标记当前ans是否可行
		for(int i=1;i<=n;i++){
			fl = 0; // 标记 ai 是否可行
			for(int j=1;j<=m;j++){
				int cc = a[i] & b[j];
				if(find(cc,ans)){
					fl = 1;
					break;
				}
			}
			if(!fl) break; // 未找到枚举 ans+1
			if(i == n){ // 全部枚举完 ai ,当前ans可行
				flag = 1;
				break;
			}
		}
		if(flag) break;
	}
	printf("%d\n",ans);
	
	return 0; 
}

D. Boboniu Chats with Du

Have you ever used the chat application QQ? Well, in a chat group of QQ, administrators can muzzle a user for days.

In Boboniu’s chat group, there’s a person called Du Yi who likes to make fun of Boboniu every day.

Du will chat in the group for n days. On the i-th day:

If Du can speak, he’ll make fun of Boboniu with fun factor ai. But after that, he may be muzzled depending on Boboniu’s mood.
Otherwise, Du won’t do anything.
Boboniu’s mood is a constant m. On the i-th day:

If Du can speak and ai>m, then Boboniu will be angry and muzzle him for d days, which means that Du won’t be able to speak on the i+1,i+2,⋯,min(i+d,n)-th days.
Otherwise, Boboniu won’t do anything.
The total fun factor is the sum of the fun factors on the days when Du can speak.

Du asked you to find the maximum total fun factor among all possible permutations of a.

Input
The first line contains three integers n, d and m (1≤d≤n≤105,0≤m≤109).

The next line contains n integers a1,a2,…,an (0≤ai≤109).

Output
Print one integer: the maximum total fun factor among all permutations of a.

Examples

input

5 2 11
8 10 15 23 5

output

48

input

20 2 16
20 5 8 2 18 16 2 16 16 1 5 16 2 13 6 16 4 17 21 7

output

195

Note
In the first example, you can set a′=[15,5,8,10,23]. Then Du’s chatting record will be:

Make fun of Boboniu with fun factor 15.
Be muzzled.
Be muzzled.
Make fun of Boboniu with fun factor 10.
Make fun of Boboniu with fun factor 23.
Thus the total fun factor is 48.

题意: 在QQ聊天群中 ,管理员可以连续几天禁言一名用户 .Du 喜欢在QQ群中与 Boboniu 开玩笑 .Du 将在QQ群中聊天 n 天 .在第 i 天 ,如果 Du 能说话 ,他将会得到值为 ai 的快乐值 ,但他也许会被禁言这取决于 Boboniu 的心情 ,否则什么也不会做 .如果 Du 能说话并且 ai > m ,这样Boboniu 就会生气并禁言 Du 随后的d天 ,这意味着 Du 在 i+1 ,i+2 , … ,min(i+d,n) 不能说话 .在 a 的所有可能排列中 ,找到 Du 一共能获得最多的快乐值总和 .

解: 把大于 m 和 小于等于 m 的区分来放 ,一个大于 m 的可以带走 d 天 .设大于 m 的天数为 x ,小于的为 y ,在大于 m 中选择 t 天 (当然选择最大的几个) ,其中一天可以放在序列末尾 ,所以一共消耗 cost = (t-1)*(d+1)+1 天 ,剩下的 n-cost 天则在小于 m 的序列中选择 ,枚举 t 即可 .

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
#define mod 1000000007
using namespace std;
// Notice the data size
// Notice the input and output 

LL n,m,k,te,ans;
LL p[MS],high[MS],low[MS]; 

bool cmp(LL a,LL b){
	return a > b;
}

int main() {
	//ios::sync_with_stdio(false);
	LL cnt1 = 0 ,cnt2 = 0;
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&p[i]);
		if(p[i]>k) high[++cnt1] = p[i];
		else low[++cnt2] = p[i];
	} 
	sort(high+1,high+cnt1+1,cmp);
	sort(low+1,low+cnt2+1,cmp);
	
	for(int i=2;i<=cnt2;i++) low[i] += low[i-1];
	
	LL ans = low[cnt2], pos, res = 0;
	for(int i=1;i<=cnt1;i++){
		res += high[i];
		pos = (i-1)*(m+1)+1;
		if(pos > n) break;
		pos = n - pos;
		pos = min(pos,cnt2);
		ans = max(ans,res+low[pos]);
	}
	printf("%lld\n",ans);
	
	
	
	return 0; 
}