codeforces 893
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; }