Giải bài trực tuyến

Trong chiến dịch Điện Biên Phủ, công tác hậu cần đã góp phần to lớn làm nên chiến thắng lẫy lừng, chấn động năm châu, rung động địa cầu của dân tộc ta. Chiến dịch đã huy động tổng lực hàng ngàn phương tiện từ cơ giới đến thô sơ để vận chuyển hàng chục vạn tấn lương thực, đạn dược ra chiến trường. Trong đó đặc biệt phải kể đến con số dân công hòa tuyến lên đến 260 ngàn người (gấp 13 lần so với dự báo của Pháp), đóng góp 11 triệu ngày công. Các con số đó đã nói lên lòng yêu nước, tinh thần quyết chiến, quyết thắng của cả dân tộc trong chiến dịch lịch sử này. Điều đáng tiếc là hiệu quả vận chuyển nói chung là khá thấp, đặc biệt là vận chuyển lương thực bằng dân công gánh bộ, số lượng lương thực tới nơi nộp kho chỉ còn 8%. Nghĩ về con số này Vinh ước ao được góp sức cùng cha ông ngày đó nâng cao hiệu quả vận chuyển, và thế là Vinh thử giải bài toán sau đây:

Có Q lít xăng ở bể chứa của kho xăng đặt ở thôn Đoài. Độ dài đường vận chuyển từ thôn Đoài đến kho xăng của Ban hậu cần chiến dịch là L. Chỉ có một xe bồn để vận chuyển xăng. Bình xăng của xe chứa được K lít, mỗi km xe tiêu thụ 1 lít xăng. Trên đường vận chuyển xăng đến đích, có thể vận chuyển xăng đến các bể chứa đặt tại một số địa điểm trên đường vận chuyển. Bắt đầu từ thôn Đoài, cứ mỗi D km trên đường vận chuyển lại có một bể chứa. Giả thiết rằng sức chứa của tất cả các bể xăng (ở các điểm trung gian cũng như tại kho xăng của Ban hậu cần chiến dịch) tối thiểu là Q mà ban đầu chúng là các bể rỗng và xe có thể đổ xăng vào và lấy xăng ra khỏi các bể này. Cần tìm cách điều hành xe để vận chuyển được một lượng xăng lớn nhất từ bể chứa ở thôn Đoài đến kho xăng của Ban hậu cần chiến dịch.

Yêu cầu: Với các điều kiện đặt ra, hãy giúp Vinh tìm cách điều hành xe để vận chuyển được một lượng xăng lớn nhất từ bể chứa ở thôn Đoài đến kho xăng của Ban hậu cần chiến dịch.

Dữ liệu: Gồm một dòng duy nhất chứa 4 số nguyên L, Q, K, D được ghi cách nhau bởi dấu cách, trong đó:

• L (1 <= L <= 10⁹) – độ dài đường vận chuyển xăng từ thôn Đoài đến kho xăng của Ban hậu cần chiến dịch;
• Q (1 <= Q <= 10¹²) – lượng xăng có ở bể chứa đặt tại thôn Đoài;
• K (1 <= K <= 10⁹) – sức chứa của bình xăng (lít) của xe;
• D (1 <= D <= 10⁹) – khoảng cách giữa các bể chứa trung gian.

Kết quả: Ghi một số nguyên là số lượng lít xăng lớn nhất có thể vận chuyển từ thôn Đoài đến kho xăng của Ban hậu cần chiến dịch. Nếu như với những điều kiện đặt ra, xe không thể đến được kho xăng của Ban hậu cần chiến dịch thì ghi ra -1.

Ví dụ:

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài có L/D <= 10000.
• Có 50% số test ứng với 50% số điểm của không có hạn chế bổ sung đối với L, Q, K, D.