পাইথনে ডাকাতরা ভল্ট লুট করতে পারবে কিনা যাচাই করা

N ডাকাত একটি ভল্ট লুট করতে চায়। গার্ড G সময় পর ফিরবে। প্রতিটি ডাকাতের নির্দিষ্ট সময় লাগে, কিন্তু একসাথে hoogsters ২ জনই ভিতরে ঢুকতে পারে। যাচাই করতে হবে কি তারা গার্ডের ফিরার আগে লুট শেষ করতে পারবে। শর্ত:

• একজন ঢুকছে এবং অন্যজন বের হচ্ছে একই সময় → একসাথে নয়।
• গার্ড G-এ ফিরলে এবং ডাকাত G-এ বের হলে → গার্ড দেখবে না।

উদাহরণ

ইনপুট: N = 3, G = 5, time = [3, 5, 2]

আউটপুট: True

ব্যয়স্থা: t=0: ডাকাত ১,২ ঢুকল; t=3: ডাকাত ১ বের, ডাকাত ৩ ঢুকল; t=5: ডাকাত ২,৩ বের।

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

1. যদি sum(time) > 2*G: False (অসম্ভব)।
2. যদি sum(time) <= G: True (সিকোয়েনশিয়ালি করা যাবে)।
3. অন্যথায় সাবসেট সাম DP (ন্যাপস্যাক) ব্যবহার করে চেক করুন:
   • valid[0..G] বুলিয়ান অ্যারে, valid[0]=True
   • প্রতিটি x in time: ulta লুপে valid[i] = True যদি valid[i-x] True হয়।
   • যদি sum(time) - max{i | valid[i]} <= G: True, অন্যথায় False।

পাইথন ইমপ্লিমেন্টেশন

def solve(N, G, time):
    if sum(time) > 2 * G:
        return False
    elif sum(time) <= G:
        return True
    else:
        valid = [False] * (G + 1)
        valid[0] = True
        for x in time:
            for i in range(G, -1, -1):
                if i - x >= 0 and valid[i - x]:
                    valid[i] = True
        max_valid = max(i for i in range(len(valid)) if valid[i])
        if sum(time) - max_valid <= G:
            return True
        else:
            return False

# টেস্ট
N = 3
G = 5
time = [3, 5, 2]
print(solve(N, G, time))  # আউটপুট: True

ইনপুট

3,5,[3,5,2]

আউটপুট

True