A. Exciting Bets

1, Title Link

https://codeforces.ml/contest/1543/problem/A

2, General idea of the topic

There are t groups of data, and each group of data contains a pair of a and B. You can perform any number of operations. Each operation can add or subtract a and B at the same time. Let the last two numbers be x and y, and the title wants to output two values, one of which is the largest g c d ( x , y ) gcd(x,y) gcd(x,y), one is to get the maximum g c d ( x , y ) gcd(x,y) gcd(x,y) the minimum number of operations required.

Data range: 1 ≤ t ≤ 5 ∗ 1 0 3 1≤t≤5*10^3 1≤t≤5∗103， 0 ≤ a , b ≤ 1 0 18 0≤a,b≤10^{18} 0≤a,b≤1018.

3, Topic analysis

• First, let's assume a < b a<b A < B, because the minimum number of operations is to be obtained, it is obvious that the operation times of always adding one and always subtracting one are the minimum. Set the minimum number of operations to x.
• According to Euclid's law, g c d ( a + x , b + x ) gcd(a+x,b+x) The value of gcd(a+x,b+x) and g c d ( b + x , b − a ) gcd(b+x,b-a) The results of gcd(b+x,b − a) are the same, so it is obvious that the first value required for the answer must be b-a.
• Then consider how to minimize the number of operations. Obviously, there are two answers here. One is that x is negative so that b + x b+x b+x is b − a b-a One is that x is positive so that b + x b+x b+x is b − a b-a Multiple of b − a. The solutions of the two schemes are obtained respectively ∣ x ∣ \left|x\right| ∣ x ∣ and then select the minimum output.
• Finally, pay attention a = b a=b If a=b and a or b have 0, it is sufficient.

4, Positive solution program

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>

using namespace std;
typedef long long ll;
ll T;
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		ll a,b;
		scanf("%lld%lld",&a,&b);
		if(a>b)//First, ensure that a < B
			swap(a,b);
		if(a==b)//Handling special situations
			printf("0 0\n");
		else
		{
			ll t1=b-a,t2=0,t3=0;
			if(b%t1==0)
				t2=0;
			else//Calculate the number of operations when x is positive and negative respectively
			{
				t2=(b/t1+1)*t1-b;
				t3=b-b/t1*t1;
			}
			printf("%lld %lld\n",t1,min(t2,t3));
		}
	}
	
	return 0;
}

B. Customising the Track

1, Title Link

https://codeforces.ml/contest/1543/problem/B

2, General idea of the topic

There are t groups of data, and each group of data contains a sequence a with length n. You can perform any operation on the value in sequence a, but you can't make it less than or equal to 0, and the sum remains unchanged. It is required to make the last ∑ i = 1 n ∑ j = i + 1 n ∣ a [ i ] − a [ j ] ∣ \sum_{i=1}^{n}\sum_{j=i+1}^{n}\left|a[i]-a[j]\right| The value of Σ i=1n Σ j=i+1n ∣ a[i] − a[j] ∣ shall be as small as possible. Output the last minimum value.

Data range: 1 ≤ t ≤ 1 0 4 1≤t≤10^4 1≤t≤104， 1 ≤ n ≤ 2 ∗ 1 0 5 1≤n≤2*10^5 1≤n≤2∗105， 0 ≤ a [ i ] ≤ 1 0 9 0≤a[i]≤10^{9} 0≤a[i]≤109.

3, Topic analysis

• An obvious conclusion is that if sequence a can be divided into n blocks, the answer must be the minimum value of 0.
• So we can ⌊ s u m / n ⌋ \lfloor sum/n\rfloor ⌊ sum/n ⌋ as the minimum size of each block, assuming that the remainder is res, divide the remaining res equally to res blocks, so that the answer must be the minimum. The answer at this time can be easily obtained by simply combining numbers as follows: r e s ∗ ( n − r e s ) res*(n-res) res∗(n−res).

4, Positive solution program

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long ll;
const ll maxn=200010;
ll T,n;
ll a[maxn];
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		ll sum=0;
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			sum+=a[i];
		}
		ll temp=sum%n;
		printf("%lld\n",temp*(n-temp));
	}
	
	return 0;
}

C. Need for Pink Slips

1, Title Link

https://codeforces.ml/contest/1543/problem/C

2, General idea of the topic

share t t t sets of data with three letters in each set C ， M ， P C，M，P C. M, P, at the beginning, the probability of each letter being selected is three floating-point numbers: c ， m ， p c，m，p c. m, p, satisfied c + m + p = 1 c+m+p=1 c+m+p=1. There is also a floating index v v v.

One letter will be randomly selected according to the probability. The rules are as follows:

