(MS0027)TRONG MỘT TRÒ CHƠI TRUYỀN TIN, MỖI ĐỘI CHƠI GỒM N THÀNH VIÊN Đ...

Bài 1: (MS0027)Trong một trò chơi truyền tin, mỗi đội chơi gồm n thành viên được bố trí dọc theo một đoan đường. Mộtđầu của đoạn đường được quy định là điểm phát tin. Từ điểm này các thành viên của đội chơi sẽ đượcđánh số lần lượt từ 1, 2,…,n dọc theo đoạn đường.Khi có hiệu lệnh, một thông tin sẽ được chuyển tới cho người số 1. Nhiệm vụ của người chơi là phảitruyền thông tin này cho tất cả các thành viên trong đội. Đội nào hoàn thành việc truyền tin nhanh nhất sẽthắng cuộc. Quá trình truyền tin phải tuân thủ các quy tắc sau đây1. Mỗi thành viên chỉ có thể di chuyển tới, lui dọc đoạn đường với tốc độ một đơn vị thời gian trên 1giây2. Mỗi thành viên có thể truyền tin cho thành viên tiếp theo nếu họ cách nhau không quá một khoảngcách K cho trước3. Sau khi nhận tin, mỗi thành viên có thể truyền tin ngay cho thành viên khác, khoảng thời gian từlúc nhận tin cho đến lúc truyền tin xem như bằng 0Viết chương trình xác định thời gian hoàn thành việc truyền tin ngắn nhất mà mỗi đội có thể thực hiệnđượcDữ liệu vào: Được lưu trong tập GAME.INP có cấu trúc như sau:- Dòng đầu tiên chứa số thự K (0 ≤ K ≤ 10

⁶

), khoảng cách tối đa mà hai thành viên có thể thực hiệnviệc truyền tin- Dòng thứ 2 chứa số nguyên N (1≤N≤10

⁵

), cho biết thành viên trong mỗi đội chơi- Mỗi dòng trong N dòng tiếp theo chứa một số thực D

i

(1≤D

i

≤10

⁹

; i=1,2,3,…,N) cho biết khoảngcách của thành viên thứ i so với điểm phát tinDữ liệu ra: Lưu vào tệp văn bản GAME.OUT chứa số thực cho biết thời gian ngắn nhất để hoàn thànhVí dụ: GAME.INP `GAME.OUT1.0002.00040.0004.0008.000SỞ GIÁO DỤC ĐÀO TẠO BẠC LIÊU