Chương trình Python kiểm tra người chơi đầu tiên thắng game đạt target

Game 2 người: Amal và Bimal. Mỗi lượt chọn số 1..k cộng vào tổng (bắt đầu 0). Ai làm tổng ≥ target thắng. Amal đi trước. Kiểm tra Amal có thể bắt buộc thắng (force win) nếu cả hai chơi tối ưu.

Ví dụ

k=5, target=10 → True

Amal chọn 4. Bimal chọn 1..5 → tổng 5..9. Amal chọn 5 → tổng 10..14 ≥ 10 thắng.

Phân tích toán học

Đây là game Nim-like / Subtraction game. Vị trí thắng/thua tuân theo pattern chu kỳ k+1.

• Nếu target % (k+1) != 0: Người đầu tiên thắng (chọn target % (k+1) đầu tiên).
• Nếu target % (k+1) == 0: Người đầu tiên thua (bất kể chọn gì, đối phương luôn phản ứng về bội số của k+1).

Code Python

def solve(k, target):
    return target % (k + 1) != 0

# Test
print(solve(5, 10))   # True  (10 % 6 = 4 != 0)
print(solve(5, 12))   # False (12 % 6 = 0)
print(solve(3, 7))    # True  (7 % 4 = 3)
print(solve(3, 8))    # False (8 % 4 = 0)

Chiến lược thắng

Nếu target % (k+1) = r != 0:

1. Lượt 1: Amal chọn r.
2. Mỗi lượt sau: Nếu Bimal chọn x, Amal chọn k+1-x.
3. Mỗi cặp lượt cộng k+1. Tổng sau lượt Amal luôn ≡ r (mod k+1).
4. Cuối cùng Amal đạt target.

Độ phức tạp

• Thời gian: O(1)
• Không gian: O(1)

Cực kỳ hiệu quả - không cần DP hay recursion.