সকলে পাইথনে আসন পেতে পারে কি না তা পরীক্ষা করার জন্য প্রোগ্রাম

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

সুতরাং, যদি ইনপুট n =2 আসন =[1, 0, 0, 0, 1, 0, 0] এর মত হয়, তাহলে আউটপুট হবে True, কারণ তারা সূচী 2 এবং 6-এ বসতে পারে।

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

• সিটের শুরুতে 0 ঢোকান এবং সিটের শেষে [0, 1] ঢোকান
• res :=0, gap :=0
• প্রতিটি i আসনের জন্য, করুন
  • যদি আমি 0 এর মত হয়, তাহলে
    • ব্যবধান :=ফাঁক + 1
  • অন্যথায় যখন ফাঁক> 0, তারপর
    • res :=res + ফ্লোর অফ (গ্যাপ - 1)/2
    • ব্যবধান :=0
• সত্য প্রত্যাবর্তন করুন যখন res>=n অন্যথায় মিথ্যা

উদাহরণ

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

def solve(n, seats):
   seats = [0] + seats + [0, 1]
   res = 0
   gap = 0
   for i in seats:
      if i == 0:
         gap += 1
      elif gap > 0:
         res += (gap - 1) // 2
         gap = 0
   return res >= n

n = 2
seats = [1, 0, 0, 0, 1, 0, 0]
print(solve(n, seats))

ইনপুট

2, [1, 0, 0, 0, 1, 0, 0]

আউটপুট

True