ডাকাত চেক করার প্রোগ্রাম পাইথনে ভল্ট ডাকাতি করতে পারে কি না

ধরুন N সংখ্যক ডাকাত একটি ভল্ট ডাকাতির চেষ্টা করছে। সেখানে একজন গার্ড ছিল কিন্তু তিনি জি পরিমাণ সময় জন্য বাইরে গিয়েছিলেন, তারপর তিনি ফিরে আসবেন. এবং প্রতিটি ডাকাতের ভল্ট ডাকাতির জন্য নির্দিষ্ট সময় থাকে, তবে তাদের মধ্যে সর্বাধিক দুজন একই সময়ে ভল্টে প্রবেশ করতে পারে। এখন সমস্যা হল আমাদের খতিয়ে দেখতে হবে তারা গার্ডের হাতে ধরা পড়ে ভল্ট ডাকাতি করতে পারে কি না? আমাদের মনে রাখতে হবে যে −

• যদি একবারে একজন ডাকাত ভল্টের ভিতরে যায় এবং একই সময়ে অন্য ডাকাত বেরিয়ে আসে, তাহলে মনে হয় তারা একই সময়ে ভল্টে ছিল না।

• গার্ড যদি G সময়ে ভল্টের ভিতরে প্রবেশ করে এবং ঠিক G সময়ে একজন ডাকাত বেরিয়ে আসে, তাহলে গার্ড ডাকাতকে লক্ষ্য করবে না৷

সুতরাং, যদি ইনপুটটি N =3 G =5 সময় =[3,5,2] এর মত হয়, তাহলে আউটপুট হবে True, কারণ সম্ভাব্য বিন্যাস সেখানে রয়েছে, অর্থাৎ −

• t=0 এ, ডাকাত1 ভিতরে যায় এবং t=3 এ বেরিয়ে আসে
• t=0 এ, ডাকাত2 ভিতরে যায় এবং t=5 এ বেরিয়ে আসে
• t=3 এ, ডাকাত3 ভিতরে যায় এবং t=5 এ বেরিয়ে আসে

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

• যদি সময়ে সমস্ত উপাদানের যোগফল> 2*G হয়, তাহলে
  • মিথ্যে ফেরত দিন
• অন্যথায় যখন সময়ে সমস্ত উপাদানের যোগফল <=G, তারপর
  • সত্য ফেরান
• অন্যথায়,
  • বৈধ :=G + 1 আকারের একটি অ্যারে, এবং প্রাথমিকভাবে সমস্ত মান মিথ্যা
  • বৈধ[0] :=সত্য
  • সময়ে প্রতিটি x এর জন্য, করুন
    • আমি G থেকে 0 রেঞ্জের জন্য, 1 কমিয়ে
      করুন
      • যদি i-x>=0 এবং বৈধ[i-x], তাহলে
        • বৈধ[i] :=সত্য
  • যদি সময়ের মধ্যে সমস্ত উপাদানের যোগফল - 0 রেঞ্জের সমস্ত i-এর জন্য সর্বাধিক i যখন বৈধ হয় তখন বৈধের আকার হয়[i] <=G, তারপর
    • সত্য ফেরান
  • অন্যথায়,
    • মিথ্যে ফেরত দিন

উদাহরণ

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

def সমাধান(N, G, time):if sum(time)> 2*G:রিটার্ন False elif sum(time) <=G:return True else:valid =[False]*(G+1) বৈধ [0] =সময় x-এর জন্য সত্য:সীমার মধ্যে i (G,-1,-1):যদি i-x>=0 এবং বৈধ[i-x]:বৈধ[i] =সঠিক হলে যোগফল(সময়) - সর্বোচ্চ(i i এর জন্য রেঞ্জে(len(valid)) যদি বৈধ[i]) <=G:return True else:return FalseN =3G =5time =[3,5,2]print(solve(N, G, time)) 
ইনপুট
 
3,5,[3,5,2]
 
আউটপুট
 
সত্য