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

মনে করুন boxes নামক একটি বাইনারি স্ট্রিং আছে, যেখানে boxes[i] = '0' বোঝায় i-তম বক্স খালি, '1' বোঝায় সেটাতে একটি বল আছে। এক অপারেশনে আমরা একটি বলকে আসল বক্স থেকে অ্যাডজেসেন্ট বক্সে সরাতে পারি। এর পর কিছু বক্সে একাধিক বল থাকতে পারে। আমাদের answer নামক একটি n সাইজের অ্যারে বের করতে হবে, যেখানে answer[i] হলো সব বল i-তম বক্সে আনতে ন্যূনতম অপারেশন।

যেমন, ইনপুট boxes = "1101" হলে, আউটপুট হবে [4, 3, 4, 5]

• প্রথম বক্সে সব বল আনতে: বক্স ২ থেকে ১ অপারেশন, শেষ বক্স থেকে ৩ অপারেশন, মোট ৪।

• দ্বিতীয় বক্সে: বক্স ১ থেকে ১, শেষ থেকে ২, মোট ৩।

• তৃতীয় বক্সে: বক্স ২ এবং শেষ থেকে ১-১, বক্স ১ থেকে ২, মোট ৪।

• চতুর্থ বক্সে: বক্স ১ থেকে ৩, বক্স ২ থেকে ২, মোট ৫।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

• left := 0, right := 0, dist := 0

• i = 0 থেকে boxes-এর সাইজ - ১ পর্যন্ত

  • যদি boxes[i] == "1" হয়, তবে

    • dist += i

    • যদি i == 0 হয়, তবে left++

    • অন্যথায় right++

• arr := [dist] দিয়ে ইনিশিয়ালাইজড লিস্ট

• i = 1 থেকে boxes-এর সাইজ - ১ পর্যন্ত

  • arr.append(arr[i-1] + left - right)

  • যদি boxes[i] == "1" হয়, তবে

    • left++, right--

• 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]