Đề thi Olimpic Tin học Lớp 11 và đáp án

Trên một hòn đảo có rất đông dân cư, người ta xây một con đường cao tốc chạy vòng quanh đảo. Để phục vụ xăng cho xe cộ chạy trên đường cao tốc đó, Chi cục xăng dầu quyết định đặt N cây xăng trong đó có một cây xăng làm trạm trung tâm để tiếp xăng cho các cây xăng còn lại.

Khoảng cách giữa cây xăng thứ i với cây xăng thứ i+1 là Di, khoảng cách từ cây xăng thứ n đến cây xăng thứ 1 là Dn. Sau khi thống kê và tính toán người ta thấy tại địa điểm đặt cây xăng i có nhu cầu L (lít/ngày) và chi phí trung bình để vận chuyển 1 lít xăng trên 1 km là 1 đồng.

Hãy tìm một trong N vị trí để đặt trạm xăng trung tâm sao cho tổng chi phí chuyên chở xăng (S) trong một ngày từ trạm trung tâm đến các cây xăng là bé nhất. Giả sử xăng ở trạm trung tâm luôn luôn đủ để cung cấp cho tất cả các cây xăng.