Solutions for https://www.tcscodevita.com/CodevitaV9/samplequestion.jsp

all code.md

F

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long sum = 0;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        long in;
        cin >> in;
        in = (long)pow(2, in);
        string str = to_string(in);
        str = str.length() > 2 ? str.substr(str.length() - 2) : str;
        in = stoi(str);
        sum += in;
    }

    cout << sum % 100 << endl;

    return 0;
}

Prob E

#include<bits/stdc++.h>
#define ll long long int

using namespace std;

bool isPerfectSquare(long double x) 
{   
  // Find floating point value of  
  // square root of x. 
  long double sr = sqrt(x); 
  
  // If square root is an integer 
  return ((sr - floor(sr)) == 0); 
} 
  
bool divisible_perfect(int num){
  int flag = 0;
for(ll i = 2; i < num; i++){
    if ( num % (i*i) == 0){
        return true;
        flag = 1;
        break;
    }
}
if(flag == 0){
    return false;
}

}  

int square_free_number_check(int num){
    ll count = 0;
    vector<int> store;

    for(ll i = 2;i<num;i++){
        if(num%i == 0 && !isPerfectSquare(i)){
          store.push_back(i);
        }
    }

    for(auto i:store){
      if(num % i == 0 && !divisible_perfect(i)){
        cout<<i<<endl;
        count++;
      }
    }

    return count;
}

int main(int argc, char const *argv[])
{
  ll N;
  cin>>N;
  cout<<square_free_number_check(N);
  return 0;
}

E