• If you draw letters P P P. Game over
• Otherwise, according to the probability corresponding to the extracted letter a a a. And floating index v v v-entry comparison
  • If a ≤ v a≤v a ≤ v, then the probability of this letter to be drawn next becomes 0 and becomes an unavailable letter, and its probability will be evenly distributed to the remaining available letters.
  • If a > v a>v a> V, then the probability of drawing this letter next will be reduced v v v. The subtracted probability will be evenly distributed to the remaining available letters.

Finally, ask what is the expected value of the number of letters in the random extraction game.

Data range: 1 ≤ t ≤ 10 1≤t≤10 1≤t≤10， 0 < c , m , p < 1 0<c,m,p<1 0<c,m,p<1， 0.1 ≤ v ≤ 0.9 0.1≤v≤0.9 0.1 ≤ v ≤ 0.9, the error range of the answer shall not exceed 1 0 6 10^6 106.

3, Topic analysis

• In fact, this problem is not complex. You only need to read the problem, set the accuracy, and then conduct violent recursive search.
• When in a state c ， m ， p c，m，p c. m, p, assume this selection respectively C ， M C，M C. In the case of M, set the recursive state of the next layer according to the meaning of the question, and then calculate the answers respectively.

4, Positive solution program

#include<iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
const double eps=1e-8;
double solve(double c,double m,double p,double v)
{
	double ans=p;
	if(c>eps)//Pay attention to accuracy
	{
		if(c>eps+v)
		{
			if(m>eps)
				ans+=c*(1+solve(c-v,m+v/2,p+v/2,v));
			else
				ans+=c*(1+solve(c-v,0,p+v,v));
		}
		else
		{
			if(m>eps)
				ans+=c*(1+solve(0,m+c/2,p+c/2,v));
			else
				ans+=c*(1+solve(0,0,p+c,v));
		}
	}
	if(m>eps)
	{
		if(m>eps+v)
		{
			if(c>eps)
				ans+=m*(1+solve(c+v/2,m-v,p+v/2,v));
			else
				ans+=m*(1+solve(0,m-v,p+v,v));
		}
		else
		{
			if(c>eps)
				ans+=m*(1+solve(c+m/2,0,p+m/2,v));
			else
				ans+=m*(1+solve(0,0,p+m,v));
		}
	}
	return ans;
}
int main()
{
	ll T;
	scanf("%lld",&T);
	while(T--)
	{
		double c,m,p,v;
		scanf("%lf%lf%lf%lf",&c,&m,&p,&v);
		printf("%.10lf\n",solve(c,m,p,v));
	}
	
	return 0;
}

D1. RPD and Rap Sheet (Easy Version)

1, Title Link

https://codeforces.ml/contest/1543/problem/D1

2, General idea of the topic

This question is called interactive question, which has t t t sets of data, each containing one n ， k n，k n. k (easy version) k = 2 k=2 k=2), the system will input an initial password every time, and the initial password is a [ 0 ， n − 1 ] [0，n-1] For the random value of [0, n − 1], you can output up to n queries to guess the password. If you guess the password correctly, the system will enter 1, otherwise enter 0.

But the password is not constant. It will change according to the following formula after guessing the password each time: used dense code ⨁ new dense code = Inquire ask value Old password ⨁ new password = query value Old password ⨁ new password = query value.

⨁ ⨁ ⨁ operation is defined as if there are two numbers A ， B A，B A. B, corresponding k k The value of the corresponding bit in k-ary is a ， b a，b a. b, the result of the corresponding bit is c = ( a + b )   m o d   k c=(a+b)~mod~k c=(a+b) mod k.

Data range: 1 ≤ t ≤ 1 0 4 1≤t≤10^4 1≤t≤104， 1 ≤ n ≤ 2 ∗ 1 0 5 1≤n≤2*10^5 1≤n≤2∗105， 2 ≤ k ≤ 100 2≤k≤100 2≤k≤100.

3, Topic analysis

• because k = 2 k=2 When k=2, this operation is equivalent to binary XOR operation, then a ⨁ b = c a⨁b=c When a ⨁ b=c a ⨁ c = b a⨁c=b a⨁c=b.
• Therefore, the formula in the title can be rewritten as: used dense code ⨁ Inquire ask value = new dense code Old password ⨁ query value = new password Old password ⨁ query value = new password
• Considering multiple queries, assume that the initial password is x x x. The passwords guessed each time are: a 1 ， a 2 ， . . . ， a n a_{1}，a_{2}，...，a_{n} a1​，a2​，...， an​. Then it will meet: x ⨁ a 1 ⨁ a 2 ⨁ . . . ⨁ a n = new dense code x⨁a_{1}⨁a_{2}⨁... ⨁a_{n} = new password x⨁a1​⨁a2​⨁... ⨁ an = new password. and s u m = a 1 ⨁ a 2 ⨁ . . . ⨁ a n sum=a_{1}⨁a_{2}⨁...⨁a_{n} sum=a1​⨁a2​⨁... The value of⨁ an ⨁ can be easily calculated during the process of the program.
• So we can guess the initial password x x x. The initial password is a [ 0 ， n − 1 ] [0，n-1] Random value of [0, n − 1], guess at most n n You can get the answer n times.

