c++
Bài 2: Nghe nhạc
Tại một trung tâm thương mại, người ta lắp một băng nhạc vào một máy phát nhạc. Khách
hàng muốn nghe bài hát nào chỉ việc nhấn phím ứng với bài đó. Để tìm và phát bài thứ i trên
băng, máy xuất phát từ đầu cuộn băng, quay băng để bỏ qua i1 bài ghi trước đó, thời gian quay băng bỏ qua mỗi bài và thời gian phát bài đó được
tính là như nhau (băng nhạc ghi N bài hát, được mã số từ 1 đến N có thời lượng tính theo phút
đủ chứa toàn bộ các bài đã cho, với mỗi bài hát ta biết thời lượng phát của bài đó). Tính trung
bình, các bài hát trong một ngày được khách hàng lựa chọn với số lần (tần suất) như nhau. Hãy
tìm cách ghi các bài trên băng sao cho tổng thời gian quay băng trong mỗi ngày là ít nhất.
Dữ liệu vào: File NHAC.INP gồm 2 dòng, dòng 1 là số tự nhiên N cho biết số lượng bài hát,
dòng 2 là N số nguyên dương thể hiện dung lượng tính theo phút của mỗi bài (mỗi số cách nhau
1 dấu cách).
Kết quả: File NHAC. OUT gồm:
• N dòng đầu tiên thể hiện trật tự bài hát trên băng (mỗi dòng gồm haisố nguyên dương j và
d cách nhau bởi dấu cách, trong đó j là mã số của bài hát cần ghi, d là thời gian tìm và
phát bài đó theo trật tự ghi này).
• Dòng thứ N + 1 ghi tổng số thời gian quay băng nếu mỗi bài hát được phát một lần
trong ngày.
Ví dụ:
nhac.inp 
3 8 3 4
nhac.out
2 3
3 7
1 15
25