#include  <math.h>
using namespace std;
int main()
{
    long int n;
    double sqnum;
    long int i,j=0,flag,chksqr,temp[10000];
  	int count=0,k;
  	cout<<"Enter the number:";
    cin>>n;
    
    for(i=2;i<=n/2;i++)
    {
        if(n%i==0)
        {    
            count++;
            sqnum=sqrt(i);
            chksqr=sqnum;
            if(chksqr==sqnum)
            {
                count--;
                temp[j]=i;
                j++;
            }
            else
            {
                for(k=0;k<j;k++) { if(i>temp[k] && j!=0)
                    {
                        if(i%temp[k]==0)
                        {	
                          	count--;
                        	k=j+1;
                        }
                    }
                    else
                        break;
                }
            }
        }
    }

    cout<<count;
    return 0;
}```

B

Use mini max approach

#include<bits/stdc++.h>

using namespace std;

int min_effort(vector<int> a,int n,int k){
    int min = a[0];
    int max = a[0];
    int m;
    for(int i =0; i < n; i++){
        if(min > a[i]){
            min = a[i];
        }
        if(max < a[i]){
            max = a[i];
        }
        m = a[k-1];
    }
    int res = (2*m*min)+(min*max);

    return res;
    
}

int main(int argc, char const *argv[])
{
    vector<int> a = {20,50,30,80,70};
    cout<<min_effort(a,a.size(),2);
    return 0;
}

//B

#include<bits/stdc++.h>
#define ll long long int
#define REP(i,n) for(ll i=0;i<n;i++)
using namespace std;
void solve(){
ll n,k;
cin>>n>>k;k--;
ll a[n];
ll b[n];
REP(i,n)
{
cin>>a[i];
b[i]=a[i];
}
sort(b,b+n);
ll mini=b[0];
ll last=b[n-1];
for(ll i=n-2;i>=k;i--)
{
b[i+1]=b[i];
}

b[k]=last;
map<ll,vector > m;
REP(i,n)
{
m[a[i]].push_back(i);
}
ll cost=0;
if(a[0]!=b[0])
{
ll real=m[b[0]].back();
swap(a[real],a[0]);
cost+=a[real]*a[0];
m[b[0]].pop_back();

}
for(ll i=1;i<n;i++)
{
if(a[i]==b[i])
continue;
ll real=m[b[i]].back();

swap(a[real],a[i]);
cost+=min(a[real]*a[i],mini*a[real]+mini*a[i]+mini*min(a[i],a[real]));
m[b[i]].pop_back();

}
cout<<cost<<endl;
}
int main(){
solve();

return 0;

}

Complexity nlogn

//G
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define REP(i,n) for(ll i=0;i<n;i++)
using namespace std;
ll n;
const ll nxm=30;
char a[nxm][nxm];
bool vis[nxm][nxm];
void recur(ll i,ll j)
{
vis[i][j]=1;
if(a[i][j]=='A')
{

    if(i+1<n && !vis[i+1][j] &&(a[i+1][j]=='R' || a[i+1][j]=='D'))
        recur(i+1,j);
    if(i-1>=0 && !vis[i-1][j] && (a[i-1][j]=='R' || a[i-1][j]=='D'))
        recur(i-1,j);
    if(j-1>=0 && !vis[i][j-1] && (a[i][j-1]=='R' || a[i][j-1]=='D'))
        recur(i,j-1);
    if(j+1<n && !vis[i][j+1] && (a[i][j+1]=='R' || a[i][j+1]=='D'))
        recur(i,j+1);
    if(i-1>=0 && j-1>=0 && !vis[i-1][j-1] && (a[i-1][j-1]=='R' || a[i-1][j-1]=='D'))
        recur(i-1,j-1);
    if(i-1>=0 && j+1<n && !vis[i-1][j+1] && (a[i-1][j+1]=='R' || a[i-1][j+1]=='D'))
        recur(i-1,j+1);
    if(i+1<n && j-1>=0 && !vis[i+1][j-1] && (a[i+1][j-1]=='R' || a[i+1][j-1]=='D'))
        recur(i+1,j-1);
    if( i+1<n && j+1<n && !vis[i+1][j+1] && (a[i+1][j+1]=='R' || a[i+1][j+1]=='D'))
        recur(i+1,j+1);


}
else if(a[i][j]=='D')
    cout<<"DESTINATION"<<endl;
else
{
    vector<char> d;
    if(i+1<n)
        d.push_back(a[i+1][j]);
     if(i-1>=0)
        d.push_back(a[i-1][j]);
    if(j-1>=0)
        d.push_back(a[i][j-1]);
    if(j+1<n)
        d.push_back(a[i][j+1]);
    if(i-1>=0 && j-1>=0)
        d.push_back(a[i-1][j-1]);
     if(i-1>=0 && j+1<n)
        d.push_back(a[i-1][j+1]);
     if(i+1<n && j-1>=0)
        d.push_back(a[i+1][j-1]);
     if(i+1<n && j+1<n)
        d.push_back(a[i+1][j+1]);

    sort(d.begin(),d.end());
    REP(it,d.size())
    {
        if(d[it]!='M' && d[it]!='R' && d[it]!='D' && d[it]!='A')
        cout<<d[it]<<" ";
    }
    cout<<endl;

    if(i+1<n && !vis[i+1][j] &&(a[i+1][j]=='R' || a[i+1][j]=='D'))
        recur(i+1,j);
    if(i-1>=0 && !vis[i-1][j] && (a[i-1][j]=='R' || a[i-1][j]=='D'))
        recur(i-1,j);
    if(j-1>=0 && !vis[i][j-1] && (a[i][j-1]=='R' || a[i][j-1]=='D'))
        recur(i,j-1);
    if(j+1<n && !vis[i][j+1] && (a[i][j+1]=='R' || a[i][j+1]=='D'))
        recur(i,j+1);
    if(i-1>=0 && j-1>=0 && !vis[i-1][j-1] && (a[i-1][j-1]=='R' || a[i-1][j-1]=='D'))
        recur(i-1,j-1);
    if(i-1>=0 && j+1<n && !vis[i-1][j+1] && (a[i-1][j+1]=='R' || a[i-1][j+1]=='D'))
        recur(i-1,j+1);
    if(i+1<n && j-1>=0 && !vis[i+1][j-1] && (a[i+1][j-1]=='R' || a[i+1][j-1]=='D'))
        recur(i+1,j-1);
    if( i+1<n && j+1<n && !vis[i+1][j+1] && (a[i+1][j+1]=='R' || a[i+1][j+1]=='D'))
        recur(i+1,j+1);

}

}
void solve(){
cin>>n;
ll i1,j1;
REP(i,n) REP(j,n)
{
cin>>a[i][j];
if(a[i][j]=='A')
{
i1=i;j1=j;
}
}
recur(i1,j1);

}
int main(){
solve();
return 0;
}

G

#include <bits/stdc++.h>

using namespace std;

short unsigned int n;
pair<int, int> destination;
char inp_array[20][20];
pair<int, int> cursor;

bool isValidIndex(pair<int, int> co_ordinate)
{
    if ((co_ordinate.first >= 0 && co_ordinate.first < n) && (co_ordinate.second >= 0 && co_ordinate.second < n))
        return true;
    else
        return false;
}

bool isObstacle(short int x, short int y)
{
    if ((inp_array[x][y] != 'A') &&
        (inp_array[x][y] != 'D') &&
        (inp_array[x][y] != 'M') &&
        (inp_array[x][y] != 'R') &&
        (inp_array[x][y] != 'X'))

        return true;
    else
        return false;
}

void visited(pair<int, int> node)
{
    inp_array[node.first][node.second] = 'X';
}

void obstacleList(pair<int, int> node)
{
    vector<char> obs;
    for (int i = node.first - 1; i <= node.first + 1; i++)
    {
        for (int j = node.second - 1; j <= node.second + 1; j++)
        {
            if (isValidIndex(make_pair(i, j)))
            {
                if (isObstacle(i, j))
                {
                    obs.push_back(inp_array[i][j]);
                }
                else if (inp_array[i][j] == 'R' || inp_array[i][j] == 'D')
                {
                    cursor = make_pair(i, j);
                }
            }
        }
    }

    sort(obs.begin(), obs.end());
    if (obs.size() == 0)
    {
        cout << "NO HURDLES" << endl;
    }
    else
    {
        for (char a : obs)
        {
            cout << a << " ";
        }
        cout << endl;
    }
}

void solve()
{
    while (cursor != destination)
    {
        visited(cursor);
        obstacleList(cursor);
    }
    if (cursor == destination)
        cout << "DESTINATION" << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> inp_array[i][j];

            if (inp_array[i][j] == 'D')
            {
                destination = make_pair(i, j);
            }
            else if ((inp_array[i][j] == 'R') &&
                     ((i == 0 && j == 0) ||
                      (i == 1 && j == 1) ||
                      (i == 1 && j == 0)))
            {
                cursor = make_pair(i, j);
            }
        }
    }
    solve();
}

E

--
Follows time limitation. Output time 1s

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

time_t start, end_time;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

int x, counter = 0;
unordered_set<int> squareFreeFactor;
bool flag = true;

bool isPerfectSquare(int x)
{
    return ((floor(sqrt(x)) - sqrt(x)) == 0);
}

unordered_set<int> factor(int a)
{
    unordered_set<int> currentFactor;
    for (int i = 2; i < a / 2; i++)
    {
        if (a % i == 0)
        {
            if (a / i == i)
            {
                if (!isPerfectSquare(i))
                    currentFactor.insert(i);
                else
                    flag = false;
            }
            else
            {
                if (!isPerfectSquare(i))
                    currentFactor.insert(i);
                else
                    flag = false;
                if (!isPerfectSquare(a / i))
                    currentFactor.insert(a / i);
                else
                    flag = false;
            }
        }
    }
    return currentFactor;
}

void factor_void(int a)
{

    for (int i = 2; i < sqrt(a); i++)
    {
        if (a % i == 0)
        {
            if (a / i == i)
            {
                if (isPerfectSquare(i))
                    flag = false;
            }
            else
            {
                if (isPerfectSquare(i))
                    flag = false;
                if (isPerfectSquare(a / i))
                    flag = false;
            }
        }
    }
}

void solve()
{
    unordered_set<int> fac = factor(x);
    if (flag)
    {
        counter++;
    }
    else
    {
        flag = true;
    }
    for (int a : fac)
    {
        factor_void(a);
        if (flag)
        {
            counter++;
        }
        else
        {
            flag = true;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> x;
    time(&start);
    solve();
    
    cout << counter << endl;
    time(&end_time);

    cout << double(end_time - start) << "s";
}