HackerEarth Foo and Exams problem solution

In this HackerEarth Foo and Exams, problem solution Foo was not amongst the most brilliant students of his class. So, he has some pending exams to clear. As the exams are approaching, this time he vowed to pass in all of them. This will only happen if he is not under stress. Foo’s stress can be calculated using a simple function called Foo_function which depends upon the time for which Foo studies continuously .

Foo_funtion is defined as follows:

F(t)=A(t^3)+B(t^2)+C*(t)+D, F(t)<=10^18

where A,B,C,D belong to the set of prime numbers. t is the time in minutes for which foo studies continuously.

As foo is not very good at solving cubic equations, he seeks your help to find out the maximum number of minutes for which he can study continuously without taking stress. Help him find t such that F(t+1) > K, and F(t) <= K, where K is the maximum stress Foo can bear.

HackerEarth Foo and Exams problem solution.

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull cube(ull num)
{
    return num*num*num; // return cube of a number
}

ull square(ull num)
{
    return num*num; // return square of a number
}

unsigned long long foo_function(int a,int b,int c,int d,int t)
{
    return ((ull)a*cube(t)+b*square(t)+c*t+d); // foo_funtion returning F(t)
}

int binarysearch(int a,int b,int c,int d,int left,int right,ull val)
{
    unsigned long long temp;
    int low=left,high=right;

    while(low<=high)
    {

        int mid=(low+high)/2;

        temp=foo_function(a,b,c,d,mid);

        if(temp<=val&&(mid==right||(foo_function(a,b,c,d,mid+1))>val))
        return mid;

        if(temp>val)
          high=mid-1;
        else if(temp<val)
          low=mid+1;

    }
}
int main(){

 int t;
 cin>>t; // test cases
 while(t--)
 {
    int a,b,c,d;    // value of a,b,c,d
    cin>>a>>b>>c>>d;
    ull val;
    cin>>val;
    int lower=1;
    int upper=1000000;
    cout<<binarysearch(a,b,c,d,lower,upper,val)<<endl;
 }
 return 0;
}

Second solution

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cassert>
#include<set>
#include<queue>
#include<map>

using namespace std;

#define vi vector < int >
#define pb push_back
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 2000000000
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define all(x) x.begin(),x.end()
#define eps 1e-9

ll a,b,c,d,k;

ll eval(ll t)
{
   double T = t;
   double tmp =  a*T*T*T + b*T*T + c*T + d;
   if(tmp + eps > 1e18 )
   return k+1;
   return a*t*t*t + b*t*t + c*t + d;
}

int main()
{
    int t;
    scanf("%d",&t);
    assert(1<=t && t<=10000);
    while(t--)
    {
         scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
         assert(2<=a && a<=(ll)1e18);
         assert(2<=b && b<=(ll)1e18);
         assert(2<=c && c<=(ll)1e18);
         assert(2<=d && d<=(ll)1e18);
         assert(2<=k && k<=(ll)1e18);
         
         ll lo = 0, hi = (ll)1e6 , mid;
         ll ans = 0;
         while(lo<=hi)
         {
             mid = (lo+hi)>>1;
             if(eval(mid)<=k)
             {
                 ans = mid;
                 lo = mid+1;
             }
             else
             {
                 hi = mid-1;
             }
         }         
         assert(ans>=0);
         printf("%lldn",ans);
    }
    //system("pause");
    return 0;
}

HackerEarth Foo and Exams problem solution

HackerEarth Foo and Exams problem solution.

Second solution

Leave a Reply

Pages

Practice