UVa Online Judge এর কথা খুব পরিচিত তাদের কাছে,যারা কম্পিউটার প্রোগ্রামিং প্রবলেম সল্ভ করার জন্য অনলাইনে ঘাঁটাঘাঁটি করে থাকে। চমৎকার এই সাইটটার প্রবলেমগুলো ওতোটা এডভান্সড না হলেও,টিপিকাল কিন্তু খুব মজার কিছু সমস্যা দিয়ে খুব সুন্দরভাবেই সাইটটা সাজানো হয়েছে। আমাদের আজকের এই ছোট্ট পর্বটা সাজানো হয়েছে এই সাইটটির 847 নং সমস্যা – Multiplication Game দিয়ে। 🙂
Problem টা ছিলো অনেকটা এরকম, Stan আর Ollie একটি খেলা খেলছে। যেখানে খেলা শুরুর প্রথমেই তারা ১ টা নাম্বার (n) ধরে নেয়( এই নাম্বারটির রেঞ্জ 1 < n < 429,49,67,295 ন। আর খেলা শুরু করবে সবসময় Stan; p = 1 ধরে। তখন সে p এর সাথে ১টি নাম্বার গুণ করবে, আর তারপরে Ollie একইভাবে নতুন p এর সাথে আরেকটি নাম্বার গুণ করবে । যেই নাম্বারটি গুণ করতে পারবে তার রেঞ্জ [2,9] ।
এভাবে করে যে সবার শেষে p >= n করতে পারবে সে ই বিজয়ী !! :3
Problem টা এরকম ভাবে আমরা চিন্তা করঃ
১. প্রথমে Stan সর্বোচ্চ কত ধরতে পারে ? (৯) তাই ০ < n <= 9 এর মধ্যে সব মান এ Stan ১ম বারে ই select করতে পারে, তাই ০ < n <= 9 এর মধ্যে যে কোন number এর জন্য Stan winner!
২. আবার ধারা ready করার জন্য আমরা বলতে পারি, যদি Stan highest 9 ধরে আর Ollie lowest 2 ধরে, তাহলে [10,18] এই ব্যবধিতে, সবসময় Ollie winner!
৩. আবার Stan এর জন্য সর্বোচ্চ 9 ধরলে [19, 162] এতে সে বিজয়ী!
এভাবে আমরা ধারা তৈরী করতে পারি : numerical value or log18(base) and depending on Stan’s highest and Ollie’s lowest value:
0 < n < 9 => Stan winner,
9 * 2 = > [10, 18] => Ollie winner [ 0.79 < n < 1]
9 * 2 * 9 =>[19, 162] => Stan [1.0187 < n < 1.760188]
9 * 2 * 9 * 2 =>[163, 324] => Ollie [ 1.7623167 < n < 2]
9 * 2 * 9 * 2 * 9 =>[325,2916] => Stan [ 2.001066183 < n < 2.760187533]
9 * 2 * 9 * 2 * 9 * 2 => [2917, 5832] => Ollie [same process ]
9 * 2 * 9 * 2 * 9 * 2 * 9 [ 5833,52488] => Stan [ same process]
9 * 2 * 9 * 2 * 9 * 2 * 9 * 2[52489,104976] => Ollie [Same process ]
9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 [104977,944784] = > Stan [same process ]
9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2[944785, 1889568] = > Ollie [same process]
9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9[1889569,17006112] = > Stan [same process]
9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2[17006113, 34012224] = > Ollie [Same process]
9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9[34012225, 306110016] = > Stan [same process]
9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2[306110017, 612220032] = > Ollie [same process]
9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9 * 2 * 9[612220032,5509980288] => Stan [same process]
তাহলে এই ব্যবধিতে মান গুলো check করে winner ঠিক করা যাবে ।
Log18 বেসে করলে value ছোট আসবে কিন্তু মান খুব সাবধানে বের করতে হবে কারণ Boundary Point গুলোতে ভুল হতে পারে ।
বোরিং লাগতে পারে,তবে এর মাঝেই প্রোগ্রামিং এর আসল মজা নিহিত! সবাইকে ধন্যবাদ! 🙂