# Binary search in C++ of Codejam Round1A ProblemA

I think the code snippet in contest analysis is not correct, while(right - left >= 1) may fall into infinite loop. So I use > instead of >=. But it doesn't give the correct answer.

However, the code passes the assertions, which means left is the result and right is the bound .. I think my code does the correct thing, but ...

Here's my code:

#define _USE_MATH_DEFINES #include<cstdio> #include<cassert> #include<cmath> int main() { int cases; scanf("%d", &cases); for(int c=1;c<=cases;c++) { double r, t; //long long t; scanf("%lf %lf", &r, &t); long long maxn = (long long)((sqrt((2*r-1)*(2*r-1)+8*t)-2*r+1)/4)+1; long long left=0, right=1; long long re= (long long)t; while ((2*r-1)*right+right*right*2 <= t) { left = right; right *= 2; } //printf("%lld\n",maxn); while(left+1<right) { long long m = left + (right - left)/2; double tt = (2*r-1)*1.0*m+2*m*m; if (tt<=t) left=m; else right=m; } assert((2*r-1)*1.0*right+2*right*right>t); assert((2*r-1)*1.0*left+2*left*left<=t); printf("Case #%d: %lld\n", c, left); } return 0; }

## Answers

Likely, double tt = (2*r-1)*1.0*m+2*m*m; is losing precision. double only has about 52 bits of integer precision.