Editorial for Bedao Regular Contest 05 - CCAKE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

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

Please read the guidelines before commenting.


There are no comments at the moment.