Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
WINSTRAT - Winning Strategy |
English | Vietnamese |
Một bảng có n hàng đánh số từ 0 đến n-1 và n cột đánh số từ 0 đến n-1. Tọa độ của một ô thuộc hàng i và cột j là (i,j). Mỗi ô nhận giá trị 0 hoặc 1. Trong bảng này, có m ô có giá trị 0. Các ô còn lại có giá trị 1. Hai người chơi một trò chơi bằng cách luân phiên thực hiện các bước đi. Người chơi thứ nhất thực hiện bước đi đầu tiên. Mỗi người chơi chỉ được thực hiện một bước đi mỗi lượt. Người chơi đến lượt mình mà không thể thực hiện bước đi nào nữa là người thua và người chơi còn lại là người chiến thắng. Một bước đi hợp lệ là một hành động đổi giá trị (0 thành 1 hoặc 1 thành 0) của bốn ô tại bốn góc của một hình chữ nhật nằm bên trong bảng thỏa mãn các điều kiện sau:
- hình chữ nhật phải có nhiều hơn 1 hàng và nhiều hơn 1 cột,
- ô với tọa độ hàng lớn nhất và tọa độ cột lớn nhất trong bốn ô phải có giá trị là 0.
Cho trước giá trị các ô trong một bảng, nhiệm vụ của bạn là viết một chương trình giúp người chơi thứ nhất xác định xem có tồn tại chiến thuật chơi để đảm bảo anh ta luôn thắng bất kể người chơi thứ hai chơi thế nào.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.
Với mỗi bộ dữ liệu, dòng đầu tiên chứa số nguyên n (0 < n < 1000) là kích thước của bảng. Dòng tiếp theo chứa số nguyên m (0 < m <100). Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên x, y (0 ≤ x,y < n) là tọa độ của một ô có giá trị 0.
Dữ liệu ra
Với mỗi bộ dữ liệu, ghi ra trên một dòng số 1 nếu tồn tại chiến thuật thắng cho người chơi thứ nhất, hoặc số 0 trong trường hợp ngược lại.
Ví dụ
Dữ liệu vào 4 100 1 0 0 100 3 0 1 0 20 0 30 100 2 2 3 3 2 10 2 1 2 2 3 Dữ liệu ra 0 0 0 1
Được gửi lên bởi: | Jimmy |
Ngày: | 2009-01-04 |
Thời gian chạy: | 0.100s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
Nguồn bài: | ACM Regional, Ho Chi Minh City 2008 |