Trên bàn cờ \(N\times N\) có \(K\le3\) kho báu ở các ô khác nhau. Khi hỏi một ô, la bàn trả về hướng của mọi bước đầu tiên nằm trên một đường Manhattan ngắn nhất tới một kho báu gần nhất. Nếu ô có kho báu, nó trả về TREASURE. Kho báu đã tìm vẫn tồn tại và vẫn ảnh hưởng tới la bàn. Tọa độ \(y\) tăng từ trên xuống dưới.

Đây là bài tương tác. Submission C++ của bạn có một hàm main và phải dùng thư viện treasurehuntlib.h; không được đọc standard input hay ghi standard output. Chỉ được ghi thông tin gỡ lỗi vào standard error.

Giao diện thư viện

Bạn không cài đặt NextHunt hay Query. Submission cần cài đặt hàm main, include treasurehuntlib.h và gọi hai hàm do bộ chấm cung cấp.

Header cung cấp chính xác giao diện sau:

enum {
    TREASURE = 0,
    DIR_RIGHT = 1,
    DIR_UP = 2,
    DIR_LEFT = 4,
    DIR_DOWN = 8,
};

void NextHunt(int &N, int &K);
int Query(int x, int y);

Khung chương trình tối thiểu:

#include "treasurehuntlib.h"

int main() {
    while (true) {
        int N, K;
        NextHunt(N, K);
        if (N == -1)
            return 0;

        // Dùng Query(x, y) để tìm K kho báu của lần tìm kiếm này.
    }
}

Dữ liệu vào

Không có standard input cho submission. Trước mỗi lần tìm kiếm, gọi NextHunt(N,K). Nếu không còn lần tìm kiếm nào, hàm gán \(N=K=-1\); khi đó phải kết thúc với mã thoát \(0\).

Dùng Query(x,y) với \(0\le x,y<N\). Hàm trả về TREASURE=0, hoặc tổng của các cờ DIR_RIGHT=1, DIR_UP=2, DIR_LEFT=4, DIR_DOWN=8. Không được gọi Query trước NextHunt, không được gọi Query hoặc NextHunt sau khi nhận \(-1\), không dùng tọa độ ngoài phạm vi, và không được hỏi quá \(1000\) lần trong một lần tìm kiếm.

Dữ liệu ra

Không có standard output. Một kho báu được tính là đã tìm khi Query ít nhất một lần tại đúng ô của nó. Có thể gọi NextHunt sớm để chuyển sang lần tìm kiếm kế tiếp; vi phạm giao thức gây RTE và nhận \(0\) điểm cho toàn bộ phân nhóm.

Ràng buộc

• \(2\le N\le10^6\), \(1\le K\le3\).
• Mỗi tiến trình có nhiều nhất \(100\,000\) lần tìm kiếm; mỗi lần có nhiều nhất \(1000\) truy vấn.
• Bộ chấm không thích nghi.

Phân nhóm

1. \(10\) điểm: \(K=1\).
2. \(30\) điểm: \(K=2\).
3. \(60\) điểm: \(K=3\).

Với một phân nhóm tổng \(S\) điểm, tất cả các lần tìm kiếm trong phân nhóm được xét cùng nhau. Nếu luôn tìm đủ kho báu, điểm là \(S/2+(S/2)\min_i f(Q_i/\lceil\log_2 N_i\rceil)\), trong đó \(f(t)=1\) khi \(t\le11\), \(f(t)=1-(t-11)/9\) khi \(11\le t\le20\), và \(f(t)=0\) khi \(t\ge20\). Nếu có lần chưa tìm đủ, điểm là \((S/2)\min_i(F_i/K_i)\). Kết quả không nguyên được làm tròn đến số nguyên gần nhất.

Ví dụ

Nguồn

CEOI 2026 - Ngày 1, bài Treasure Hunt.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.