1109 - False Ordering

1109 - False Ordering

Solution 01:

#include<bits/stdc++.h>

using namespace std;

void Sieve(int n, bool prime[], bool primesqure[], int a[])

{

    for(int i = 2; i <= n; i++)

        prime[i] = true;

    for(int i = 0; i <= (n*n + 1); i++)

        primesqure[i] = false;

    prime[1] = false;

    for(int p = 2; p*p <= n; p++){

        if(prime[p] == true){

            for(int i = p*2; i <= n; i += p)

                prime[i] = false;

        }

    }

    int j = 0;

    for(int p = 2; p <= n; p++){

        if(prime[p])

        {

            a[j] = p;

            primesqure[p*p] = true;

            j++;

        }

    }

}

int countDivisor(int n)

{

    if(n == 1)return 1;

    bool prime[n+1], primesqure[n*n +1];

    int a[n];

    Sieve(n,prime, primesqure, a);

    int ans = 1;

    for(int i = 0; ; i++){

        if(a[i]*a[i]*a[i] > n)break;

        int cnt = 1;

        while(n % a[i] == 0){

            n = n/a[i];

            cnt = cnt + 1;

        }

        ans = ans * cnt;

    }

    if(prime[n])ans = ans * 2;

    else if(primesqure[n])ans = ans*3;

    else if(n != 1)ans = ans*4;

    return ans;

}

bool cmp (const pair<int, int> &aa, const pair<int, int> &bb)

{

  if(aa.first != bb.first )

    {

        return aa.first < bb.first;

        }

            else     {

        return(aa.second > bb.second);

    }

}

int main()

{

    vector<pair<int, int> >Vp;

    for(int i = 1; i <= 1000; i++){

        int x = countDivisor(i);

        //cout << i << " -------> "<<x<<endl;

        Vp.push_back({x,i});

    }

    sort(Vp.begin(), Vp.end(),cmp);

   // for(auto x: Vp){

       // cout << x.first << " "<< x.second<<endl;

   // }

   int t;

   cin >> t;

   for(int cs = 1; cs <= t; cs++){

        int x;

   cin >> x;

   cout << "Case "<<cs<< ": "<<Vp[x-1].second<<endl;

   }

   return 0;

}

Solution 02:

#include<bits/stdc++.h>

using namespace std;

int countDivisors (int n)

{

    int cnt = 0;

    for(int i = 1; i <= sqrt(n); i++){

        if(n % i == 0){

            if(n/i == i)cnt++;

            else cnt += 2;

        }

    }

    return cnt;

}

bool cmp (const pair<int, int> &aa, const pair<int, int> &bb)

{

  if(aa.first != bb.first )

    {

        return aa.first < bb.first;

        }

            else     {

        return(aa.second > bb.second);

    }

}

int main()

{

    vector<pair<int, int> >Vp;

    for(int i = 1; i <= 1000; i++){

        int x = countDivisors(i);

        //cout << i << " -------> "<<x<<endl;

        Vp.push_back({x,i});

    }

    sort(Vp.begin(), Vp.end(),cmp);

   // for(auto x: Vp){

       // cout << x.first << " "<< x.second<<endl;

   // }

   int t;

   cin >> t;

   for(int cs = 1; cs <= t; cs++){

        int x;

   cin >> x;

   cout << "Case "<<cs<< ": "<<Vp[x-1].second<<endl;

   }

   return 0;

}

Share: