Hướng giải: MOVES

Nguồn: Free Contest

Đặt tổng số sinh viên của toàn bộ ~n~ ngôi nhà là ~S~.

Dễ thấy luôn tồn tại cách yêu cầu các bạn sinh viên di chuyển để số người trong các ngôi nhà lúc sau tạo thành một dãy số bất kì có tổng các phần từ bằng ~S~.

Ta sắp xếp các sinh viên để số người trong các ngôi nhà tạo thành dãy số: ~d~, ~0~, ~d~, ~0~, ~. . .~ cho tới khi còn ít hơn ~d~ người thì ta cho số người còn lại đó vào ngôi nhà cuối cùng.

Dễ thấy cách xếp này thoả mãn yêu cầu của chính phủ đưa ra rằng hai ngôi nhà liên tiếp không có quá ~d~ người và cách xếp này có thể chứa được tối đa ~\lfloor\frac{n+1}{2}\rfloor.d~ sinh viên.

Ta sẽ chứng minh rằng trong mọi cách xếp thoả mãn ~S \le \lfloor\frac{n+1}{2}\rfloor.d~:

Nếu ~n~ là số chẵn: $$\displaystyle \begin{cases} a_1 + a_2 \le d \\ a_3 + a_4 \le d \\ ... \\ a_{n-1} + a_n \le d \end{cases} $$

\(→ \lfloor\frac{n+1}{2}\rfloor.d = \frac{n}{2}.d = a_1 + a_2 + . . . + a_n = S \le \lfloor\frac{n+1}{2}\rfloor.d\)

Đối với trường hợp ~n~ lẻ ta chứng minh tương tự.

Vậy cách xếp nêu trên luôn là tối ưu. Câu trả lời cho truy vấn là ~\text{YES}~ nếu ~S \le \lfloor\frac{n+1}{2}\rfloor.d~, còn lại là ~\text{NO}~.