Bạn cần giải một bài tương tác được mô phỏng trong cùng tiến trình.

Độ ngon của mỗi chiếc bánh pudding là một số nguyên dương không quá \(4500\). Một chiếc bánh bí mật có độ ngon \(w\), trong đó \(1\le w\le m\).

Trong một lần hỏi, bạn chọn một dãy không rỗng \(a=[a_0,a_1,\ldots,a_{k-1}]\) gồm độ ngon của những chiếc bánh mua thêm. Thư viện chèn chiếc bánh bí mật vào dãy rồi sắp xếp thành

Giá trị trả về là

Hãy xác định chính xác \(w\), đồng thời dùng càng ít lần hỏi và càng ít bánh mua thêm càng tốt.

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

Bạn không được cài đặt hàm main, không được đọc standard input và không được ghi standard output. Submission phải include pudding.h và cài đặt:

void init(int c, int t);

• c là số hiệu test; c = 0 biểu thị dữ liệu mẫu.
• t là số trường hợp bí mật trong test.
• Thư viện gọi hàm đúng một lần khi chương trình bắt đầu.

int find_tastiness(int c, int m);

• c là số hiệu test và m là cận trên của \(w\).
• Hàm phải trả về chính xác \(w\).
• Thư viện gọi hàm đúng t lần. Mỗi lần gọi có một giá trị \(w\) đã được cố định riêng.

Trong find_tastiness, bạn có thể gọi:

int query_tastiness(std::vector<int> a);

• a phải không rỗng; mỗi phần tử phải thuộc \([1,4500]\).
• Hàm trả về tổng gcd được định nghĩa ở trên.
• Trong mỗi lần gọi find_tastiness, bạn được gọi query_tastiness không quá \(15\) lần.
• Tổng độ dài của mọi vector a trong một lần gọi find_tastiness không quá \(3000\).

Khung khai báo:

#include "pudding.h"

Thư viện tương tác không thích nghi: giá trị \(w\) đã được xác định trước mỗi lần gọi find_tastiness và không thay đổi theo các câu hỏi. Thí sinh không được tìm cách đọc trạng thái nội bộ của grader hoặc giao tiếp trực tiếp qua standard input/output.

Trong mọi trường hợp, phần thư viện của grader dùng không quá \(1.5\) giây và \(64\ \mathrm{MiB}\); lượng tài nguyên này không tính vào giới hạn dành cho submission.

Ràng buộc

• \(1\le t\le3000\).
• \(1\le m\le3000\).
• \(1\le w\le m\).

Phân nhóm

Tính chất A: \(w\) là số nguyên tố trong mọi trường hợp.

Cách tính điểm

Nếu có một giá trị trả về sai, một câu hỏi không hợp lệ hoặc vượt giới hạn, test tương ứng nhận \(0\) điểm.

Nếu mọi giá trị đều đúng, gọi \(Q\) là số câu hỏi lớn nhất trong một lần gọi find_tastiness, \(S\) là tổng số bánh mua thêm lớn nhất trong một lần gọi, và \(P\) là số điểm của test. Điểm nhận được là

Trong đó

và

Ví dụ tương tác

Giả sử \(m=197\) và chiếc bánh bí mật có \(w=26\).

Ở câu hỏi đầu, dãy sau sắp xếp là \([7,20,26,2026]\), nên kết quả bằng

Ở câu hỏi thứ hai, dãy là \([13,26,52]\) và kết quả bằng \(13+26=39\). Lần tìm này dùng \(Q=2\) câu hỏi và \(S=3+2=5\) bánh.

Nguồn

CCF NOI 2026 - Ngày 1, bài Pudding. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.