পাইথনের প্রতিটি বাক্সে সমস্ত বল সরানোর জন্য ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি স্ট্রিং আছে যাকে বক্স বলা হয়, যেখানে বক্স[i] '0' ইঙ্গিত করে ith বক্স খালি, এবং '1' নির্দেশ করে এতে একটি বল রয়েছে। এখন, একটি অপারেশনে, আমরা একটি বল একটি বক্স থেকে একটি সংলগ্ন বক্সে নিয়ে যেতে পারি। এটি করার পরে, কিছু বাক্সে একাধিক বল থাকতে পারে। আমাদের n আকারের একটি অ্যারের উত্তর খুঁজে বের করতে হবে, যেখানে উত্তর[i] হল ith বক্সে সমস্ত বল সরানোর জন্য ন্যূনতম সংখ্যক অপারেশন।

সুতরাং, যদি ইনপুটটি বক্সের মত হয় ="1101", তাহলে আউটপুট হবে [4, 3, 4, 5]

• প্রথম বক্সে সমস্ত বল রাখার জন্য, আমাদের একটি অপারেশনের মাধ্যমে বক্স2 থেকে এবং তিনটি অপারেশনের মাধ্যমে শেষ বল থেকে নিতে হবে, তাই মোট 4টি অপারেশন।

• সমস্ত বল দ্বিতীয় বক্সে রাখার জন্য, আমাদের একটি অপারেশনের মাধ্যমে বক্স1 থেকে এবং দুটি অপারেশনের মাধ্যমে শেষ বল থেকে নিতে হবে, তাই মোট 3টি অপারেশন।

• তৃতীয় বক্সে সমস্ত বল রাখার জন্য, আমাদেরকে বক্স২ থেকে নিতে হবে এবং প্রতিটিতে একটি করে অপারেশন করে শেষ করতে হবে এবং বক্স১ থেকে দুটি অপারেশন করে মোট 4টি অপারেশন করতে হবে।

• শেষ বক্সে সমস্ত বল রাখতে, আমাদের তিনটি অপারেশন সহ বক্স1 থেকে এবং দুটি অপারেশন সহ বক্স2 থেকে নিতে হবে, তাই মোট 5টি অপারেশন।

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

• বাম :=0, ডানে :=0, dist :=0

• আমার জন্য 0 থেকে বাক্সের আকার - 1, করুন

  • যদি বক্সগুলি[i] "1" এর মত হয়, তাহলে

    • dist :=dist + i

    • যদি আমি 0 এর সমান হয়, তাহলে

      • left :=left + 1

    • অন্যথায়,

      • ডান:=ডান + 1

• arr :=একটি তালিকা এবং প্রাথমিকভাবে এটিতে dist রাখুন

• আমি রেঞ্জ 1 থেকে বাক্সের আকার - 1 এর জন্য, করুন

  • ঢোকান arr[i-1] + বাম - ডানে arr শেষে

  • যদি বক্সগুলি[i] "1" এর মত হয়, তাহলে

    • left :=left + 1

    • ডান :=ডান - 1

• ফেরত arr

উদাহরণ

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

def solve(boxes):
   left = 0
   right = 0

   dist = 0
   for i in range(len(boxes)):
      if boxes[i] == "1":
         dist += i
         if i == 0:
            left += 1
         else:
            right += 1
   arr = [dist]
   for i in range(1, len(boxes)):
      arr.append(arr[i-1] + left - right)
      if boxes[i] == "1":
         left += 1
         right -= 1
   return arr

boxes = "1101"
print(solve(boxes))

ইনপুট

"1101"

আউটপুট

[4, 3, 4, 5]