Xác định người thắng trò chơi giảm số theo lũy thừa 2 trong Python

Amal và Bimal chơi với số n. Nếu n là lũy thừa của 2, chia cho 2. Ngược lại, trừ đi lũy thừa 2 lớn nhất nhỏ hơn n. Người làm n=1 thắng. Amal đi trước. Tìm người thắng.

Ví dụ: n=19 → Amal thắng.

Giải thuật

• Đếm số lượt (res) cho đến khi n=1:
  • Tìm b = lũy thừa 2 lớn nhất < n.
  • n = n - b (nếu n không phải lũy thừa 2) hoặc n = n/2 (nếu n là lũy thừa 2).
  • res++.
• Nếu res chẵn → Amal thắng, lẻ → Bimal thắng.

Ví dụ mã Python

def solve(n):
    res = 0
    while n > 1:
        b = 1
        while b * 2 < n:
            b *= 2
        n -= b
        res += 1
    return 'Amal' if res % 2 == 0 else 'Bimal'

n = 19
print(solve(n))  # Output: Amal

Đầu vào

19

Đầu ra

Amal