পাইথনে কিউব গড়ে তোলা সম্ভব কিনা চেক করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে nums আছে যাতে nটি ভিন্ন কিউবের সাইজ রয়েছে, সেগুলো অনুভূমিকভাবে রাখা আছে। আমাদের কিউবগুলোকে লম্বভাবে গড়ে তোলা হবে। নতুন কিউব নিচের শর্ত মেনে চলতে হবে:

• যদি i-তম কিউব j-তম কিউবের উপরে থাকে, তবে j-তম কিউবের সাইড লেংথ i-তম কিউবের সাইড লেংثের চেয়ে বড় বা সমান হতে হবে।

যখন আমরা লম্বভাবে গড়িয়ে তোলব, তখন আমরা কিউবগুলোকে শুধু বাম পাশ বা ডান পাশ থেকে নিতে পারব, মাঝপথ থেকে নয়। আমাদের চেক করতে হবে আমরা সেগুলো গড়ে তুলতে পারি কিনা।

উদাহরণস্বরূপ, যদি ইনপুট nums = [1,2,3,7,8] হয়, তবে আউটপুট হবে True কারণ আমরা ডান থেকে বামে কিউবগুলো নিয়ে সফলভাবে গড়ে তুলতে পারি।

সমাধানের ধাপসমূহ

• n := size of nums
• d := nums-এর এলিমেন্ট থেকে একটি ডবল-এন্ডেড কিউ (deque) বানান
• flag := True
• prev := 0
• while d is not empty:
  • first := d[0]
  • last := d[-1]
  • যদি prev != 0 এবং (first > prev অথবা last > prev), তবে flag := False এবং লুপ থেকে বের হোন
  • যদি first >= last, তবে prev := d.popleft()
  • অন্যথায় prev := d.pop()
• যদি flag true হয়, তবে True রিটার্ন করুন, অন্যথায় False

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বুঝার জন্য:

from collections import deque

def solve(nums):
    n = len(nums)
    d = deque(nums)
    flag = True
    prev = 0
    while d:
        first = d[0]
        last = d[-1]
        if prev != 0 and (first > prev or last > prev):
            flag = False
            break
        if first >= last:
            prev = d.popleft()
        else:
            prev = d.pop()
    if flag:
        return True
    else:
        return False

nums = [1,2,3,7,8]
print(solve(nums))

ইনপুট

[1,2,3,7,8]

আউটপুট

True