มีหอคอยความสูงต่างกัน อมลและบิมลสลับกันเลือกหอคอยสูง X แล้วแยกเป็น Y หอคอยสูง Z (Y*Z=X, Y,Z>1) ผู้ที่ไม่สามารถแยกได้แพ้ อมลเล่นก่อน หาผู้ชนะ
ตัวอย่าง: height=[3,1,2] → ผลลัพธ์ Bimal
ขั้นตอนการแก้ปัญหา
ใช้ทฤษฎี Sprague-Grundy คำนวณ Grundy number สำหรับแต่ละความสูง:
- คำนวณ Grundy สำหรับความสูง 1..limit (limit=1000+5) โดยพิจารณาตัวหารคี่
- XOR Grundy ของทุกหอคอย หากผลลัพธ์ != 0 อมลชนะ มิฉะนั้นบิมลชนะ
ตัวอย่างโค้ด Python
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])
g = 0
while g in s:
g += 1
result[i] = g
return result
g = util()
def solve(height):
r = 0
for h in height:
r ^= g[h]
return "Amal" if r else "Bimal"
# ทดสอบ
height = [3, 1, 2]
print(solve(height)) # ผลลัพธ์: Bimal
อินพุตตัวอย่าง
[3,1,2]
เอาต์พุตตัวอย่าง
Bimal
