Thiết bị quét mới
Đề bài
Mô tả
Trong vai trò đóng góp cho Đại chiến Bong Bóng, bạn được giao nhiệm vụ tìm ra pháo đài mới xây của đối phương. Thế giới bạn sống là một lưới khổng lồ kích thước , các hàng đánh số từ đến từ trên xuống dưới, các cột đánh số từ đến từ trái sang phải. Ô ở hàng , cột gọi là ô .
Bạn biết căn cứ của đối phương có dạng một hình chữ nhật với các cạnh song song với các cạnh của lưới. Để giúp bạn định vị căn cứ, bạn được phát một thiết bị mới có thể quét một hình chữ nhật bất kỳ của lưới và cho biết diện tích phần chung giữa vùng quét và căn cứ.
Không may, thiết bị chạy bằng pin và bạn không thể sạc lại. Điều đó có nghĩa là bạn chỉ có thể dùng thiết bị tối đa lần.
Tương tác
Đây là bài toán tương tác. Chương trình của bạn có thể quét hình chữ nhật có ô góc trên trái là và ô góc dưới phải là bằng cách in ra một dòng "? " (, ). Bạn sẽ nhận lại diện tích phần chung của hình chữ nhật đó với căn cứ của đối phương, hoặc nếu truy vấn không hợp lệ.
Nếu nhận được , hãy kết thúc chương trình ngay lập tức và bạn sẽ nhận kết quả sai. Nếu không, bạn có thể nhận một kết quả bất kỳ vì chương trình sẽ tiếp tục đọc từ một luồng đã đóng. Chương trình của bạn được dùng không quá truy vấn.
Khi đã chắc chắn vị trí căn cứ của đối phương, hãy in ra "! " (, ), trong đó là ô góc trên trái và là ô góc dưới phải của căn cứ.
Sau mỗi dòng in ra, nhớ đẩy bộ đệm đầu ra (ví dụ cout << endl hoặc fflush(stdout) trong C++, print(..., flush=True) trong Python).
Ràng buộc
- Lưới có kích thước .
- Căn cứ là một hình chữ nhật cố định, không thay đổi trong quá trình tương tác.
- Được dùng tối đa truy vấn.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 0 0 |
? 1 1 5 5 ? 2 2 4 4 ? 2 2 4 2 ? 2 2 2 4 ! 3 3 4 4 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Căn cứ là hình vuông từ ô tới ô . |
| 1 | ? 1 1 1 1 ! 1 1 1 1 |
Ví dụ bổ sung (không có trong đề gốc). Căn cứ chỉ gồm ô : quét đúng ô đó được diện tích . |
Bình luận