Bạn đang tìm một vị trí trong đất để đặt chú giun cưng Maximus. Bạn giới hạn việc tìm kiếm trong một vùng hình hộp có kích thước \(N \times M \times K\) xentimét, được chia thành một lưới ba chiều gồm các ô lập phương có thể tích một xentimét khối. Mỗi ô có tọa độ \((x,y,z)\) với \(1 \le x \le N\), \(1 \le y \le M\), \(1 \le z \le K\). Độ ẩm \(H[x,y,z]\) là một số nguyên từ \(1\) đến \(10^9\).

Maximus thích những nơi ẩm ướt. Hãy tìm một ô có độ ẩm không nhỏ hơn độ ẩm của cả sáu ô kề nó theo các trục, để chú không bò đi. Chính xác hơn, cần tìm một ô \((x,y,z)\) sao cho

Độ ẩm ngoài hình hộp được xem là \(0\). Độ ẩm trong hộp cố định từ trước và không phụ thuộc vào các phép đo. Bạn chỉ được đo độ ẩm nhiều nhất \(Q\) lần.

Giao diện lập trình

Phiên bản này sử dụng giao diện hàm C++17. Tải tệp đính kèm worm.h, khai báo #include "worm.h" và cài đặt hàm sau; không viết main:

struct WormPosition { int x, y, z; };  // Đã được định nghĩa trong worm.h.
WormPosition find_worm(int N, int M, int K, int Q);

Trình chấm gọi hàm một lần cho mỗi bộ dữ liệu. Ba tham số đầu là kích thước hình hộp, còn \(Q\) là số phép đo tối đa. Hàm trả về tọa độ đánh số từ 1 của một ô thỏa mãn điều kiện trên. Trả về kết quả không tốn truy vấn; ô kết quả không bắt buộc phải được đo trước đó.

Trình chấm cung cấp hàm sau trong worm.h:

int measure(int x, int y, int z);

Hàm trả về \(H[x,y,z]\). Mỗi lời gọi đều tính một truy vấn, kể cả khi hỏi lại cùng một ô. Tọa độ phải nằm trong hộp. Một lời gọi không hợp lệ hoặc vượt quá \(Q\) truy vấn làm bộ dữ liệu bị chấm sai ngay lập tức. Chương trình không cần xử lý giá trị -1 hay flush như giao thức tương tác cũ.

Chỉ dùng một luồng, phép tính và bộ nhớ C++ thông thường. Không đọc/ghi đầu vào/đầu ra, mở tệp, tạo tiến trình hoặc kiểm tra hệ thống. Chỉ gọi measure trong quá trình thực hiện find_worm, không gọi từ hàm khởi tạo biến toàn cục. Chi tiết và chương trình minh họa có trong tệp đính kèm API.md.

Ràng buộc

• \(N\), \(M\), \(K\), \(Q\) là số nguyên dương, với giá trị cụ thể theo từng nhóm bên dưới.
• \(1 \le H[x,y,z] \le 10^9\) trong hình hộp; ngoài hộp có độ ẩm bằng \(0\).
• Mọi tọa độ truyền cho measure và tọa độ trả về đều phải nằm trong hình hộp.
• Được gọi measure nhiều nhất \(Q\) lần.

Phân nhóm

Mỗi nhóm chỉ có điểm khi tất cả các bộ dữ liệu trong nhóm đều đúng. Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (10 điểm): \(M=K=1\), \(N=1\,000\,000\), \(Q=10\,000\).
• Nhóm 2 (22 điểm): \(M=K=1\), \(N=1\,000\,000\), \(Q=35\).
• Nhóm 3 (12 điểm): \(K=1\), \(N=M=200\), \(Q=4\,000\).
• Nhóm 4 (19 điểm): \(K=1\), \(N=M=1\,000\), \(Q=3\,500\).
• Nhóm 5 (14 điểm): \(N=M=K=100\), \(Q=100\,000\).
• Nhóm 6 (23 điểm): \(N=M=K=500\), \(Q=150\,000\).

Ví dụ

measure(3, 1, 1) trả về 13
measure(2, 1, 1) trả về 14
measure(1, 1, 1) trả về 10
find_worm trả về {2, 1, 1}

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ nhất.