โปรแกรมตรวจสอบว่า Amal ชนะเกมหินได้หรือไม่ใน Python

สมมติว่ามีผู้เล่นสองคน Amal และ Bimal เล่นเกมกัน และ Amal เริ่มก่อน เริ่มต้นมี n หินที่แตกต่างกันในกอง ในแต่ละเทิร์น ผู้เล่นจะลบหินจำนวนที่เป็นจำนวนกำลังสอง (ไม่เป็นศูนย์) ออกจากกอง หากผู้เล่นคนใดไม่สามารถทำการเคลื่อนไหวได้ เขาก็แพ้เกม ดังนั้นถ้าเรามี n เราต้องตรวจสอบว่า Amal สามารถชนะเกมได้หรือไม่

เช่น ถ้าอินพุตคือ n = 21 ผลลัพธ์จะเป็น True เพราะ Amal สามารถเอา 16 ก่อน แล้ว Bimal เอา 4 แล้ว Amal เอา 1 และชนะเกม

วิธีแก้ปัญหา

squares := รายการใหม่
square := 1, increase := 3
while square <= n:
- เพิ่ม square ลงท้าย squares
- square := square + increase
- increase := increase + 2
เพิ่ม square ลงท้าย squares
dp := รายการว่างขนาด (n + 1)
dp[0] := False
สำหรับ k ในช่วง 1 ถึง n:
- s := 0, dp[k] := False
- while squares[s] <= k และ dp[k] ว่าง:
  - ถ้า dp[k - squares[s]] ว่าง: dp[k] := True
  - s := s + 1
return องค์ประกอบสุดท้ายของ dp

ตัวอย่าง

def solve(n):
    squares = []
    square = 1
    increase = 3
    while square <= n:
        squares.append(square)
        square += increase
        increase += 2
    squares.append(square)
    dp = [None] * (n + 1)
    dp[0] = False
    for k in range(1, n + 1):
        s = 0
        dp[k] = False
        while squares[s] <= k and not dp[k]:
            if not dp[k - squares[s]]:
                dp[k] = True
            s += 1
    return dp[-1]

n = 21
print(solve(n))

อินพุต

เอาต์พุต

True