Lật đĩa Reversi
Đề bài
Mô tả
Reversi là một trò chơi chiến thuật trên bàn cờ dành cho hai người. Hôm nay, Bob có quân cờ (gọi là đĩa), mỗi đĩa có một mặt sáng và một mặt tối, được đánh số từ đến . Bob có một bàn cờ đủ rộng để đặt đúng đĩa trên một hàng và đủ dài để chứa hết các đĩa. Vì vậy, Bob xếp các đĩa thật ngay ngắn: các đĩa từ đến lần lượt theo thứ tự từ trái sang phải, từ trên xuống dưới (mỗi hàng đĩa, hàng cuối có thể không đầy). Sau khi xếp, mọi đĩa đều ở mặt tối.
Alice là bạn của Bob, cô yêu thích các số từ đến . Hôm nay Alice sẽ đến nhà Bob chơi. Bob muốn tạo bất ngờ cho cô nên quyết định thay đổi các đĩa đã xếp trên bàn cờ: Bob muốn các đĩa từ đến ở mặt sáng và mọi đĩa còn lại ở mặt tối. Tuy nhiên việc này rất tốn thời gian vì khá lớn, nên Bob chế tạo một robot làm thay.
Robot của Bob có thể lật cùng lúc tất cả các đĩa nằm trong một hình chữ nhật với kích thước tùy chọn. Tuy nhiên việc chọn kích thước hình chữ nhật và ra lệnh cho robot cũng rất tốn thời gian, nên Bob muốn bạn giúp điều khiển robot với số lần ít nhất mà vẫn đạt yêu cầu.
Dùng hệ tọa độ có trục hướng sang phải (theo cột) và trục hướng xuống dưới (theo hàng). Đĩa thứ nằm trong ô vuông đơn vị có góc trên trái và góc dưới phải . Ví dụ, đĩa thứ nhất nằm trong ô vuông từ đến . Một lần điều khiển robot được mô tả bởi hình chữ nhật có góc trên trái và góc dưới phải ; robot lật mọi đĩa có ô vuông nằm trong hình chữ nhật đó. Hình chữ nhật được phép phủ cả những ô không có đĩa (các ô sau đĩa ở hàng cuối).
Dữ liệu vào
Một dòng duy nhất gồm bốn số nguyên , , , (, ).
Dữ liệu ra
- Dòng đầu tiên in ra số nguyên : số lần ít nhất Bob cần điều khiển robot.
- dòng tiếp theo, mỗi dòng in ra bốn số nguyên không âm , , , mô tả góc trên trái và góc dưới phải của một hình chữ nhật, với và .
Nếu có nhiều cách tối ưu, in ra cách bất kỳ.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 15 4 3 13 | 3 2 0 4 1 0 1 4 3 0 3 1 4 |
Bàn cờ có hàng: , , , . Ba hình chữ nhật lật các đĩa ; các đĩa ; đĩa . |
| 19 4 2 19 | 2 1 0 4 1 0 1 4 5 |
Hình thứ nhất lật các đĩa . Hình thứ hai phủ các hàng , , , (kể cả ô trống sau đĩa ). |
Bình luận