Editorial for Bedao Regular Contest 05 - CCAKE
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Khi cắt chiếc bánh bằng ~X~ đường cắt ngang và ~Y~ đường cắt dọc, dễ thấy rằng chiếc bánh này sẽ được chia thành ~X + 1~ phần theo chiều ngang và ~Y + 1~ phần theo chiều dọc.
Mỗi miếng bánh được cắt ra đều có diện tích ~\ge S~, vì vậy nếu như ta coi phần bé nhất được cắt ra theo chiều ngang là ~i~, thì tất cả phần được cắt ra theo chiều dọc phải ~\ge j = \lceil \frac{S}{i} \rceil~. Dựa vào điều này, ta có đáp án là tổng của ~3~ trường hợp sau:
- ~i \ge \lceil \sqrt{S} \rceil, j \ge \lceil \sqrt{S} \rceil.~
- ~i < \lceil \sqrt{S} \rceil, j \ge \lceil \sqrt{S} \rceil.~
- ~i \ge \lceil \sqrt{S} \rceil, j < \lceil \sqrt{S} \rceil.~
Ở trường hợp ~1~, ta tính trực tiếp đáp án trong ~\mathcal{O}(1)~. Ở trường hợp ~2~, ta lặp qua tất cả các giả trị của ~i < \lceil \sqrt{S} \rceil~. Ở trường hợp ~3~, ta lặp qua tất cả các giả trị của ~j < \lceil \sqrt{S} \rceil~.
Do đó, ta đã chuyển được bài toán trở về hai bài toán con như sau:
- Chia ~n~ số thành ~a~ số đều có giá trị ~\ge b~.
- Chia ~n~ số thành ~a~ số có giá trị bé nhất là ~b~.
Với bài toán đầu tiên, dễ thấy được đây là bài toán chia kẹo điển hình, với công thức là ~\binom{n - a \times (b - 1) - 1}{k - 1}~.
Với bài toán thứ hai, ta nhận thấy rằng đáp án là số cách chia ~n~ số thành ~a~ số đều có giá trị ~\ge b~, trừ đi số cách chia ~n~ số thành ~a~ số đều có giá trị ~> b~. Do đó ta sẽ dùng cách tính của bài toán thứ nhất để tìm đáp án của bài toán thứ hai.
Độ phức tạp thuật toán: ~\mathcal{O}(t \times \sqrt{S})~.
Comments