WINSTRAT - Winning Strategy

Giới hạn
  • Thời gian: 0.019s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

  • Người up: paulmcvn
  • Nguồn bài: ACM Regional, Ho Chi Minh City 2008