Cách 1

Thực hiện các bước sau:

1. Thêm một hộp mới, hộp mới thêm thì đặt vách ngăn vào hộp cho đến khi đạt giới hạn số lượng phần của hộp hoặc không còn vách ngăn nào nữa.
2. Cho bánh trung thu vào từng phần cho đến khi đạt giới hạn sức chứa mỗi phần hoặc không còn bánh trung thu nào nữa.
3. Nếu vẫn còn bánh trung thu thì lặp lại bước 1.

Số lượng hộp đã thêm là kết quả của bài toán.

Độ phức tạp: \(O\left(n\right)\).

Cách 2

Giả sử ta có \(x\) hộp, như vậy có thể chia được tối đa \(num = x + \min\left(\left(a-1\right) \cdot x, k\right)\) phần. Với \(x\) hộp ta có thể chứa được hết \(n\) bánh trung thu khi và chỉ khi \(num \cdot b \ge n\).

Từ đó có thể sử dụng chặt nhị phân để tìm ra kết quả.

Độ phức tạp: \(O\left(\log\left(n\right)\right)\).

Cách 3

Từ cách chặt nhị phân ở trên, ta có thể viết ra một công thức tính như sau:

• Xét tập giá trị \(x\) sao cho \(\left(a-1\right) \cdot x \le k\):
  • Khi đó \(x \le \left\lfloor \frac{k}{a-1} \right\rfloor\).
  • Giá trị \(x\) phải thỏa mãn \(\left(x + \min\left(\left(a-1\right) \cdot x, k\right)\right) \cdot b = a \cdot b \cdot x \ge n \Leftrightarrow x \ge \left\lceil \frac{n}{a \cdot b} \right\rceil\).
  • Nếu \(\left\lceil \frac{n}{a \cdot b} \right\rceil > \left\lfloor \frac{k}{a-1} \right\rfloor\) thì không tồn tại \(x\) thỏa mãn.
  • Nếu ngược lại thì giá trị \(x\) nhỏ nhất thỏa mãn và cũng là kết quả bài toán là \(\left\lceil \frac{n}{a \cdot b} \right\rceil\).
• Xét tập giá trị \(x\) sao cho \(\left(a-1\right) \cdot x > k\):
  • Khi đó \(x > \left\lfloor \frac{k}{a-1} \right\rfloor \Leftrightarrow x \ge \left\lfloor \frac{k}{a-1} \right\rfloor + 1\).
  • Giá trị \(x\) phải thỏa mãn \(\left(x + \min\left(\left(a-1\right)\cdot x, k\right)\right) \cdot b = \left(x + k\right) \cdot b \ge n \Leftrightarrow x \ge \left\lceil \frac{n}{b} \right\rceil - k\).
  • Như vậy thì giá trị \(x\) nhỏ nhất thỏa mãn là \(\max\left( \left\lfloor \frac{k}{a-1} \right\rfloor + 1, \left\lceil \frac{n}{b} \right\rceil - k \right)\).

Độ phức tạp: \(O\left(1\right)\).