Codeforces Round #691 (Div. 2)

A. Red-Blue Shuffle

題目
There are n cards numbered 1,…,n. The card i has a red digit ri and a blue digit bi written on it.

We arrange all n cards in random order from left to right, with all permutations of 1,…,n having the same probability. We then read all red digits on the cards from left to right, and obtain an integer R. In the same way, we read all blue digits and obtain an integer B. When reading a number, leading zeros can be ignored. If all digits in a number are zeros, then the number is equal to 0. Below is an illustration of a possible rearrangement of three cards, and how R and B can be found.

Two players, Red and Blue, are involved in a bet. Red bets that after the shuffle R>B, and Blue bets that R<B. If in the end R=B, the bet results in a draw, and neither player wins.

Determine, which of the two players is more likely (has higher probability) to win the bet, or that their chances are equal. Refer to the Note section for a formal discussion of comparing probabilities.

Input
The first line contains a single integer T (1≤T≤100) — the number of test cases.

Descriptions of T test cases follow. Each test case description starts with a line containing a single integer n (1≤n≤1000) — the number of cards.

The following line contains a string of n digits r1,…,rn — red digits on cards 1,…,n respectively.

The following line contains a string of n digits b1,…,bn — blue digits on cards 1,…,n respectively.

Note that digits in the same line are not separated with any delimiters.

Output
Print T answers for the test cases in order, one per line.

If Red has a strictly higher change to win, print “RED”.

If Blue has a strictly higher change to win, print “BLUE”.

If both players are equally likely to win, print “EQUAL”.

Note that all answers are case-sensitive.

Example
inputCopy
3
3
777
111
3
314
159
5
09281
09281
outputCopy
RED
BLUE
EQUAL
Note
Formally, let nR be the number of permutations of cards 1,…,n such that the resulting numbers R and B satisfy R>B. Similarly, let nB be the number of permutations such that R<B. If nR>nB, you should print “RED”. If nR<nB, you should print “BLUE”. If nR=nB, print “EQUAL”.

In the first sample case, R=777 and B=111 regardless of the card order, thus Red always wins.

In the second sample case, there are two card orders when Red wins, and four card orders when Blue wins:

order 1,2,3: 314>159;
order 1,3,2: 341>195;
order 2,1,3: 134<519;
order 2,3,1: 143<591;
order 3,1,2: 431<915;
order 3,2,1: 413<951.
Since R<B is more frequent, the answer is “BLUE”.

In the third sample case, R=B regardless of the card order, thus the bet is always a draw, and both Red and Blue have zero chance to win.

題意
有n張牌，每張上面有兩個數字，排列這些牌之后比較上面n個數字的大小放在一起和下面n個數字放在一起的大小，如果上面大的數量多，RED獲勝，如果相同則EQUAL 否則BLUE獲勝

思路
直接比較上面和下面的差值誰大即可， 剛開始想錯了，統計了所有排列，

代碼

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		string s,t;
		cin>>s>>t;
		if(s==t)
		{
			cout<<"EQUAL\n";
			continue;
		}
		int len = s.size();
		long long ans1 = 0 , ans2 = 0;
		for(int i=0;i<len;i++)
		{
			if(s[i]>t[i])
			ans1++;
			else if(t[i]>s[i])
			ans2++;
		}
		if(ans1 > ans2)
		cout<<"RED\n";
		else if(ans1 == ans2)
		cout<<"EQUAL\n";
		else
		cout<<"BLUE\n";
	}
} 

B. Move and Turn

題目
A robot is standing at the origin of the infinite two-dimensional plane. Each second the robot moves exactly 1 meter in one of the four cardinal directions: north, south, west, and east. For the first step the robot can choose any of the four directions, but then at the end of every second it has to turn 90 degrees left or right with respect to the direction it just moved in. For example, if the robot has just moved north or south, the next step it takes has to be either west or east, and vice versa.

The robot makes exactly n steps from its starting position according to the rules above. How many different points can the robot arrive to at the end? The final orientation of the robot can be ignored.

