Binary search in C++ of Codejam Round1A ProblemA -

i think code snippet in contest analysis not correct, while(right - left >= 1) may fall infinite loop. use > instead of >=. doesn't give correct answer.

however, code passes assertions, means left result , right bound .. think code correct thing, ...

here's 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; } 

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