Chở Hàng
Xem PDFvà là đôi bạn thân. Bọn họ quyết định tổ chức tiệc ở nhà của . Để chuẩn bị cho buổi tiệc, họ cần vận chuyển hàng hóa từ kho đến địa điểm tổ chức.
Hai bọn họ thuê một công ty có \(N\) xe tải, mỗi xe tải chở một khối lượng hàng hóa nhất định. Mỗi lần vận chuyển được tối đa \(3\) xe. Biết rằng thời gian cơ bản để đi tới nhà của là \(60\) phút, và cứ mỗi \(1\) kg hàng hóa trên xe thì xe đó sẽ đi muộn thêm \(5\) phút.
Trong một chuyến (tối đa \(3\) xe), thời gian hoàn thành chuyến đó được tính bằng thời gian của xe đi lâu nhất trong nhóm. Sau khi một chuyến (nhóm \(3\) xe) đi xong thì mới được bắt đầu chuyến tiếp theo. Vì muốn tạo bất ngờ cho nên cả hai phải chuẩn bị trong tổng thời gian nhanh nhất.
Yêu cầu: In ra tổng số phút tối ưu (nhỏ nhất) cần để chở toàn bộ số xe hàng tới nhà của .
Input
- Dòng 1: Một số nguyên dương \(N\) (\(N \le 500\)).
- Dòng 2: Gồm \(N\) số nguyên dương, mỗi số đại diện cho khối lượng hàng hóa (tính bằng kg) của từng xe tải.
Output
- Một số nguyên duy nhất là tổng số phút tối ưu để hoàn thành việc vận chuyển.
Example
Test 1
Input
2
1 7Output
95Note
Hai xe này có thể đi cùng một chuyến. Xe chở \(7\) kg sẽ mất \(60 + 7 \cdot 5 = 95\) phút. Xe chở \(1\) kg mất \(60 + 1 \cdot 5 = 65\) phút. Thời gian chuyến đi tính theo xe lâu nhất là \(95\) phút.
Test 2
Input
4
1 8 4 4Output
165Note
Để tối ưu, ta có thể chia làm 2 chuyến:
- Chuyến 1: Gồm các xe có khối lượng \(8, 4, 4\) kg. Thời gian chuyến này là \(60 + 8 \cdot 5 = 100\) phút.
- Chuyến 2: Gồm xe có khối lượng \(1\) kg. Thời gian chuyến này là \(60 + 1 \cdot 5 = 65\) phút.
- Tổng thời gian: \(100 + 65 = 165\) phút.
Constraints
- \(N \le 500\)
- Khối lượng mỗi xe không quá \(10^6\) kg.
Bình luận (8)