Có gì trong đề IOI 2026 Day 1 · Kệ Sách nhà Sơn

IOI là một trong những kỳ thi lớn nhất hằng năm dành cho học sinh trung học, xoay quanh thuật toán và lập trình: mỗi ngày thi năm tiếng, ba thử thách. Cùng với ICPC Final, đây cũng là nơi cho ra những bộ đề khó nhất mỗi năm.

Vậy có gì trong ngày 1 đề thi năm 2026?

Bài 1

Ball Machine

Đề bài

Tóm tắt

Bạn được cho một cây ẩn: không biết cây có bao nhiêu đỉnh, cũng không biết hình dạng của nó. Thứ duy nhất được biết là cây có đúng M đỉnh lá.

Ban đầu cây hoàn toàn trống — không đỉnh nào chứa bóng. Bạn tương tác với cây qua đúng hai thao tác: insert(U, X) và collect().

Mỗi đỉnh chứa tối đa một quả bóng. Bóng chỉ đi lên, không bao giờ đi xuống.

Máy · mô phỏng

Cỗ máy

U = 1X =

Cây mẫu trên chỉ để minh hoạ cơ chế: 7 đỉnh, M = 4 lá. Trong đề thật, cấu trúc này bị giấu đi.

Thao tác I

insert(U, X)

bool insert(int U, int X)

Thả một quả bóng mang giá trị X vào đỉnh U.
Quả bóng di chuyển lên phía gốc chừng nào đỉnh cha hiện tại còn trống; nó dừng lại ngay khi đỉnh cha đã có bóng, hoặc khi đã tới gốc.
Trả về false nếu toàn bộ đường đi từ U lên gốc đã đầy — quả bóng không có chỗ để nằm.
Ngược lại trả về true, và vị trí cuối cùng của bóng là đỉnh trống cao nhất mà nó chạm tới được.

Hệ quả: tập các đỉnh có bóng luôn liên thông với gốc — nếu một đỉnh có bóng thì cha của nó cũng có bóng.

Thao tác II

collect()

vector<int> collect()

Bắt đầu tại gốc. Nếu đỉnh hiện tại có bóng, thu giá trị của nó và đẩy vào mảng kết quả, đỉnh trở thành trống.
Trong các đỉnh con đang giữ bóng, chọn đỉnh có giá trị nhỏ nhất rồi đệ quy xuống đó.
Nếu nhiều đỉnh con cùng giá trị nhỏ nhất, máy đi vào một trong số đó một cách ngẫu nhiên.
Lặp lại cho tới khi không còn đỉnh con nào giữ bóng; quay lui và tiếp tục.

Trả về mảng đã thu thập. Sau thao tác này, cây trở lại rỗng hoàn toàn.

Thứ tự trong mảng chính là kênh thông tin duy nhất rò rỉ ra ngoài về hình dạng của cây.

Minh hoạ I

Quả bóng trôi lên — insert(1, 20)

Trạng thái ban đầu

Tất cả các đỉnh đều rỗng

Chèn giá trị 20 vào đỉnh 1

(đỉnh lá bên trái)

Đỉnh cha của đỉnh 1 còn rỗng

→ Đẩy giá trị 20 lên đỉnh cha

Đỉnh cha vẫn còn rỗng

→ Tiếp tục đẩy 20 lên tới gốc (root)

đỉnh đang giữ bóng 20đỉnh rỗnghướng bóng di chuyển

Minh hoạ II

Trình tự thu thập — collect()

Bắt đầu từ gốc (10)

→ thu 10 vào mảng, đỉnh gốc trở nên rỗng

Mảng: [10]

Chọn đỉnh con nhỏ nhất (20)

→ thu 20 vào mảng

Mảng: [10, 20]

Tiếp tục xuống 40

→ thu 40 vào mảng, hết đỉnh con

Mảng: [10, 20, 40]

Quay lại gốc: hai đỉnh 30

→ chọn ngẫu nhiên, giả sử nhánh phải

Mảng: [10, 20, 40, 30]

Tại đỉnh 30 nhánh phải

→ con nhỏ nhất là 50, thu 50

Mảng: [10, 20, 40, 30, 50]

Quay lại gốc: còn đỉnh 30

→ thu 30, cây rỗng hoàn toàn

Mảng: [10, 20, 40, 30, 50, 30]

đỉnh đang thu thậpđỉnh còn bóngđỉnh rỗng

Kết quả cuối cùng[ 10 , 20 , 40 , 30 , 50 , 30 ]

Bước 4 là chỗ duy nhất có ngẫu nhiên: hai đỉnh con cùng mang giá trị 30, máy chọn một trong hai. Ở đây giả sử nó chọn nhánh phải.

Ghi chú kỹ thuật

Quy ước & điểm cần chú ý

Số đỉnh N không biết trước; chỉ có M — số lá — là dữ kiện cho sẵn.
Mỗi lần insert chỉ thêm đúng một bóng, và kết quả true/false đã là một bit thông tin về độ “đầy ” của đường lên gốc.
Vì tập đỉnh có bóng luôn liên thông với gốc, một dãy insert vào cùng một đỉnh U sẽ lần lượt lấp đầy đường U → gốc từ trên xuống.
Giá trị X do bạn chọn — dùng nó để điều khiển thứ tự duyệt của collect, biến thao tác thu thập thành phép đo.
Tính ngẫu nhiên khi trùng giá trị là nguồn nhiễu duy nhất: tránh nó bằng cách luôn dùng các giá trị đôi một khác nhau.

Trong bản mô phỏng ở trên, nếu U đã có bóng nhưng phía trên còn chỗ trống, quả bóng được coi là trôi lên tới đỉnh trống gần nhất rồi tiếp tục leo theo luật thường.

Chấm điểm

Ràng buộc & subtask

2 ≤ N ≤ 1000
1 ≤ M ≤ 200
M < N

Subtask	Ràng buộc thêm	Điểm
01	Gốc có đúng M đỉnh con.	5 / 5
02	M ≤ 3	10 / 10
03	N ≤ 200, M ≤ 45	13 / 25
04	Không có ràng buộc thêm.	7 / 60
Tổng		35 / 100

Điểm riêng phần theo C

Hai subtask đầu chấm trọn gói. Subtask 3 và 4 thì điểm trượt theo C — càng nhỏ càng nhiều điểm:

Subtask 3 · 25 điểm

	1000 < C	0
▸	45 < C ≤ 1000	13
	C ≤ 45	25

Subtask 4 · 60 điểm

	1000 < C	0
▸	200 < C ≤ 1000	7
	71 < C ≤ 200	47 − C/5
	44 < C ≤ 71	104 − C
	C ≤ 44	60

▸ mức điểm hiện tại

Lời giải hiện tại được 13 ở subtask 3 và 7 ở subtask 4, tức C đang nằm trong khoảng 200 < C ≤ 1000. Muốn ăn thêm thì phải kéo C xuống: dưới 200 là subtask 4 bắt đầu tăng liên tục, C ≤ 45 thì subtask 3 đạt trọn 25, và C ≤ 44 thì subtask 4 đạt trọn 60.