(6 ĐIỂM) BANG NHACTẠI MỘT QUẦY BĂNG ĐĨA NGỜI TA GHI CÁC BÀI HÁT THEO B...

Bài 3: (6 điểm) Bang nhac

Tại một quầy băng đĩa ngời ta ghi các bài hát theo băng. khi khách hàng chọn bài hát thứ

i trong băng thì phải quay băng để bỏ qua i-1 bài hát trớc đó. Thời gian quay băng bỏ qua

mọi bài hát trớc đó và thời gian phát bài hát đó là nh nhau. Trung bình mỗi lợt khách đến

các bài hát trong băng đợc họ lựa chọn là nh nhau. Giả sử băng của chủ quán có dung l-

ợng ghi vừa đủ N bài hát, với mỗi bài hát họ biết dung lợng mỗi bài hát phát ra. Hỏi chủ

quán phải ghi các bài hát vào băng nh thế nào để cho tổng thời gian quay băng trong mọi

lợt khách đến là nhanh nhất?

Dữ liệu vào: Từ file văn bản bannghac.inp nh sau:

- Dòng đầu tiên là số N(1<=N<=100) thể hiện số lợng bài hát.

- Dòng thứ 2 là N số nguyên N, mỗi số là thời gian phát mỗi bài hát.

Kết quả ra: Ghi vào file văn bản bangnhac.out nh sau:

- Dòng đầu tiên ghi tổng số thời gian phát băng đó nếu mỗi bài hát đợc phát một lần.

- N dòng tiếp theo, mỗi dòng ghi 2 số nguyên là thứ tự bài hát và thời gian tìm và phát bài

hát đó.

VD:

bangnhac.inp bangnhac.out

5 44

3 2 6 10 1 5 1

2 3

1 6

3 12

4 22

Họ và tên thí sinh:... Số báo danh:...