Âu thuyền
Đề bài
Mô tả
Âu thuyền là một buồng có cửa chắn, dùng trên kênh đào và sông để đưa thuyền qua lại giữa các đoạn nước có độ cao khác nhau. Khi thuyền đi vào buồng, các cửa được đóng lại, mực nước trong buồng được dâng lên hoặc hạ xuống cho bằng đoạn nước kế tiếp, và thuyền tiếp tục hành trình một cách êm ả. Nhờ có âu thuyền, những tuyến đường thủy dài có thể vượt đồi và băng qua nhiều dạng địa hình mà không cần một lộ trình hoàn toàn bằng phẳng.
Khi đưa thuyền lên dốc: (1) thuyền ở độ cao thấp, cửa trái mở để thuyền đi vào; (2) thuyền vào buồng, cả hai cửa đóng lại; (3) nước được bơm vào buồng, mực nước dâng lên; (4) thuyền đã ở độ cao cao hơn, cửa phải mở để thuyền đi ra; (5) thuyền rời buồng. Khi đưa thuyền xuống dốc thì làm tương tự: thuyền vào từ cửa phải ở độ cao cao, cả hai cửa đóng, nước được rút bớt khỏi buồng để hạ mực nước, rồi cửa trái mở cho thuyền đi ra ở độ cao thấp hơn.
Bạn phụ trách hệ thống âu thuyền phức tạp nhất thế giới, gồm buồng. Buồng thứ đặt ngay tại độ cao () và có thể đưa thuyền từ độ cao lên độ cao và ngược lại. Buồng thứ có diện tích đáy , nghĩa là lượng nước cần để vận hành buồng thứ là . Lượng nước cần để vận hành cả hệ thống được định nghĩa là lượng nước lớn nhất cần cho một buồng nào đó trong hệ thống.
Để cắt giảm chi phí vận hành, bạn được giao nhiệm vụ giảm số buồng xuống còn . Để làm điều đó, bạn được thực hiện thao tác sau đúng lần:
Giả sử số buồng hiện tại là . Chọn hai buồng liên tiếp và (). Chúng được thay bằng một buồng duy nhất:
- nối thẳng độ cao với độ cao (độ cao biến mất khỏi hệ thống);
- có diện tích đáy .
Sau khi gộp, số buồng giảm đi và các buồng được đánh số lại từ đến theo thứ tự độ cao tăng dần.
Chi phí vận hành là quan trọng, nhưng tiết kiệm nước cũng quan trọng không kém. Trong tất cả các cách giảm số buồng xuống còn , hãy tìm lượng nước nhỏ nhất có thể cần để vận hành cả hệ thống.
Dữ liệu vào
Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu:
- Dòng thứ nhất chứa hai số nguyên và (): số buồng ban đầu của hệ thống và số buồng cần đạt được.
- Dòng thứ hai chứa số nguyên (): các độ cao đặt buồng.
- Dòng thứ ba chứa số nguyên (): diện tích đáy của các buồng.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra lượng nước nhỏ nhất có thể cần để vận hành cả hệ thống, trong tất cả các cách giảm số buồng xuống còn .
Ràng buộc
- .
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 2 2 3 5 7 9 8 4 2 1 2 3 4 1 1 1 1 |
48 4 |
Bộ thứ nhất: có cách. Gộp buồng và : buồng mới nối độ cao với , diện tích đáy , cần ; buồng còn lại cần ; cả hệ thống cần . Gộp buồng và : buồng thứ nhất cần , buồng mới cần , cả hệ thống cần . Đáp án là . Bộ thứ hai: gộp hai buồng đầu thành buồng cần , gộp hai buồng cuối thành buồng cần . |
| 1 5 3 1 3 4 8 10 2 1 5 1 3 |
24 | Ví dụ bổ sung (không có trong đề gốc). Gộp buồng với , và buồng với : các buồng cần , và . |
Bình luận