Posts

Showing posts with the label Ternary Search Problem Tutorial

Light OJ - 1297 - Largest Box - Tutorial

Image
এই প্রব্লেমে আমাদের L দৈর্ঘ্য এবং W প্রস্থের একটা পেপার দেয়া থাকবে। এই পেপারের চার কোণা থেকে X^2 ক্ষেত্রফল বিশিষ্ট চারটি বর্গ ক্ষেত্র কেটে নিতে হবে যাতে অবশিষ্ট পেপার দিয়ে সর্বোচ্চ আয়তনের একটি ঢাকনাবিহীন বক্স বানানো যায়। এই প্রব্লেমের সল্যুশন নিয়ে চিন্তা করার আগে অন্য একটা প্রব্লেম নিয়ে চিন্তা করা যাক।  মনে কর, তোমাকে একটি সংখ্যা X দেয়া আছে। X কে এমন দুটি সংখ্যার যোগফল হিসেবে প্রকাশ করতে হবে যাদের গুণফল সর্বোচ্চ হয়। এক্ষেত্রে ১০=৫+৫ গুণফল ২৫। ১১=৫+৬ গুণফল ৩০।  এই প্রব্লেমেও তোমাকে একইভাবে আয়তন ম্যাক্সিমাইজ করতে হবে। আর তুমি জানো VOLUME = LENGTH * WIDTH * HEIGHT তোমাকে দৈর্ঘ্য প্রস্থ দেয়া থাকবে। উচ্চতা X এর এমন একটি মান বের করতে হবে যাতে আয়তন সর্বোচ্চ হয়। বুঝতেই পারছো উচ্চতা বাড়লে দৈর্ঘ্য , প্রস্থ কমবে।  আগের প্রব্লেম টা বুঝতে পারলে বুঝতেই পারছো এই প্রব্লেমে উচ্চতা X এর ভ্যালু বাড়ার সাথে সাথে একটি নির্দিষ্ট সময় পর্যন্ত আয়তন বাড়বে। এরপর আবার আয়তন কমতে শুরু করবে। অর্থাৎ , গ্রাফটি হবে এমনঃ  আর এই কাজটি তুমি খুব সহজেই টার্নারী সার্চ দিয়ে করতে পারো।...