দুই বালতি

নির্দেশনা

দুটি ভিন্ন আকারের বালতি এবং প্রথমে কোন বালতি ভরবেন তা দেওয়া থাকলে, বালতিগুলোর মধ্যে কৌশলগতভাবে তরল স্থানান্তর করে সঠিক পরিমাণ লিটার মাপতে কতগুলো অ্যাকশন লাগবে, তা নির্ণয় করুন।

আপনার সমাধানকে কিছু নিয়ম মেনে চলতে হবে:

• আপনি একবারে কেবল একটি অ্যাকশন করতে পারবেন।
• সম্ভাব্য অ্যাকশন মাত্র ৩টি:
  1. একটি বালতি থেকে অন্যটিতে ঢালা, যতক্ষণ না: a) প্রথম বালতিটি খালি হয়ে যায় b) দ্বিতীয় বালতিটি ভরে যায়
  2. একটি বালতি খালি করা এবং অন্যটিতে কিছু না করা।
  3. একটি বালতি ভরা এবং অন্যটিতে কিছু না করা।
• কোনো অ্যাকশনের পরে আপনি এমন অবস্থায় পৌঁছাতে পারবেন না, যেখানে শুরু করার বালতিটি খালি আর অন্যটি ভরা।

আপনার প্রোগ্রাম ইনপুট হিসেবে নেবে:

• বালতি one-এর আকার
• বালতি two-এর আকার
• কাঙ্ক্ষিত কত লিটার পর্যন্ত পৌঁছাতে হবে
• প্রথমে কোন বালতি ভরবেন, বালতি one না বালতি two

আপনার প্রোগ্রাম নির্ধারণ করবে:

• কাঙ্ক্ষিত পরিমাণ লিটারে পৌঁছাতে মোট কতটি অ্যাকশন লাগবে, শুরুর বালতির প্রথম ভরাটসহ
• কাঙ্ক্ষিত পরিমাণ লিটার শেষমেশ কোন বালতিতে থাকবে, বালতি one না বালতি two
• অন্য বালতিতে কত লিটার বাকি থাকবে

লক্ষ করুন: এক বা উভয় বালতিতে যেকোনো সময় পরিবর্তন করা হলে সেটি এক (১) অ্যাকশন হিসেবে ধরা হবে।

উদাহরণ: বালতি one-এ সর্বোচ্চ ৭ লিটার ধরে, আর বালতি two-তে সর্বোচ্চ ১১ লিটার ধরে। ধরা যাক, একটি নির্দিষ্ট ধাপে বালতি one-এ ৭ লিটার আর বালতি two-তে ৮ লিটার আছে (৭,৮)। আপনি যদি বালতি one খালি করেন এবং বালতি two-তে কোনো পরিবর্তন না করেন, ফলে যথাক্রমে ০ লিটার আর ৮ লিটার থাকে (০,৮), তবে সেটি একটি অ্যাকশন হিসেবেই ধরা হবে। এর বদলে, আপনি যদি বালতি one থেকে বালতি two-তে ঢালতেন যতক্ষণ না বালতি two ভরে যায়, ফলে বালতি one-এ ৪ লিটার আর বালতি two-তে ১১ লিটার থাকত (৪,১১), তবে সেটিও কেবল একটি অ্যাকশন হিসেবেই ধরা হতো।

আরেকটি উদাহরণ: বালতি one-এ ৩ লিটার ধরে, আর বালতি two-তে সর্বোচ্চ ৫ লিটার ধরে। আপনাকে বলা হয়েছে, আপনাকে বালতি one দিয়ে শুরু করতে হবে। তাই আপনার প্রথম অ্যাকশন হলো বালতি one ভরা। দ্বিতীয় অ্যাকশন হিসেবে আপনি বালতি one খালি করার সিদ্ধান্ত নেন। তৃতীয় অ্যাকশনে আপনি বালতি two ভরতে পারবেন না, কারণ এতে তৃতীয় নিয়মটি ভাঙে, অর্থাৎ কোনো অ্যাকশনের পরে আপনি এমন অবস্থায় পৌঁছাতে পারবেন না যেখানে শুরুর বালতিটি খালি আর অন্যটি ভরা।

Fullstack Academy-এ <3 দিয়ে লিখেছেন Lindsay Levine।

---

সূত্র

Water Pouring Problem