পাইথনে চকলেট গেমে আমল প্রথম মুভে কতভাবে জেতে পারে তা বের করা

আমল এবং বিমল একটি গেম খেলছে। n কন্টেইনার আছে যাতে চকলেট। আমল প্রথম খেলে। প্রতিটি টার্নে একজন প্লেয়ার একটি নন-এমপ্টি কন্টেইনার থেকে এক বা একাধিক চকলেট নেয়। যিনি চকলেট নিতে পারবেন না সে হারবে। আমল প্রথম মুভে কতভাবে খেললে সে নিশ্চিত জেতবে তা বের করতে হবে।

উদাহরণ

ইনপুট: count = [2, 3]

আউটপুট: 1

আমল দ্বিতীয় কন্টেইনার থেকে ১টি চকলেট নিলে [2, 2] হয়। এরপর বিমল যাই করুক, আমল জেতে পারে।

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

এটি নিম (Nim) গেম। XOR-সাম (Nim-sum) ব্যবহার করে:

1. tmp := 0
2. প্রতিটি c in count: tmp ^= c
3. যদি tmp == 0: রিটার্ন ০ (আমল হारेगा)।
4. অন্যথায়: moves := 0; প্রতিটি c এর জন্য যদি (tmp ^ c) < c হয় তবে moves++।
5. moves রিটার্ন করুন।

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

def solve(count):
    tmp = 0
    for c in count:
        tmp ^= c
    if not tmp:
        return 0
    else:
        moves = 0
        for c in count:
            moves += (tmp ^ c) < c
        return moves

# টেস্ট
count = [2, 3]
print(solve(count))  # আউটপুট: 1

ইনপুট

[2, 3]

আউটপুট

1