คำอธิบายปัญหา
เกมสองคน: Amal และ Bimal สลับกันเลือกตัวเลข 1 ถึง k บวกเข้ากับผลรวม (เริ่ม 0) ใครทำให้ผลรวม ≥ target ก่อนชนะ Amal เล่นก่อน ตรวจสอบว่า Amal บังคับชนะได้หรือไม่ (ทั้งคู่เล่นอย่างเหมาะสม)
ตัวอย่าง
k = 5, target = 10 → Output: True
Amal เลือก 4 ก่อน ไม่ว่ Bimal จะเลือก 1-5, Amal เลือก 5 ถัดไปถึง 10 ชนะ
หลักการแก้ปัญหา (คณิตศาสตร์)
นี่คือเกม Nim แบบง่าย: ตำแหน่งที่เป็น "losing position" คือตำแหน่งที่ target % (k + 1) == 0
- ถ้า
target % (k + 1) != 0→ ผู้เล่นคนแรกชนะได้ (True) - ถ้า
target % (k + 1) == 0→ ผู้เล่นคนแรกแพ้ (False)
การตนการทำงาน (Python)
def solve(k, target):
return target % (k + 1) != 0
k = 5
target = 10
print(solve(k, target)) # Output: True
อินพุต / เอาต์พุต
Input: 5, 10 Output: True
