Tutorial — Bàn Cờ Logic

Hãy chú ý thứ tự ưu tiên của các phép toán logic: phép AND luôn được thực hiện trước phép OR. Điều này đồng nghĩa với việc biểu thức cuối cùng là phép OR của nhiều khối con, trong đó mỗi khối con chỉ gồm các phép AND nối tiếp nhau.

Toàn bộ biểu thức nhận giá trị đúng khi và chỉ khi có ít nhất một khối con nhận giá trị đúng, tức là khối đó chỉ gồm toàn các giá trị đúng. Vì Minh là người đi trước, hãy xem xét liệu Minh có thể cô lập ngay một giá trị đúng ở hai đầu mút hoặc bảo vệ một cặp giá trị đúng liền kề hay không.

Minh chắc chắn thắng khi và chỉ khi chuỗi bắt đầu bằng ký tự `1`, kết thúc bằng ký tự `1`, hoặc tồn tại hai ký tự `1` đứng liền kề nhau (`11`). Bạn chỉ cần duyệt qua chuỗi một lần với độ phức tạp thời gian $O(n)$ để kiểm tra các điều kiện này.