Đào xúc regolith
Đề bài
Mô tả
Một cơn bão vũ trụ đã phủ lớp regolith (đất đá vụn) nguy hiểm dọc theo một đường hào dài . Đường hào gồm ô được đánh số từ đến từ trái sang phải, ô chứa gam regolith (). Bên ngoài đường hào có hai trạm thải: trạm (bên trái) và trạm (bên phải).
Tiến sĩ Aurel có chiếc xẻng trọng lực được đánh số từ đến . Xẻng () mỗi lần có thể vận chuyển tối đa gam regolith giữa hai ô kề nhau (từ ô sang ô , hoặc từ ô sang ô ) với chi phí calo.
Để điều phối việc dọn dẹp, người ta chọn một ngưỡng phân chia ():
- Toàn bộ regolith ở các ô được chuyển sang trái về trạm .
- Toàn bộ regolith ở các ô được chuyển sang phải về trạm .
Hãy giải một trong hai bài toán con, tùy theo :
- Nếu : cho trước , hãy tính tổng số calo nhỏ nhất cần dùng.
- Nếu : hãy tìm giá trị () sao cho tổng số calo tiêu tốn là nhỏ nhất. Nếu có nhiều giá trị cùng đạt giá trị nhỏ nhất, hãy tìm nhỏ nhất.
Dữ liệu vào
- Dòng 1: số nguyên .
- Dòng 2: số nguyên ().
- Dòng 3: số nguyên cách nhau bởi dấu cách ().
- Dòng 4 (chỉ có khi ): số nguyên ().
Dữ liệu ra
In ra một số nguyên duy nhất: đáp án của bài toán con .
Ràng buộc
- .
- .
- .
- (khi ).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 4 1 3 1 3 2 |
10 | Ô chuyển về trạm : từ ô sang ô chuyển gam (xẻng và xẻng , hoặc một lần xẻng : calo), từ ô sang trạm chuyển gam (xẻng : calo). Ô chuyển về trạm : từ ô sang ô chuyển gam ( calo), từ ô sang trạm chuyển gam ( calo). Tổng . |
| 2 5 2 1 1 1 2 |
2 | Ví dụ bổ sung (không có trong đề gốc). Tổng calo nhỏ nhất với lần lượt là ; cả và đều tối ưu nên in nhỏ hơn là . |
Bình luận