nguyenquangminh423@gmail.com
Nông dân
9 Dự án
4 Bài đăng
0 Khóa học

Giới thiệu bản thân

Thông tin cá nhân

  • Bạn có 100,800 thóc

Giải thưởng

    Chưa có giải thưởng

Thông tin Học tập

  • Học sinh chưa tham gia khóa học tại TEKY

Kỹ năng công nghệ

    Học sinh chưa hoàn thành kỹ năng Công nghệ nào trong chương trình học tại TEKY

Thành tích đạt được

  • Học sinh chưa hoành thành chương trình học nào tại TEKY

project
project
project
project
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


Xem thêm
Ly Ly Mew

giỏi quá

Trả lời 146d

Đăng nhập để tham gia bình luận


Hùng Hoàng Việt
test

Sao bạn đỉnh thế

Trả lời 147d

Đăng nhập để tham gia bình luận


Đăng nhập để tham gia bình luận