Here Everything Is Fair

 আসো  Modulus (%) বের করি।  ধরো তোমাকে ২ টা সংখ্যা a আর b দেওয়া আছে। তোমাকে (a+b)%c বের করতে হবে। যেখানে a,b,c এর মান 2 ^ 64 - 1 অব্দি হতে পারে  যা c/c++ সর্বচ্চ মান (মানে unsigned long long int এ। এর চেয়ে বেশি ভ্যালু হলে আমরা সেটা String দিয়ে হ্যান্ডেল করি)।   কি ভাবছ? অনেক সহজেই  ans=(a+b)%c ;   বের করলেই হয়ে গেলো তাইনা ? আচ্ছা ধরি, a= 1844674407370955161 4 , b= 100 , ans = ( 184467440737095516 1 4 +  100 ) % 18446744073709551615    [যেখানে c= 2 ^ 64 - 1 ] এভাবে  বের করা কি সম্ভব?, আসলে কি হবে এখানে ?  ( 184467440737095516 1 4 + 100 ) যোগ করলে overflow হবে। ( 2 ^ 64 - 1 এর চেয়ে বেশি হয়ে যাবে যা unsigned long long int   এও আটানো সম্ভব হবে না ), যদি যোগ-ই করতে না পারি তাহলে কেমনে mod c (%c ) বের করবো? যাক তাহলে  ans = (a+b)%c;  সমাধান কাজ করলো না। আচ্ছা আরেকটু ভাবি,  উপরের মতো করে যদি না হয় তাহলে আমাদের পরবর্তি ধাপ কি হতে পারে? উমম,!  আমরা জানিতো  (a+b)%c থাকলে আমরা এটাকে (a%c ...

আচ্ছা আজকে বাইনারি সার্চের একটা প্রাক্টিক্যাল ইমপ্লিমেন্টেসান এর সীমাবদ্ধতা দেখি।  আসা করা যাই আমরা সবাই জানি বাইনারি সার্চ কি, কিভাবে কাজ করে । তো দেখি আমরা কি সমস্যার সম্মুখিন হতে পারি বাইনারি সার্চ প্রাক্টিক্যালি ইমপ্লিমেন্ট করতে গেলে।  ধরো, তোমাকে 100 থেকে 18,446,744,073,709,551,615 এর মধ্যে একটা  x  সংখ্যা খুঁজে বেড় করতে কতোবার খুঁজা লাগবে বলা হল। তুমি কি করবে?  সুন্দর করে তুমি বাইনারি সার্চের কোড লিখবে। (নিচের মতো করে) unsigned long long b=100, e= 18446744073709551615, mid,c=0; while (b<e){      mid = (b+e)/2;      c++;     if (mid==x) return c;     if (mid<x) b=mid+1;     else e=mid-1;   } কিন্তু একটু ভাবোতো , তোমার কোড কি  কাজ করবে? আমার মনে হয় করবে না, তোমাদের কি মনে হয়?   আচ্ছা আসো এখন দেখি কেন কাজ করবে না উপরের কোড টা।  আসলে তোমাকে 100 থেকে 18446744073709551615 ( 2 ^ 64 - 1 ) এর মধ্যে  x খুঁজে বের করতে কতবার খুঁজা লাগবে তা বের করতে ...