Đề bài

Có \(N\) nguyên liệu, đánh số từ \(0\) đến \(N-1\). Đầu bếp có thể làm một tập \(X\) các loại sốt. Mỗi loại sốt \(S\in X\) dùng đúng \(2\) hoặc \(3\) nguyên liệu, tức là \(S\subseteq\{0,1,\ldots,N-1\}\) và \(|S|\in\{2,3\}\). Hai loại sốt khác nhau không có cùng tập nguyên liệu.

Bạn cần xác định \(|X|\). Tập \(X\) không được cung cấp trực tiếp; thay vào đó, bạn có thể thực hiện các phép thử mù. Trong một phép thử, bạn chọn một tập nguyên liệu \(Y\) thỏa mãn

Grader trả về

Mục tiêu là tìm chính xác \(|X|\) với ít phép thử nhất.

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

int solve(int N);
int query(vector<int> Y);

• solve(N) được gọi đúng một lần và phải trả về \(|X|\).
• Trong solve, bạn có thể gọi query(Y). Các phần tử của Y phải phân biệt, nằm trong \([0,N-1]\), và kích thước không vượt quá \(\lceil N/2\rceil+1\).
• query trả về \(f(Y)\) và được gọi nhiều nhất \(3\,000\) lần trong một test.
• Chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• \(6\le N\le 1\,000\).
• \(1\le |X|\le 50\,000\).
• Mọi \(S\in X\) có \(|S|\in\{2,3\}\).
• Grader không thích nghi: \(X\) được cố định trước khi solve được gọi.

Phân nhóm

Nếu chương trình trả lời sai ở bất kỳ test nào của một nhóm, điểm của nhóm đó là \(0\). Nếu mọi test đều đúng, gọi \(Q\) là số lần gọi query lớn nhất trong nhóm:

• Nhóm 1 và 2 nhận toàn bộ điểm nếu \(Q\le 3\,000\).
• Với nhóm 3 và 4, nếu \(Q\le 41\) thì nhận toàn bộ điểm. Nếu \(41<Q\le 3\,000\), điểm nhóm được nhân với

Grader mẫu

Grader mẫu đọc \(N\), số \(K=|X|\), rồi \(K\) dòng mô tả từng loại sốt dưới dạng L a[0] ... a[L-1]. Grader in giá trị solve trả về và số lần gọi query.

6
2
2 0 1
3 2 3 4

2
3

Trong ví dụ, \(X=\{\{0,1\},\{2,3,4\}\}\). Một cách hợp lệ là hỏi lần lượt các tập \(\{0,1,2\}\), \(\{2,3,4\}\) và \(\{0,2,3,5\}\), nhận các kết quả \(1,1,0\), rồi trả về \(2\).

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 2, giấy phép CC BY-NC-SA 4.0.