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;

}

## 0 Comments