VOI 16 Bài 2 - Hậu cần

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VOI 2016 bài 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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.

Input

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 \leq L \leq 10^9)~ -- độ 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 \leq Q \leq 10^{12})~ -- lượng xăng có ở bể chứa đặt tại thôn Đoài;
  • ~K\: (1 \leq K \leq 10^9)~ -- sức chứa của bình xăng (lít) của xe;
  • ~D\: (1 \leq D \leq 10^9)~ -- khoảng cách giữa các bể chứa trung gian.

Output

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~.

Giới hạn

  • Có ~50~% số test ứng với ~50~% số điểm của bài có ~\frac{L}{D} \leq 10^4~.
  • 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~.

Sample Input 1

3 10 3 1

Sample Output 1

1

Sample Input 2

5 7 3 1

Sample Output 2

-1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.