trang chủ / đề bài / icpc21_bt_n

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 109×109, các hàng đánh số từ 1 đến 109 từ trên xuống dưới, các cột đánh số từ 1 đến 109 từ trái sang phải. Ô ở hàng i, cột j gọi là ô (i,j).

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 66 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à (x1,y1) và ô góc dưới phải là (x2,y2) bằng cách in ra một dòng "? x1 y1 x2 y2" (1≤x1≤x2≤109, 1≤y1≤y2≤109). 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 −1 nếu truy vấn không hợp lệ.

Nếu nhận được −1, 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á 66 truy vấn.

Khi đã chắc chắn vị trí căn cứ của đối phương, hãy in ra "! x y p q" (1≤x≤p≤109, 1≤y≤q≤109), trong đó (x,y) là ô góc trên trái và (p,q) 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 109×109.
  • 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 66 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ừ ô (3,3) tới ô (4,4).
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 ô (1,1): quét đúng ô đó được diện tích 1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0