Chọn đội tuyển Olympic 2026 môn Tin học, Ngày 1, Bài 2

1. Tóm tắt đề

Có $N$ quả bóng được đánh số từ $0$, quả thứ $i$ có màu $A_i$. Có $K (3 \leq K \leq N)$ màu được đánh số từ $0$, trong đó với mỗi màu, có ít nhất $1$ quả bóng có màu đó.

Bạn chỉ được biết số $N$, không được biết mảng $A$ và số màu $K$.

Với mỗi câu hỏi, bạn có thể chọn một tập con gồm một số quả bóng trong $N$ quả, sau đó bạn sẽ được biết số lượng màu khác nhau trong các quả bóng được chọn có lớn hơn hoặc bằng $\lfloor \frac{K + 1}{2} \rfloor$ hay không.

Yêu cầu: Trả ra một mảng $B$ sử dụng ít câu hỏi nhất có thể, trong đó:

• $0 \leq B_i < K$.
• Với mọi cặp số $(i, j)$, nếu $A_i = A_j \Leftrightarrow B_i = B_j$.

Scoring:

• Subtask $1 (10\%)$: $N \leq 10, K = 3$.
• Subtask $2 (20\%)$: $N \leq 10$.
• Subtask $3 (70\%)$: $N \leq 256$.

Tính điểm: Nếu trong bất kỳ trường hợp thử nghiệm nào, chương trình của bạn trả về cấu hình không thỏa mãn yêu cầu đề bài thì bạn sẽ không nhận được điểm cho test đó. Ngược lại, gọi $P$ là số câu hỏi mà bạn sử dụng:

• $P \leq 1400$: $100\%$ số điểm.
• $1400 \leq P \leq 14000$: $\frac{1400}{P} \times 100\%$ số điểm.
• $P > 14000$: $0\%$ số điểm.

2. Subtask 1

Mỗi câu hỏi chỉ cần hỏi $2$ cặp $i, j$ sẽ biết $A_i = A_j$ hay $A_i \neq A_j$. Từ đây dễ dàng tìm được mảng $B$.

3. Subtask 2

Hỏi toàn bộ câu hỏi có thể ($2^N$ câu hỏi). Từ đây có thể suy ra mảng $B$.

4. Subtask 3

Ta chia mảng $A$ thành $2$ tập $X$ và $Y$, trong đó:

• Tập $X$ có $\lfloor \frac{K + 1}{2} \rfloor - 1$ màu phân biệt.
• Tập $Y$ có $K - \left(\lfloor \frac{K + 1}{2} \rfloor - 1\right)$ màu phân biệt.

Dễ thấy có thể làm điều này trong $N$ câu hỏi bằng cách nạp dần các phần tử vào tập $X$, nếu không thỏa thì đẩy qua tập $Y$.

Sau đó, ta tìm các “điểm cắt” của tập $X$, tức là tìm các điểm $i_1, i_2, \dots$, trong đó:

• $X_0, X_1, \dots, X_{i_1}$ có $1$ màu phân biệt.
• $X_0, X_1, \dots, X_{i_2}$ có $2$ màu phân biệt.

$$\dots$$

Có thể làm điều này bằng cách bỏ dần phần tử ở tập $X$ cho đến khi tập $X$ kết hợp với một số phần tử của tập $Y$ có ít hơn $\lfloor \frac{K + 1}{2} \rfloor$ màu phân biệt. Sau đó thêm lại một số phần tử của $Y$ vào $X$ để $X$ trở về số màu ban đầu.

Sau khi tìm được các điểm cắt, có thể dễ dàng sử dụng chặt nhị phân để tìm mảng $B$.

Cách này tốn khoảng $1500$ câu hỏi trong trường hợp xấu nhất. Tuy nhiên, nếu ta shuffle mảng $A$ trước khi hỏi thì chỉ mất khoảng $1350$ câu hỏi.