পাইথনে টাওয়ার ব্রেকিং গেমের বিজয়ী খুঁজে বের করা

height অ্যারেতে n টাওয়ারের উচ্চতা আছে। আমল এবং বিমল গেম খেলছে। নিয়ম:

• আমল প্রথম খেলে।
• প্রতিটি মুভে একটি টাওয়ার উচ্চতা X বেছে নিয়ে Yটি টাওয়ারে ভাঙতে হবে (Y*Z = X; X,Y > 1)।
• যিনি মুভ দিতে পারবেন না সে হাবে।

বিজয়ীর নাম বের করতে হবে।

উদাহরণ

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

আউটপুট: Bimal

আমল ২-কে ১,১ করে দিলে [3,1,1,1] হয়। বিমল ৩-কে ১,১,১ করলে আমলের মুভ থাকে না।

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

1. গ্রান্ডি নম্বর (Sprague-Grundy) প্রিকম্পিউট করুন util() ফাংশনে।
2. প্রতিটি উচ্চতা i এর জন্য সম্ভাব্য ভাঙন থেকে মেক্স (mex) বের করুন।
3. সব টাওয়ারের গ্রান্ডি নম্বর XOR করুন।
4. XOR ≠ 0 হলে "Amal", অন্যথায় "Bimal"।

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

def util(limit=10**3 + 5):
    result = [0] * limit
    for i in range(2, limit):
        s = set()
        for j in range(1, int(i**0.5) + 1):
            d, r = divmod(i, j)
            if r == 0:
                if j & 1:
                    s.add(result[d])
                if d & 1:
                    s.add(result[j])
        j = 0
        while j in s:
            j += 1
        result[i] = j
    return result

g = util()

def solve(height):
    r = 0
    for i in height:
        r ^= g[i]
    return "Amal" if r else "Bimal"

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

ইনপুট

[3,1,2]

আউটপুট

Bimal