মান লেট k সংখ্যক ক্যান্ডি আছে। আমাদের এগুলো শিশুদের মধ্যে বিতরণ করতে হবে। এখন কিছু নিয়ম আছে
- i-তম শিশু i^2 সংখ্যক ক্যান্ডি পাবে
- যদি i-তম শিশু i^2 সংখ্যক ক্যান্ডি না পায়, তবে সেটা একটি বৈধ সার্ভ হবে না।
ইন্ডেক্স i-এ থাকা যেকোনো শিশু ক্যান্ডি পাবে না যতক্ষণ না ১ থেকে i-1 পর্যন্ত সব শিশু সার্ভ করা হয়
তাহলে, যদি ইনপুট হয় k = 20, তবে আউটপুট হবে ৩ কারণ, প্রথমটি পাবে ১, দ্বিতীয়টি পাবে 2^2 = 4, তৃতীয়টি পাবে 3^2 = 9, কিন্তু চতুর্থটির লাগবে 4^2 = 16, কিন্তু আমাদের কাছে শুধু ৬টি ক্যান্ডি বাকি, তাই এটি বৈধ বিতরণ নয়, তাই শুধু তিনজন শিশু সার্ভ হবে।
এটি সমাধান করতে, আমরা নিচের পদক্ষেপগুলো অনুসরণ করব −
- left := 0, right := k
- যখন right - left > 1, করুন
- mid := floor of (left + right) / 2
- যদি floor of (mid * (mid + 1) * (2 * mid + 1) / 6) > k, তবে
- right := mid
- অন্যথায়,
- left := mid
- যদি right *(right + 1) *(2 * right + 1) <= k * 6, তবে
- right রিটার্ন করুন
- left রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন −
def solve(k): left = 0 right = k while (right - left > 1): mid = (left + right) // 2 if (mid * (mid + 1) * (2 * mid + 1) // 6 > k): right = mid else: left = mid if (right * (right + 1) * (2 * right + 1) <= k * 6): return right return left k = 20 print(solve(k))
ইনপুট
20
আউটপুট
3
