Dr Wu 5 uva 2294 (Live)

Easy Binary Search Problem .

Code : -

Complexity : O(log2(range)) per case

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

using namespace std; double arr[1005]; int comp(double a,double b) { double diff = a - b; if(diff>EPS) return 1; //a is bigger if(diff<-EPS) return -1; // b is bigger else return 0; //equal } int main() { //pre-processing arr[0] = 0.000; loop(x,1,1000) { //For x number of cards you will get overhang of arr[x] arr[x] = arr[x-1] + (double)(1.00000/(x+1))*1.0000 ; } while(true){ int num_cards; // Binary search on number of cards double actual_overhang; cin>>actual_overhang; if(comp(actual_overhang,0.00000)==0) { return 0 ; } int lo_cards = 0; int hi_cards = 900; //pretty safe to assume while(lo_cards<=hi_cards) { int mid_cards = (lo_cards + hi_cards )/2; int mid_cards_plus_extra = mid_cards + 1; double lower_overhang = arr[mid_cards]; double hi_overhang = arr[mid_cards_plus_extra]; if(comp( lower_overhang,actual_overhang ) == -1 && comp(hi_overhang,actual_overhang)==1) { num_cards = mid_cards_plus_extra; break; } if(comp(lower_overhang,actual_overhang)==0) { num_cards = mid_cards; break; } if(comp(lower_overhang,actual_overhang)==-1) //Too less cards I have guess { lo_cards = mid_cards; } if(comp(lower_overhang,actual_overhang)==1 ) //Too many cards I have guessed { hi_cards = mid_cards; } } pf("%d card(s)\n",num_cards); } return 0; }