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

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

• আমল প্রথম খেলে।
• প্রতিটি মুভে একটি টাওয়ার উচ্চতা X বেছে নিয়ে Y-এ কমানো হবে (1 ≤ Y < X; Y, X-কে বিভাজ্য করে)।
• যিনি মুভ দিতে পারবেন না সে হাবে।

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

উদাহরণ

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

আউটপুট: Bimal

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

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

1. প্রতিটি টাওয়ারের হাইটকে প্রাইম ফ্যাক্টরাইজ করুন। মোট প্রাইম ফ্যাক্টরের সংখ্যা (with multiplicity) = গ্রান্ডি নম্বর।
2. সব গ্রান্ডি নম্বর XOR করুন।
3. XOR ≠ 0 হলে "Amal", অন্যথায় "Bimal"।

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

def util(a, n):
    ans = 0
    for i in range(n):
        ans ^= a[i]
    return ans

def solve(height):
    n = len(height)
    b = [0] * n
    for i in range(n):
        if height[i] == 1:
            b[i] = 0
        else:
            b[i] = 0
            j = 2
            root = int(height[i]**0.5)
            while height[i] != 1 and j <= root:
                if height[i] % j == 0:
                    while height[i] % j == 0:
                        b[i] += 1
                        height[i] //= j
                j += 1
            if height[i] != 1:
                b[i] += 1
    ans = util(b, n)
    return "Amal" if ans != 0 else "Bimal"

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

ইনপুট

[3,1,2]

আউটপুট

Bimal