COVUA3 - Bàn cờ vua 3
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

Thì ra món quà trong hộp quà bị khóa bởi ổ khóa to bự lần trước mà An nhận được lại là một bàn cờ. Bàn cờ có kích thước NxM được sơn màu xen kẻ trắng và đen (ô trên trái luôn được sơn màu trắng) giống bàn cờ vua. Nhưng bàn cờ này lại không dùng để chơi cờ, mà bản thân nó đã là một trò chơi. Khi chơi, bạn có thể chọn ra một hình chứ nhật con bất kì trong bàn cờ, giới hạn ô trên trái là (x1, y1), ô dưới phải là (x2, y2) (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M), sau đó thực hiện việc đổi màu cho hình chữ nhật đó: trắng thành đen và đen thành trắng, trò chơi kết thúc khi tất cả các ô trên bàn cờ đều cùng màu.

Rất thích thú với trò chơi mới lạ này, An bắt đầu mày mò nhưng vẫn không biết làm thế nào để có thể chơi tối ưu nên đã nhờ bạn giúp đỡ. Nhưng An là một người rất tự cao, cậu ta chỉ muốn bạn nói ra số bước đi của cách chơi tối ưu nhất để có thể so sánh xem cách chơi của cậu ta là tối ưu hay chưa mà thôi. Hãy giúp cậu ta nhé.

Dữ liệu nhập: dòng đầu tiên chứa mốt số nguyên T - số lượng test case (T ≤ 1000). T dòng tiếp theo, mỗi dòng chứa 2 số nguyên N, M là kích thước của bàn cờ (1 ≤ N, M ≤109).

Dữ liệu xuất: gồm T dòng, mỗi dòng chứa một số nguyên duy nhất là kết quả tìm được của bộ test tương ứng.

Ví dụ

  • input
    1
    2 2
    output
    2

Có 2 cách chơi với số bước đi là 2:

  • Cách 1: lần lượt chọn 2 ô (1, 1) và (2, 2), chuyển từ trắng sang đen thì sẽ được toàn bộ là màu đen
  • Cách 2: lần lượt chọn 2 ô (2, 2) và (1, 1), chuyển từ đen sang trắng thì sẽ được toàn bộ là màu trắng.
Back to Top