4, Positive solution program

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long ll;
ll T,n,k;
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&n,&k);
		ll sum=0,t=0;
		for(ll i=0;i<=n-1;i++)//Set the initial password to i
		{
			ll temp=(i^sum);//Calculate x ^ A1 ^ A2 ^^ an
			printf("%lld\n",temp);fflush(stdout);
			scanf("%lld",&t);
			if(t)
				break;
			sum^=temp;//Calculate A1 ^ A2 ^^ an
		}
	}
	
	return 0;
}

D2. RPD and Rap Sheet (Hard Version)

1, Title Link

https://codeforces.ml/contest/1543/problem/D2

2, General idea of the topic

Same as D1.

3, Topic analysis

• ⨁ ⨁ ⨁ operation is defined as if there are two numbers A ， B A，B A. B, corresponding k k The value of the corresponding bit in k-ary is a ， b a，b a. b, the result of the corresponding bit is c = ( a + b )   m o d   k c=(a+b)~mod~k c=(a+b) mod k.
• because k k k is not necessarily 2, but our calculation shows that the formula can not be rewritten as: used dense code ⨁ Inquire ask value = new dense code Old password ⨁ query value = new password Old password ⨁ query value = new password.
• But we can still try the inverse operation and find ( c − b )   m o d   k = a (c-b)~mod~k=a (c − b) mod k=a, let this operation be: c ㊀ b = a c㊀b=a c㊀b=a. Therefore, we still try to ask many times to see if there is a law.
• Considering multiple queries, assume that the initial password is x x x. The new password is y ， z ， f y，z，f y. z, f, the passwords guessed each time are: a 1 ， a 2 ， . . . ， a n a_{1}，a_{2}，...，a_{n} a1​，a2​，...，an​.
  • Then it will meet: x ⨁ y = a 1 x⨁y=a_{1} x⨁y=a1​， y ⨁ z = a 2 y⨁z=a_{2} y⨁z=a2​， z ⨁ f = a 3 z⨁f=a_{3} z⨁f=a3​.
  • a 2 ㊀ y = z a_{2}㊀y=z a2​㊀y=z， a 1 ㊀ x = y a_{1}㊀x=y a1 ㊀ x=y, so z = a 2 ㊀ ( a 1 ㊀ x ) z=a_{2}㊀(a_{1}㊀x) z=a2​㊀(a1​㊀x)， f = a 3 ㊀ [ a 2 ㊀ ( a 1 ㊀ x ) ] f=a_{3}㊀[a_{2}㊀(a_{1}㊀x)] f=a3​㊀[a2​㊀(a1​㊀x)].
  • By analogy, suppose we can still use the in Easy Version x ， s u m x，sum x. sum got our answer. s u m sum sum expression is completely expanded a i a_{i} ai ， we find that:
    • i i When i is an odd number, new dense code = s u m i ㊀ x New password = sum_{i}㊀x New password = sumi ㊀ x.
    • i i When i is an even number, new dense code = s u m i ⨁ x New password = sum_{i}⨁x New password = sumi ⨁ x.
    • and s u m sum sum can be obtained by s u m i = a i ㊀ s u m i − 1 sum_{i}=a_{i}㊀sum_{i-1} sumi​=ai​㊀sumi−1​.
• So we can guess the initial password x x x. The initial password is a [ 0 ， n − 1 ] [0，n-1] Random value of [0, n − 1], guess at most n n You can get the answer n times.

4, Positive solution program

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long ll;
ll T,n,k;
ll add(ll x,ll y)
{
	ll times=1,ans=0;
	while(x>0 || y>0)
	{
		ll t1=x%k;
		ll t2=y%k;
		ans=ans+(t1+t2)%k*times;
		x/=k;
		y/=k;
		times*=k;
	}
	return ans;
}
ll sub(ll x,ll y)
{
	ll times=1,ans=0;
	while(x>0 || y>0)
	{
		ll t1=x%k;
		ll t2=y%k;
		ans=ans+(t1-t2+k)%k*times;
		x/=k;
		y/=k;
		times*=k;
	}
	return ans;
}
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&n,&k);
		ll sum=0,t=0;
		for(ll i=0;i<=n-1;i++)
		{
			ll temp;
			if(i&1)
				temp=sub(sum,i);
			else
				temp=add(sum,i);
			printf("%lld\n",temp);fflush(stdout);
			scanf("%lld",&t);
			if(t)
				break;
			sum=sub(temp,sum);
		}
	}
	
	return 0;
}

E. The Final Pursuit

1, Title Link

https://codeforces.ml/contest/1543/problem/E

2, General idea of the topic

