Ngày chụp ảnh
Đề bài
Mô tả
Hôm nay là ngày chụp ảnh ở một trường tiểu học. học sinh đứng thành một hàng dọc, trong đó là số chẵn; học sinh thứ tính từ đầu hàng có chiều cao và các chiều cao đôi một khác nhau.
Mỗi người trong hàng phải xuất hiện trong đúng một bức ảnh. Với một bức ảnh, thợ ảnh gọi người bất kỳ vẫn còn trong hàng (), không nhất thiết đứng cạnh nhau. Theo thứ tự trong hàng, người đầu tiên trong số họ tạo thành một hàng ảnh và người còn lại tạo thành một hàng ảnh khác. Thợ ảnh chọn hàng ảnh nào đứng trước; hàng còn lại đứng ngay phía sau. Những người trong cùng một hàng ảnh có thể đứng theo thứ tự bất kỳ, vì vậy để chắc chắn không ai bị che khuất, người thấp nhất ở hàng sau phải cao hơn người cao nhất ở hàng trước.
Ví dụ, với hàng , nếu gọi sáu bạn thì hàng ảnh thứ nhất là , hàng ảnh thứ hai là , và có thể chụp với hàng thứ hai đứng trước, vì người thấp nhất ở hàng sau () cao hơn người cao nhất ở hàng trước (). Ngược lại, với hàng , nếu gọi bốn bạn thì hai hàng ảnh và không thể tạo thành một bức ảnh: dù hàng nào đứng sau thì vẫn có thể có người bị che khuất.
Trước khi chụp ảnh, cô giáo có thể cho hai bạn đứng cạnh nhau trong hàng đổi chỗ cho nhau, bao nhiêu lần cũng được. Mỗi lần đổi chỗ mất giây và mỗi bức ảnh mất giây.
Yêu cầu: Tìm tổng thời gian nhỏ nhất để chụp ảnh cho tất cả mọi người.
Dữ liệu vào
- Dòng đầu tiên gồm ba số nguyên , và (, chẵn, ): số học sinh, thời gian một lần đổi chỗ và thời gian chụp một bức ảnh, tính bằng giây.
- Dòng thứ hai gồm số nguyên đôi một khác nhau (): chiều cao của các học sinh từ đầu hàng đến cuối hàng.
Dữ liệu ra
In ra một số nguyên duy nhất: tổng thời gian nhỏ nhất, tính bằng giây.
Ràng buộc
- , chẵn.
- .
- , các đôi một khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 10 120 130 110 140 |
11 | Hai bạn cao và đổi chỗ, hàng trở thành . Sau đó một bức ảnh chụp tất cả: đứng trước, đứng sau. Tổng thời gian là . |
| 4 20 10 120 130 110 140 |
20 | Không đổi chỗ, chụp hai bức ảnh: đầu tiên đứng trước , sau đó đứng trước . Tổng thời gian là . |
Bình luận