Những cây cầu đẹp
Đề bài
Mô tả
Điều gì kết nối tất cả chúng ta? Thường thì đó là những cây cầu. Từ thời cổ đại, con người đã xây cầu cho đường bộ, cho tàu hỏa, cho người đi bộ, và làm cầu máng dẫn nước. Đó là cách nhân loại không chịu khuất phục trước địa hình bất tiện.
Công ty Xây dựng Cầu Vòm (ABC) chuyên, như bạn đoán, xây cầu vòm. Kiểu cầu cổ điển này được đỡ bởi các trụ cầu dựng từ mặt đất bên dưới cầu. Các vòm nằm giữa các trụ phân bố trọng lượng của cầu lên các trụ kề bên.
Cầu của ABC thường có các trụ đặt cách nhau không đều. Vì lý do thẩm mỹ, các vòm cầu của ABC luôn là nửa đường tròn, như minh họa trong hình dưới. Tuy nhiên, vòm cầu có thể chạm mặt đất nhưng không được đi xuống dưới mặt đất. Điều này khiến một số cách đặt trụ là không thể.

Hình (a): hai trụ liên tiếp cách nhau được nối bởi một vòm nửa đường tròn bán kính , đỉnh vòm nằm ở mặt cầu. Hình (b): một cách đặt trụ không hợp lệ (vòm không được đi xuống dưới mặt đất). Hình (c): một cây cầu ứng với ví dụ thứ nhất.
Với một mặt cắt địa hình và độ cao mong muốn của cầu, thường có nhiều cách xây một cây cầu vòm. Mặt cắt địa hình được mô hình hóa bằng một hàm tuyến tính từng khúc, cho bởi điểm mốc , trong đó tọa độ của một điểm là vị trí dọc theo cây cầu, còn tọa độ là độ cao của mặt đất so với mực nước biển tại vị trí đó. Trụ đầu tiên và trụ cuối cùng phải được xây tại điểm mốc đầu tiên và điểm mốc cuối cùng, các trụ ở giữa chỉ được xây tại các điểm mốc. Chi phí của một cây cầu gồm chi phí các trụ (tỉ lệ với chiều cao của chúng) cộng với chi phí các vòm (tỉ lệ với lượng vật liệu sử dụng). Như vậy một cây cầu có trụ với chiều cao , các trụ liên tiếp cách nhau theo phương ngang các khoảng , có tổng chi phí là
với các hằng số và cho trước. ABC muốn xây mỗi cây cầu với chi phí nhỏ nhất có thể.
Dữ liệu vào
Dòng đầu tiên chứa bốn số nguyên , , và : là số điểm mô tả mặt cắt địa hình, là độ cao mong muốn của cây cầu so với mực nước biển, và là các hệ số chi phí như mô tả ở trên.
Tiếp theo là dòng, dòng thứ chứa hai số nguyên , mô tả mặt cắt địa hình.
Dữ liệu ra
In ra chi phí nhỏ nhất để xây một cây cầu từ vị trí tới vị trí ở độ cao so với mực nước biển. Nếu không thể xây được cây cầu nào như vậy, in ra impossible.
Ràng buộc
- .
- .
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 60 18 2 0 0 20 20 30 10 50 30 70 20 |
6460 | Đặt trụ tại (hình (c)). Chiều cao các trụ là , tổng ; các khoảng cách là . Chi phí . |
| 4 10 1 1 0 0 1 9 9 9 10 0 |
impossible | Trụ tại (hoặc ) chỉ cao , nên mọi vòm nối với nó phải có bán kính không quá và không thể tới (hoặc ). Vòm nối thẳng với có bán kính , tại chỉ cao so với mực nước biển, nên cắt vào mặt đất. |
Bình luận