Hướng dẫn giải bài khó trên 799. Champagne Tower leetcode

https://leetcode.com/problems/champagne-tower/description/

Bạn không thể ngủ vì thấy bản thân ngu không thể tả khi không làm được bài khó ? Đừng lo captain Minh ở đây để giúp bạn

Đề bài:
Chúng ta xếp ly theo hình kim tự tháp, hàng đầu tiên có 1 ly, hàng thứ hai có 2 ly, cứ tiếp tục như vậy cho đến hàng thứ 100. Mỗi ly đựng một cốc sâm panh.

Sau đó, một ít sâm panh được rót vào ly đầu tiên ở trên cùng. Khi cốc trên cùng đầy, chất lỏng đổ thừa sẽ rơi đều xuống cốc ngay bên trái và bên phải cốc. Khi những chiếc ly đó đầy, lượng sâm panh dư thừa sẽ rơi đều về bên trái và bên phải của những chiếc ly đó, v.v. (Một chiếc ly ở hàng dưới cùng có lượng sâm panh dư thừa rơi xuống sàn.)

Ví dụ, sau khi rót một cốc sâm panh thì phần trên cùng của ly sẽ đầy. Sau khi rót hai cốc sâm panh, hai ly ở hàng ghế thứ hai đã đầy một nửa. Sau khi rót ba cốc sâm panh, hai cốc đó sẽ đầy - bây giờ có tổng cộng 3 ly đầy. Sau khi rót bốn cốc sâm panh, hàng thứ ba có ly ở giữa đầy một nửa, và hai ly bên ngoài đầy một phần tư, như hình bên dưới.

Khi lướt qua đề bài chúng ta có thể đơn giản nghĩ rằng chỉ cần tìm số hàng mà có thể đổ đầy số ly ( ví dụ với 11 ly thì chúng ta sẽ lấp được đầy 4 hàng ( vì 1+2+3+4=10 ) và chỉ cần chia ly thứ 11. Với mỗi ly dư thì ly ngoài cùng và trong cùng sẽ được chia 1/ (2 ^ số hàng đã hoàn thành ) và mỗi ly ở giữa thì chỉ cần lấy phần còn lại chia đều. Tuy nhiên thì đời không như là mơ, nếu nghĩ kĩ chúng ta có thể thấy rằng để rượu bắt đầu chảy xuống 1 hàng thì hàng trước đó không nhất thiết phải đầy. Với ví dụ trong ảnh , chúng ta có thể thấy rằng đến ly thứ 5 là ly giữa của hàng số 3 đã đầy và từ ly thứ 6 bắt đầu chảy xuống.  Nói chung là đồ cứng nên anh em đừng cố ranh ma dùng toán cho nhanh.

Với bài này chúng ta có thể chạy từng hàng và rót từng ly, sau đó nếu tràn thì sẽ chia luôn vào 2 bên trái phải ở hàng kế tiếp