มีเซต {1..n} อมลและบิมลสลับกันเลือกจำนวนเฉพาะ p จากเซต แล้วเอา p และพหุคูณของ p ออก ผู้ที่ไม่สามารถเลือกได้แพ้ อมลเล่นก่อน หาผู้ชนะ
ตัวอย่าง: n=5 → ผลลัพธ์ Amal
ขั้นตอนการแก้ปัญหา
จำนวนการเคลื่อนไหวเท่ากับจำนวนจำนวนเฉพาะ ≤ n หากจำนวนเฉพาะเป็นคี่ อมลชนะ (เพราะเล่นก่อน) มิฉะนั้นบิมลชนะ ใช้ Sieve of Eratosthenes นับจำนวนเฉพาะ
ตัวอย่างโค้ด Python
MAX = 100000
primes = [0] * (MAX + 1)
sieve = [0] * (MAX + 1)
for i in range(2, MAX):
if sieve[i] == 0:
primes[i] = primes[i-1] + 1
for j in range(i, MAX+1, i):
sieve[j] = i
else:
primes[i] = primes[i-1]
def solve(n):
return "Bimal" if primes[n] % 2 == 0 else "Amal"
# ทดสอบ
n = 5
print(solve(n)) # ผลลัพธ์: Amal
อินพุตตัวอย่าง
5
เอาต์พุตตัวอย่าง
Amal
