Chương trình kiểm tra Amal có thắng trò chơi đá không trong Python

Amal và Bimal chơi game, Amal đi trước. n viên đá. Mỗi lượt lấy số đá = số chính phương (1,4,9,16...). Không lấy được thì thua. Kiểm tra Amal có thắng không với n cho trước.

Ví dụ: n = 21, đầu ra = True (Amal lấy 16, Bimal lấy 4, Amal lấy 1 thắng).

Giải pháp

DP game theory (trạng thái thắng/thua):

• Tạo danh sách squares: 1, 4, 9, 16... ≤ n (+1 số lớn hơn n)
• dp[k] = True nếu người chơi hiện tại thắng với k viên đá
• dp[0] = False
• Với k từ 1 đến n:
  • dp[k] = False
  • Với mỗi square s ≤ k: nếu dp[k-s] == False: dp[k] = True; break
• Trả về dp[n]

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

21

Đầu ra

True