โปรแกรมนับวิธีทำหมากรุกแรกเพื่อให้ผู้เริ่มต้นชนะในเกมช็อกโกแลตใน Python

อมลและบิมลเล่นเกม: มี n ภาชนะ แต่ละอันมีช็อกโกแลต count[i] เม็ด สลับกันเลือกภาชนะและหยิบช็อกโกแลต 1 เม็ดขึ้นไป ผู้ที่ไม่สามารถหยิบได้แพ้ อมลเล่นก่อน หาจำนวนวิธีที่อมลสามารถทำหมากรุกแรกได้เพื่อให้ชนะแน่นอน

ตัวอย่าง: count=[2,3] → ผลลัพธ์ 1 (หยิบ 1 เม็ดจากภาชนะที่ 2)

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

เป็นเกม Nim แบบคลาสสิก: คำนวณ XOR ของทุก count (nim-sum)

1. คำนวณ tmp = XOR ของทั้งหมดใน count
2. หาก tmp == 0 → ผู้เล่นคนแรกแพ้แน่นอน คืนค่า 0
3. มิฉะนั้น นับจำนวนภาชนะที่ (tmp XOR count[i]) < count[i] ซึ่งเป็นจำนวนวิธีที่ทำให้ nim-sum กลายเป็น 0

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

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

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

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

[2, 3]

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

1