Linda thích thỉnh thoảng đổi màu tóc và mong bạn trai Archie nhận ra sự khác biệt giữa màu tóc cũ và màu tóc mới. Archie nhận xét về màu tóc của Linda khi và chỉ khi anh nhận thấy sự khác biệt, nên Linda luôn biết liệu Archie có nhận ra việc đổi màu tóc hay không.

Trên thị trường vừa xuất hiện một dòng thuốc nhuộm tóc mới, trong đó các màu được đánh số bằng các số nguyên từ \(1\) đến \(N\). Chênh lệch giữa các số càng nhỏ thì sự khác biệt về màu sắc nhìn bằng mắt cũng càng nhỏ.

Linda giả thiết rằng với dòng thuốc nhuộm này, tồn tại một ngưỡng chênh lệch màu \(C\) (\(1\le C\le N\)): Archie nhận ra sự khác biệt giữa màu hiện tại \(\mathrm{color}_{\mathrm{new}}\) và màu trước đó \(\mathrm{color}_{\mathrm{prev}}\) nếu \(|\mathrm{color}_{\mathrm{new}}-\mathrm{color}_{\mathrm{prev}}|\ge C\), và không nhận ra nếu \(|\mathrm{color}_{\mathrm{new}}-\mathrm{color}_{\mathrm{prev}}|<C\).

Linda đã mua \(N\) bộ thuốc nhuộm thuộc dòng mới, mỗi màu từ \(1\) đến \(N\) có đúng một bộ, và sẵn sàng tiến hành thí nghiệm. Cô sẽ đổi màu tóc định kỳ và quan sát xem Archie có nhận ra hay không. Vì mỗi lần nhuộm phải dùng hết một bộ thuốc nhuộm để đạt được màu mong muốn, mỗi màu chỉ có thể được sử dụng nhiều nhất một lần.

Trước thí nghiệm, Linda dùng thuốc nhuộm thuộc một dòng khác, không tương thích với dòng mới. Vì vậy, phản ứng của Archie đối với màu đầu tiên được dùng trong thí nghiệm không có ý nghĩa.

Linda muốn xác định chính xác \(C\) với số lần nhuộm có giới hạn. Hãy viết chương trình tìm \(C\) bằng cách thử các màu trong \(N\) màu đã cho và quan sát phản ứng của Archie trước mỗi lần đổi màu tóc.

Yêu cầu cài đặt

Đây là bản điều chỉnh của bài tương tác Colors, sử dụng giao diện hàm C++ chạy trong cùng tiến trình với trình chấm. Nộp một tệp C++17 hoặc C++20, có #include "colors.h", hiện thực hàm sau và không viết hàm main:

long long find_threshold(long long N);

Trình chấm gọi find_threshold(N) đúng một lần cho mỗi bộ dữ liệu. Hàm chỉ nhận \(N\); giá trị \(C\) được giữ bí mật. Hàm phải trả về chính xác \(C\). Việc trả về kết thúc quá trình tìm kiếm, không tính là một truy vấn và không có phản hồi hay truy vấn tiếp theo.

Tệp colors.h cũng khai báo hàm do trình chấm cung cấp:

int query(long long P);

Mỗi lần gọi query(P) chọn màu tiếp theo, với \(1\le P\le N\). Hàm trả về 1 nếu Archie nhận ra sự khác biệt giữa hai màu được sử dụng gần nhất, hoặc 0 nếu không. Từ lần gọi thứ hai, phản hồi là 1 khi chênh lệch tuyệt đối giữa màu mới và màu ngay trước đó lớn hơn hoặc bằng \(C\), và là 0 khi chênh lệch nhỏ hơn \(C\).

Phản hồi của lần gọi đầu tiên không có ý nghĩa và có thể là 0 hoặc 1; lời giải phải hoạt động đúng với cả hai khả năng. Không được gọi với cùng một giá trị \(P\) hai lần. Được gọi query nhiều nhất \(64\) lần, tính cả lần đầu tiên, trong mọi phân nhóm.

