โปรแกรมหาผู้ชนะเกมลดความสูงหอคอยใน Python

มีหอคอยความสูงต่างกัน อมลและบิมลสลับกันเลือกหอคอยสูง X ลดความสูงเป็น Y (1 ≤ Y < X, Y หาร X ลงตัว) ผู้ที่ไม่สามารถลดได้แพ้ อมลเล่นก่อน หาผู้ชนะ

ตัวอย่าง: height=[3,1,2] → ผลลัพธ์ Bimal

ขั้นตอนการแก้ปัญหา

Grundy number ของหอคอยสูง X คือจำนวนเฉพาะในการแยกตัวประกอบของ X (นับซ้ำ) ใช้ Nim-sum:

1. แยกตัวประกอบแต่ละความสูง นับจำนวนเฉพาะ (with multiplicity) → Grundy number
2. XOR ทุก Grundy number หาก != 0 อมลชนะ มิฉะนั้นบิมลชนะ

ตัวอย่างโค้ด Python

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:
            cnt = 0
            h = height[i]
            j = 2
            root = int(h**0.5)
            while h != 1 and j <= root:
                if h % j == 0:
                    while h % j == 0:
                        cnt += 1
                        h //= j
                j += 1
            if h != 1:
                cnt += 1
            b[i] = cnt
    ans = util(b, n)
    return "Amal" if ans != 0 else "Bimal"

# ทดสอบ
height = [3, 1, 2]
print(solve(height))  # ผลลัพธ์: Bimal

อินพุตตัวอย่าง

[3,1,2]

เอาต์พุตตัวอย่าง

Bimal