Input
The only line contains a single integer n (1≤n≤1000) — the number of steps the robot makes.

Output
Print a single integer — the number of different possible locations after exactly n steps.

Examples
inputCopy
1
outputCopy
4
inputCopy
2
outputCopy
4
inputCopy
3
outputCopy
12
Note
In the first sample case, the robot will end up 1 meter north, south, west, or east depending on its initial direction.

In the second sample case, the robot will always end up 2–√ meters north-west, north-east, south-west, or south-east.

題意
在笛卡爾直角坐標系上走n步，第一步可以往四個方面走，其他每一步都只能往左往右拐，問n步后能到達的點有多少個，

思路
暴力畫圖推規律，

可以推出
1 4
2 4
3 12
4 9
5 24
6 16
7 40
8 25
9 60
10 36

容易發現
偶數的時候是 3 2 3^2 32 開始的，每下一項 ( n + 1 ) 2 (n+1)^2 (n+1)2 的一個數列
奇數的時候是從4開始的每次之間的差遞增4的數列

代碼

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

long long qpow(ll a,ll b)
{
	ll base = a,ans = 1;
	while(b)
	{
		if(b&1)
		ans *= base;
		base *= base;
		b >>= 1;
	}
	return ans;
}
int main()
{
	int n;
	cin>>n;
	if(n==1)
	cout<<4<<"\n";
	else if(n==2)
	cout<<4<<"\n";
	else
	{
		if(n&1)
		{
			ll now = 8;
			ll ans = 4;
			for(int i=3;i<=n;i+=2)
			{
				ans += now;
				now += 4;
			}
			cout<<ans<<"\n";
		}
		else
		{
			ll ans = 2;
			for(int i=4;i<=n;i+=2)
			ans ++;
			cout<<qpow(ans,2)<<"\n";
		}
	}
}

C. Row GCD

題目
You are given two positive integer sequences a 1 , … , a n a1,…,an a1,…,an and b 1 , … , b m b1,…,bm b1,…,bm. For each j=1,…,m find the greatest common divisor of a 1 + b j , … , a n + b j a1+bj,…,an+bj a1+bj,…,an+bj.

Input
The first line contains two integers n and m (1≤n,m≤2? 1 0 5 10^5 105).

The second line contains n integers a1,…,an (1≤ai≤10^18).

The third line contains m integers b1,…,bm (1≤bj≤1018).

Output
Print m integers. The j-th of them should be equal to GCD(a1+bj,…,an+bj).

Example
inputCopy
4 4
1 25 121 169
1 2 7 23
outputCopy
2 3 8 24

題意
給一個長度為n的陣列a和長度為m的陣列b 每次吧a陣列每個數都加上b[j] 后求當前a的gcd

思路
首先我們需要知道一個gcd的基本性質 ： g c d ( a , b ) = g c d ( a ? b , b ) gcd(a,b)=gcd(a-b,b) gcd(a,b)=gcd(a?b,b)
知道了這個之后我們把 ( a 1 + b j , … , a n + b j ) (a1+bj,…,an+bj) (a1+bj,…,an+bj)每一項從第二項開始后一項減去前一項，a的GCD不變，現在就只有 a 1 + b j a1+bj a1+bj這一項沒有被減去過任何數，于是我們先求差分陣列的GCD，再每一項與 a 1 + b j a1+bj a1+bj求GCD就是最后的答案

代碼

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int maxn = 200000+100;
 
ll a[maxn] , b[maxn] , tool[maxn];
 
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
//	cout<<__gcd(30000000000000,6000000000000)<<"\n";
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=n-1;i++)
	tool[i] = a[i+1] - a[i];
	ll g = tool[1];
	for(int i=2;i<=n-1;i++)
	{
		g = __gcd(g,tool[i]);
	}
//	cout<<g<<"\n";
	for(int i=1;i<=m;i++)
	{
		cout<<__gcd(g,b[i] + a[1])<<" ";
	}
}