Số nước đi đầu tiên để Amal thắng trò chơi lấy kẹo trong Python

Amal và Bimal chơi trò chơi Nim: n hộp kẹo, mỗi hộp có count[i] kẹo. Mỗi lượt lấy ít nhất 1 kẹo từ một hộp. Người không lấy được thua. Amal đi trước. Tìm số cách Amal lấy kẹo ở lượt đầu để đảm bảo thắng.

Ví dụ: count=[2,3] → 1 cách (lấy 1 kẹo từ hộp 2).

Giải thuật

• Tính XOR của tất cả count[i] → tmp.
• Nếu tmp == 0: Amal thua nếu đối thủ chơi tối ưu → trả về 0.
• Ngược lại: đếm số hộp mà (tmp XOR count[i]) < count[i]. Đó là số nước đi thắng.

Ví dụ mã Python

def solve(count):
    tmp = 0
    for c in count:
        tmp ^= c
    if not tmp:
        return 0
    moves = 0
    for c in count:
        moves += (tmp ^ c) < c
    return moves

count = [2, 3]
print(solve(count))  # Output: 1

Đầu vào

[2, 3]

Đầu ra

1