Dùng kiểu long long cho \(N\), \(P\) và giá trị trả về \(C\). Bài nộp không đọc đầu vào chuẩn (stdin), không ghi đầu ra chuẩn (stdout) và không cần đẩy bộ đệm đầu ra (flush). Việc trả về đúng \(C\) không xóa các vi phạm trước đó: màu ngoài miền, màu lặp hoặc vượt quá giới hạn truy vấn vẫn khiến bài nộp không được chấp nhận.

Tệp đính kèm và chạy thử

Gói công khai boi20colors.zip gồm colors.h, public_grader.cpp, README.vi.md, sample.in và example.cpp. example.cpp chỉ là khung cần hoàn thiện, không phải lời giải. Viết lời giải vào solution.cpp và biên dịch cùng trình chạy thử công khai:

g++ -std=c++17 -O2 solution.cpp public_grader.cpp -o colors
./colors < sample.in
./colors 0 < sample.in
./colors 1 < sample.in

Trình chạy thử đọc một dòng N C từ tệp do bạn cung cấp; sample.in chứa 7 4. Chỉ trình chạy thử đọc dòng này, rồi gọi find_threshold(N). Hai lệnh cuối buộc phản hồi đầu tiên lần lượt là 0 và 1.

Nếu đáp án đúng và không có vi phạm, trình chạy thử in Accepted ra đầu ra chuẩn, in số truy vấn theo dạng <số truy vấn> queries ra đầu ra lỗi chuẩn (stderr) và kết thúc với mã \(0\). Nếu đáp án sai, lặp màu hoặc quá \(64\) truy vấn, trình chạy thử in Wrong Answer ra đầu ra chuẩn và kết thúc với mã \(1\). Một màu ngoài miền khiến trình chạy thử in Invalid query ra đầu ra lỗi chuẩn và kết thúc ngay với mã \(1\). Đây là thông báo của công cụ chạy thử; bài nộp chỉ cần trả về đáp án qua hàm.

Ràng buộc

• \(N\) và \(C\) là các số nguyên, \(1<N\le10^{18}\) và \(1\le C\le N\).
• Mỗi truy vấn dùng một số nguyên \(P\) với \(1\le P\le N\); mọi giá trị \(P\) đã truy vấn phải đôi một khác nhau.
• Chương trình được dùng nhiều nhất \(64\) lần gọi query, tính cả truy vấn đầu tiên, để tìm đúng \(C\).
• Giới hạn thời gian: \(0{,}3\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(9\) điểm: \(N\le64\).
2. \(13\) điểm: \(N\le125\).
3. \(21\) điểm: \(N\le1000\).
4. \(24\) điểm: \(N\le10^9\).
5. \(33\) điểm: không có ràng buộc thêm.

Ví dụ

Input        Output
7
             ? 2
1
             ? 7
1
             ? 4
0
             ? 1
0
             ? 5
1
             = 4

Ghi chú về giao thức gốc

Trong đề tương tác gốc, chương trình đọc \(N\), in ? P rồi đọc phản hồi cho mỗi truy vấn; khi biết đáp án thì in = C và dừng. Trình chấm không phản hồi đáp án cuối và không nhận thêm truy vấn. Bản dùng hàm thay mỗi cặp hỏi/đáp bằng query(P) và thay dòng đáp án cuối bằng giá trị trả về của find_threshold.

Đề gốc yêu cầu flush sau mỗi truy vấn và liệt kê các lệnh sau:

Trong C++, std::endl vừa in ký tự xuống dòng vừa đẩy dữ liệu trong bộ đệm ra ngoài. Những lệnh này chỉ mô tả giao thức gốc, không cần dùng trong bản nộp qua hàm.

Đề gốc lưu ý rằng vẫn có thể nhận Output isn't correct sau khi in đúng đáp án nếu đã vi phạm ràng buộc, và vi phạm giao thức có thể dẫn đến Execution killed. Trong bản dùng hàm, quy tắc tương ứng vẫn là: đáp án đúng không làm mất các vi phạm trước đó. Dữ liệu chạy thử do người dùng cung cấp trong đề gốc là một dòng N C, cũng là định dạng đầu vào của trình chạy thử công khai.