Giải thưởng lớn là một trò chơi truyền hình nổi tiếng. Bạn là người chơi may mắn lọt vào vòng chung kết, đứng trước một dãy \(n\) hộp được đánh số từ \(0\) đến \(n-1\) theo thứ tự từ trái sang phải. Mỗi hộp chứa một giải thưởng mà bạn chưa biết cho đến khi mở hộp. Có \(v\ge 2\) loại giải thưởng, được đánh số từ \(1\) đến \(v\) theo thứ tự giá trị giảm dần.

Giải thưởng loại \(1\) có giá trị cao nhất: một viên kim cương. Có đúng một viên kim cương trong tất cả các hộp. Giải thưởng loại \(v\) có giá trị thấp nhất: một cây kẹo mút. Các giải thưởng ít giá trị hơn xuất hiện với số lượng nhiều hơn hẳn: với mọi \(2\le t\le v\), nếu có \(k\) giải thưởng loại \(t-1\), thì số giải thưởng loại \(t\) lớn hơn nghiêm ngặt \(k^2\).

Mục tiêu của bạn là giành được viên kim cương. Cuối trò chơi, bạn phải chọn mở một hộp và nhận giải thưởng trong đó. Trước khi chọn hộp, bạn được hỏi Rambod, người dẫn chương trình, một số câu hỏi. Trong mỗi câu hỏi, bạn chọn một hộp \(i\); Rambod trả lời bằng một mảng \(a\) gồm hai số nguyên:

• \(a[0]\) là số hộp ở bên trái hộp \(i\) chứa giải thưởng có giá trị lớn hơn giải thưởng trong hộp \(i\).
• \(a[1]\) là số hộp ở bên phải hộp \(i\) chứa giải thưởng có giá trị lớn hơn giải thưởng trong hộp \(i\).

Chẳng hạn, nếu \(n=8\), bạn hỏi về hộp \(i=2\) và nhận được \(a=[1,2]\), thì trong hai hộp \(0,1\) có đúng một hộp chứa giải thưởng giá trị hơn giải thưởng ở hộp \(2\); trong các hộp \(3,4,\ldots,7\) có đúng hai hộp như vậy.

Hãy tìm hộp chứa viên kim cương bằng cách sử dụng ít câu hỏi.

Chi tiết cài đặt

Đây là bài toán tương tác thông qua lời gọi hàm. Bạn cần khai báo sử dụng tệp prize.h và cài đặt hàm:

int find_best(int n);

Chương trình chấm gọi find_best đúng một lần, với n là số hộp. Hàm phải trả về nhãn \(d\) của hộp chứa viên kim cương: số nguyên duy nhất \(0\le d\le n-1\) mà hộp \(d\) chứa giải thưởng loại \(1\).

Trong quá trình thực hiện find_best, bạn có thể gọi hàm sau do chương trình chấm cung cấp:

std::vector<int> ask(int i);

• i là nhãn hộp được hỏi, phải thỏa mãn \(0\le i\le n-1\).
• Hàm trả về một mảng \(a\) có đúng hai phần tử. \(a[0]\) là số hộp bên trái \(i\) chứa giải thưởng có giá trị lớn hơn giải thưởng trong hộp \(i\); \(a[1]\) là số hộp bên phải \(i\) chứa giải thưởng có giá trị lớn hơn giải thưởng trong hộp \(i\).

Bạn chỉ cài đặt find_best; hàm ask và hàm main do chương trình chấm cung cấp. Chương trình của bạn nhận thông tin về các hộp thông qua ask và trả lời bằng giá trị trả về của find_best. Mỗi lần gọi ask đều được tính là một câu hỏi, kể cả khi hỏi lại một hộp. Không được gọi quá \(10\,000\) lần trong một bộ dữ liệu; gọi với chỉ số không hợp lệ, vượt giới hạn số câu hỏi hoặc trả về hộp không chứa kim cương sẽ bị chấm sai.

Hành vi thích nghi của chương trình chấm

Trong một số bộ dữ liệu, chương trình chấm có hành vi thích nghi: dãy giải thưởng không được cố định trước, và câu trả lời có thể phụ thuộc vào các câu hỏi mà chương trình của bạn đã đặt ra.

Sau mỗi câu trả lời, luôn tồn tại ít nhất một dãy giải thưởng thỏa mãn các ràng buộc của bộ dữ liệu và phù hợp với tất cả các câu trả lời đã đưa ra. Lời giải phải tìm được hộp chứa kim cương ngay cả khi làm việc với chương trình chấm thích nghi này.

Ví dụ

Chương trình chấm gọi:

find_best(8);

Giả sử các loại giải thưởng trong tám hộp lần lượt là \([3,2,3,1,3,3,2,3]\). Các lời gọi có thể thực hiện và giá trị trả về tương ứng là:

ask(0) → [0, 3]
ask(1) → [0, 1]
ask(2) → [1, 2]
ask(3) → [0, 0]
ask(4) → [2, 1]
ask(5) → [2, 1]
ask(6) → [1, 0]
ask(7) → [3, 0]

Viên kim cương nằm trong hộp \(3\), nên find_best phải trả về \(3\).

Phần trên của hình thể hiện loại giải thưởng trong từng hộp. Phần dưới minh họa lời gọi ask(2): có một hộp được đánh dấu ở bên trái và hai hộp được đánh dấu ở bên phải, tương ứng với câu trả lời \([1,2]\).

Ràng buộc

• \(3\le n\le 200\,000\).
• Có \(v\ge 2\) loại giải thưởng; loại giải thưởng trong mỗi hộp là một số nguyên từ \(1\) đến \(v\).
• Có đúng một giải thưởng loại \(1\).
• Với mọi \(2\le t\le v\), nếu có \(k\) giải thưởng loại \(t-1\) thì có nhiều hơn \(k^2\) giải thưởng loại \(t\).

Tương đương, nếu \(c_t\) là số giải thưởng loại \(t\), thì:

Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

Ở subtask \(2\), bạn có thể nhận điểm thành phần. Nếu lời giải trả về đáp án đúng cho tất cả các bộ dữ liệu của subtask này, gọi \(q\) là số lần gọi ask lớn nhất trong tất cả các bộ dữ liệu đó. Điểm của subtask được tính như sau:

Trong khoảng \(5000<q\le 6000\), công thức tính điểm là:

Chương trình chấm mẫu

Chương trình chấm mẫu không thích nghi. Nó đọc và sử dụng một mảng giải thưởng cố định \(p\), trong đó \(p[b]\) là loại giải thưởng trong hộp \(b\) với mọi \(0\le b\le n-1\).

Dữ liệu vào của chương trình chấm mẫu có định dạng:

• Dòng \(1\): \(n\).
• Dòng \(2\): \(p[0]\ p[1]\ \ldots\ p[n-1]\).

Mảng \(p\) được chương trình chấm mẫu sử dụng để trả lời các lời gọi ask; hàm find_best chỉ nhận tham số \(n\).

Chương trình chấm mẫu C++ in giá trị trả về của find_best trên dòng đầu tiên. Dòng thứ hai có dạng Query count: q, trong đó \(q\) là tổng số lần gọi ask trong lần chạy đó. Chương trình chấm mẫu cũng giới hạn số lần gọi ask ở mức \(10\,000\) và yêu cầu mọi chỉ số được hỏi đều hợp lệ.

8
3 2 3 1 3 3 2 3

3
Query count: 8