There are t groups of data in total, and each group of data gives an example by using point pairs to represent edges n n n-dimensional hypercube.

Define a common n n n-dimensional hypercube, each point has a number, and the two points are connected. If and only if, the two point numbers have only one bit different in binary. So an ordinary n n n-dimensional hypercube is unique. And we can put an ordinary n n The n-dimensional hypercube corresponds to the cube given in the title through a sequence. Now it is required to find one of the sequences.

Now color each point, there are n n n colors are available. It is required that the color adjacent to a point in the final coloring result n n n points have n n n colors.

Data range: 1 ≤ t ≤ 4096 1≤t≤4096 1≤t≤4096， 1 ≤ n ≤ 16 1≤n≤16 1≤n≤16.

3, Topic analysis

• Finding a suitable sequence can be obtained by means of violence and greed, which is not proved here.
• When painting, we can paint an ordinary one first n n n-dimensional hypercube, and then we get the coloring of the original graph through the sequence we get.
• If n n n is not 2 2 2, there is no legal coloring scheme.
• For an ordinary n n n-dimensional hypercube, if the binary expression of the number of this point is: b n − 1 b n − 2 ... b 2 b 1 b 0 b_{n-1}b_{n-2}\ldots b_2 b_1 b_0 bn − 1 − bn − 2... b2 − b1 − b0, its coloring scheme is: ⨁ i = 0 n − 1 i ⋅ b i \bigoplus\limits_{i=0}^{n-1} i\cdot b_i i=0⨁n−1​i⋅bi​. It is proved as follows:
  • obviously 0 ≤ ⨁ i = 0 n − 1 i ⋅ b i ≤ n − 1 0≤\bigoplus\limits_{i=0}^{n-1} i\cdot b_i≤n-1 0 ≤ i=0 ⨁ n − 1 ⋅ i ⋅ bi ≤ n − 1 is valid.
  • If two points u ， v u，v u. v connected, color c 1 ， c 2 c1，c2 c1, c2, so v = u ⊕ ( 1 ≪ ( c 1 ⊕ c 2 ) ) v=u\oplus(1\ll (c_1\oplus c_2)) v=u⊕(1≪(c1​⊕c2​)). here u ， v u，v u. v only in ( c 1 ⊕ c 2 ) (c_1\oplus c_2) (c1 ⊕ c2) is different and obviously satisfies the connected relationship.

4, Positive solution program

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
#include <vector>

using namespace std;
typedef long long ll;
const ll maxm=100010;
ll n,m;
ll p[maxm];
bool used[maxm];
set<ll> s[maxm];
vector<ll> adj[maxm];
void permuteHypercube()
{
	memset(p,-1,sizeof(p));
	memset(used,false,sizeof(used));
	p[0]=0;
	used[0]=true;
	for(ll u=1;u<m;u++)
	{
		vector<ll> req;
		for(ll i=0;i<n;i++)//Find the points directly connected in simple, from large to small 
		{
			ll v=u^(1<<i);
			if(v<u)//Because only those smaller than it have finished numbering 
				req.push_back(v);
		}
        ll v=req[0];
		for(ll i=0;i<adj[p[v]].size();i++)
		{
			ll w=adj[p[v]][i];//In simple, u and V are connected, so p [v] and P [u] in the original drawing are connected. In the original drawing, P [v] and W are connected, so p[u]=w 
			if(used[w])
				continue;
			if(req.size()==1 || s[w].find(p[req[1]])!=s[w].end())//W is connected by two U's, then p[u] is w 
			{
				p[u]=w;
				used[w]=true;
				break;
			}
		}
    }
}
int main()
{
	ll T;
	scanf("%lld",&T);
	while(T--)
	{
		for(ll i=0;i<maxm;i++)
			adj[i].clear(),s[i].clear();
		scanf("%lld",&n);
		m=(1<<n);
		for(ll i=0;i<n*m/2;i++)
		{
			ll u,v;
			scanf("%lld%lld",&u,&v);
			adj[u].push_back(v);
			adj[v].push_back(u);
			s[u].insert(v);
			s[v].insert(u);
		}
		permuteHypercube();
		for(ll i=0;i<m;i++)
			printf("%lld ",p[i]);
		printf("\n");
		if(n!=1 && n!=2 && n!=4 && n!=8 && n!=16)
		{
			printf("-1\n");
			continue;
		}
		ll simple[maxm],ans[maxm];
		for(ll i=0;i<m;i++)//Color simple first 
		{
			ll color=0;
			for(ll j=0;j<n;j++)
				if(i&(1<<j))
					color=color^j;
			simple[i]=color;
		}
		for(ll i=0;i<m;i++)
			ans[p[i]]=simple[i];
		for(ll i=0;i<m;i++)
			printf("%lld ",ans[i]);
		printf("\n");
	}
	return 0;
}