In this HackerEarth Monk’s Encounter with Polynomial problem solution Our monk, while taking a stroll in the park, stumped upon a polynomial ( A X2 + B X +C ) lying on the ground. The polynomial was dying! Being considerate, our monk tried to talk and revive the polynomial. The polynomial said:
I have served my purpose, and shall not live anymore. Please fulfill my dying wish. Find me the least non-negative integer Xo, that shall make my value atleast K i.e., A Xo2 + B Xo + C >= K .
Help our Monk fulfill the polynomial’s dying wish!
HackerEarth Monk’s Encounter with Polynomial problem solution.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int test;
cin>>test;
while(test--)
{
ll A,B,C,K;
cin>>A>>B>>C>>K;
ll lb=0, ub =100000;
ll ans = -1;
while(lb<=ub)
{
ll mid = (lb+ub)/2;
ll val = A*(mid*mid) + B*mid + C;
if(val >= K){
ans = mid;
ub = mid-1;
}
else
lb = mid+1;
}
cout<<ans<<endl;
}
return 0;
}
Second solution
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
long long f(long long x)
{
return a*x*x + b*x + c;
}
int main()
{
int t;
long long k;
cin>>t;
assert(1 <= t && t <= 100000);
while(t--)
{
cin>>a>>b>>c;
cin>>k;
assert(1 <= a && a <= 1000000);
assert(1 <= b && b <= 1000000);
assert(1 <= c && c <= 1000000);
assert(1 <= k && k <= (long long)1e10);
int ans = 100000000;
int l = 0 , h = -b/(2*a) , m;
while(l <= h)
{
m = (l+h)/2;
if(f(m) >= k)
{
ans = min(ans,m);
l = m + 1;
}
else
{
h = m - 1;
}
}
l = max(0LL,-b/(2*a)) , h = 10000000;
while(l <= h)
{
m = (l+h)/2;
if(f(m) >= k)
{
ans = min(ans,m);
h = m - 1;
}
else
{
l = m + 1;
}
}
cout<<ans<<endl;
}
return 0;
}