পাইথনে নিয়ম বজায় রেখে তাদের বিতরণ করার সময় অনেক শিশু ক্যান্ডি পাবে তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের k সংখ্যক ক্যান্ডি আছে। এগুলো আমাদের শিশুদের মধ্যে বিতরণ করতে হবে। এখন কিছু নিয়ম আছে

এই শিশু i^2 সংখ্যক ক্যান্ডি পাবে
সূচী 1 থেকে i-i পর্যন্ত সমস্ত শিশুকে পরিবেশন করা না হওয়া পর্যন্ত I-এ কোনো শিশু কোনো মিষ্টি পাবে না
যদি বাচ্চারা i^2 সংখ্যক ক্যান্ডি না পায়, তাহলে সেটা বৈধ পরিবেশন নয়।

সুতরাং, যদি ইনপুটটি k =20 এর মত হয় তবে আউটপুটটি 3 হবে কারণ, প্রথমটি 1 পাবে, দ্বিতীয়টি 2^2 =4 পাবে, তৃতীয়টি 3^2 =9 পাবে, তবে চতুর্থটির প্রয়োজন 4। ^2 =16, কিন্তু আমাদের কাছে মাত্র 6টি ক্যান্ডি বাকি আছে, তাই এটি একটি বৈধ বিতরণ নয়, তাই শুধুমাত্র তিনটি শিশুকে পরিবেশন করা হবে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

বামে :=0, ডানে :=k
যখন ডান - বাম> 1, করুন
- মাঝে :=তল (বাম + ডান) / 2
- যদি (মধ্য * (মধ্য + 1) * (2 * মধ্য + 1) / 6)> k, তাহলে
  - ডান :=মধ্য
- অন্যথায়,
  - বামে :=মধ্য
যদি ডান *(ডান + 1) *(2 * ডান + 1) <=k * 6, তারপর
- ডানে ফিরুন
বাম দিকে ফিরুন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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))