Codeworks round 651 (Div. 2) ABCD solution

A. Maximum GCD Topic link

Divide 2 that will do

#include<iostream>
using namespace std;
int main()
{
    
	int n;
	int t;
	scanf("%d",&t);
	while(t--){
    
		cin>>n;
		cout<<n/2<<endl;
	}
	return 0;
}

B. GCD Compression Topic link

Answer key : We can pair odd numbers and even numbers separately , In this way, the sum of each pair of numbers can be 2 to be divisible by . Please note that , We can always form n−1 Yes , Because in the worst case , We will discard an odd number and an even number . If we discard multiple even or odd numbers , We can form another pair with an even sum .

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
int a[N];

int main()
{
    
	int t;
	cin >> t;
	while(t--)
	{
    
		cin >> n;
		vector< int > even, odd;
		for(int i = 1; i <= 2 * n; i++)
		{
    
			cin >> a[i];
			if(a[i] % 2)
				odd.push_back(i);
			else
				even.push_back(i);
		}
		vector< pair< int, int > > ans;
		for(int i = 0; i + 1 < odd.size(); i += 2)
			ans.push_back({
    odd[i], odd[i + 1]});
		for(int i = 0; i + 1 < even.size(); i += 2)
			ans.push_back({
    even[i], even[i + 1]});
		for(int i = 0; i < n - 1; i++)
			cout << ans[i].first << " " << ans[i].second << endl;
	}
	return 0;
}

C. Number Game Topic link

The question ： Give you a number n, You can do two things , Divide by any greater than 1 The latter is in n Greater than 1 Subtract 1,Ashishgup Go ahead , Until I can't go , If Ashishgup I can't go , be FastestFinger win .
Answer key ：FastestFinger stay n=1,n=2 Of x Power ,n Is even and n/2 Greater than or equal to 3 Win in three cases

#include<bits/stdc++.h>
using namespace std;
bool isprime(int x){
    
	if(x<3)return 0;
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0)
			return 0;
	return 1;
}
bool check(int x){
    
	for(int i=2;i<31;i++)if(pow(2,i)==x)return 1;
	return 0;
}
int main(){
    
	int t,n;cin>>t;
	while(t--){
    
	cin>>n;
		if(n==1||check(n)||(n%2==0&&isprime(n/2)))
			cout<<"FastestFinger\n";
		else
			cout<<"Ashishgup\n";
	} 
}

D. Odd-Even Subsequence Topic link

Answer key :
Binary search for answers , And check whether it is given x, At least a subsequence of length can be formed .k Make all elements in the odd index or even index ≤x.

#include < bits/stdc++.h >
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N = 2e5 + 5;

int n, k;
int a[N];

bool check(int x, int cur)
{
    
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
    
		if(!cur)
		{
    
			ans++;
			cur ^= 1;
		}
		else
		{
    
			if(a[i] <= x)
			{
    
				ans++;
				cur ^= 1;
			}
		}
	}
	return ans >= k;
}

int binsearch(int lo, int hi)
{
    
	while(lo < hi)
	{
    
		int mid = (lo + hi) / 2;
		if(check(mid, 0) || check(mid, 1))
			hi = mid;
		else
			lo = mid + 1;
	}
	return lo;
}

int32_t main()
{
    
	IOS;
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	int ans = binsearch(1, 1e9);
	cout << ans;
	return 0;
}