codeforces 893

mail@pastecode.io avatarunknown
c_cpp
a month ago
2.6 kB
2
Indexable
Never
#include<bits/stdc++.h>
#include<string>
#include<limits.h>
#include<algorithm>
#include<numeric>
#define ll long long
#define fr(i,a,b) for(int i=a;i<b;i++)
#define cap(s) transform(s.begin(), s.end(),s.begin(),::toupper)
#define pb push_back
#define smol(s) transform(s.begin(), s.end(),s.begin(),::tolower)
using namespace std;

int factorial(int n)
{
    return (n==1 || n==0) ? 1: n * factorial(n - 1); 
}

double nck(int n,int k){
	double val=((double)factorial(n))/(factorial(k)*factorial(n-k));
	return val;
}

bool isPrime(ll n)
{
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to square root of n
    for (ll i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
 
    return true;
}

void backtrack(vector<int>& nums, int start,
               vector<vector<int> >& resultset,
               vector<int> curr_set)
{
    resultset.push_back(curr_set);
 
    for (int i = start; i < nums.size(); i++) {
 
        // If the current element is repeating
        if (i > start
            && nums[i] == nums[i - 1]) {
            continue;
        }
 
        // Include current element
        // into the subsequence
        curr_set.push_back(nums[i]);
 
        // Proceed to the remaining array
        // to generate subsequences
        // including current array element
        backtrack(nums, i + 1, resultset,
                  curr_set);
 
        // Remove current element
        // from the subsequence
        curr_set.pop_back();
    }
}

vector<vector<int> > AllSubsets(
    vector<int> nums)
{
    // Stores the subsequences
    vector<vector<int> > resultset;
 
    // Stores the current
    // subsequence
    vector<int> curr_set;
 
    // Sort the vector
    sort(nums.begin(), nums.end());
 
    // Backtrack function to
    // generate subsequences
    backtrack(nums, 0, resultset,
              curr_set);
 
    // Return the result
    return resultset;
}

int score(vector<int> vt){
	set<int> x;
	for(int i=0;i<vt.size()-1;i++){
		x.insert(__gcd(vt[i],vt[i+1]));
	}
	return x.size();
}

int main(){
	ll t;
	cin>>t;
	// cin.ignore(numeric_limits<streamsize>::max(), '\n');
	while(t--){	
		long long n;
		cin>>n;
		vector<int> v;
		int max_score = INT_MIN;
		int points;
		for(int i=1;i<=n;i++){
			v.push_back(i);
		}
		vector<vector<int>> results = AllSubsets(v);
		for(int i=0;i<results.size();i++){
			points = score(results[i]);
			if(points>max_score){
				max_score=points;
			}
		}
		cout<<points<<endl;

	}	
	return 0;
}