Chiếm đất trên sao Hỏa
Đề bài
Mô tả
Năm 2030, Elon Sumk và Jeff Sozeb hạ cánh thành công xuống sao Hỏa. Cả hai cùng chọn một vùng đất bằng phẳng để hạ cánh tàu vũ trụ. Vùng đất này có thể mô hình hóa thành một bảng hình chữ nhật gồm hàng và cột. Các hàng được đánh số từ đến theo hướng từ Bắc xuống Nam, các cột được đánh số từ đến theo hướng từ Tây sang Đông. Ô ở hàng thứ và cột thứ được ký hiệu là .
Elon Sumk hạ cánh tại ô , Jeff Sozeb hạ cánh tại ô . Sau khi hạ cánh thành công, họ bắt đầu chiếm thêm đất. Do công nghệ còn hạn chế, họ chỉ có thể chiếm đất bên trong vùng đất hình chữ nhật này. Trên sao Hỏa, người ta dùng khoảng cách Manhattan để đo khoảng cách giữa các ô.
Elon Sumk và Jeff Sozeb thống nhất chiếm các ô đất theo quy tắc sau:
- Nếu một ô gần vị trí hạ cánh của Elon Sumk hơn hẳn so với vị trí hạ cánh của Jeff Sozeb, ô đó thuộc về Elon Sumk.
- Nếu một ô gần vị trí hạ cánh của Jeff Sozeb hơn hẳn so với vị trí hạ cánh của Elon Sumk, ô đó thuộc về Jeff Sozeb.
- Nếu khoảng cách từ một ô đến hai vị trí hạ cánh bằng nhau, không ai chiếm ô đó.
Trong bài toán này, bạn được cho kích thước vùng đất và , số ô thuộc về Elon Sumk là và số ô thuộc về Jeff Sozeb là . Nhiệm vụ của bạn là xác định vị trí hạ cánh của hai người.
Nhắc lại, khoảng cách Manhattan giữa hai ô và là .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số bộ test. Tiếp theo là bộ test, mỗi bộ test nằm trên một dòng gồm bốn số nguyên dương , , và (, ).
Dữ liệu vào đảm bảo tổng trên mọi bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra trên một dòng bốn số nguyên , , và là vị trí hạ cánh của Elon Sumk và Jeff Sozeb, hoặc in -1 -1 -1 -1 nếu không có lời giải.
Nếu có nhiều lời giải, in ra một lời giải bất kỳ.
Ràng buộc
- .
- là số nguyên dương, .
- Tổng trên mọi bộ test không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 3 3 3 3 |
3 3 1 1 | Elon Sumk hạ cánh ở góc , Jeff Sozeb ở góc . Elon Sumk chiếm ô , , ; Jeff Sozeb chiếm ô , , ; ô trên đường chéo , , không thuộc về ai. |
| 4 2 2 1 1 2 2 3 1 1 5 2 3 3 4 2 7 |
1 1 2 2 -1 -1 -1 -1 1 2 1 3 -1 -1 -1 -1 |
Ví dụ này không có trong đề gốc. Ở bộ test thứ nhất, hai người hạ cánh ở hai góc đối nhau, mỗi người chiếm đúng ô của mình, hai ô còn lại không thuộc về ai. Ở bộ test thứ ba, Elon Sumk chiếm các cột , Jeff Sozeb chiếm các cột . |
Bình luận