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