Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HVT_CAR - Đoàn xe qua cầu


Một đoàn xe hộ tống có N chiếc đi trên một đoạn đường một chiều đã được bố trí theo thứ tự từ 1 đến N. Mỗi một xe trong đoàn trên thì có một vận tốc là V và trọng lượng là W.
Khi đi qua một chiếc cầu có trọng tải không quá P thì phải chia đoàn xe trên thành các nhóm sao cho tổng khối lượng của mỗi một nhóm là không quá P. Thêm vào nữa là các nhóm phải đi tuần tự. Nghĩa là nhóm thứ i chỉ được đi khi mà toàn bộ xe của nhóm thứ i - 1 đã qua cầu.
Vận tốc đi của mỗi một nhóm là hoàn toàn khác nhau và phụ thuộc vào xe có tốc độ chậm nhất trong nhóm đó.
Hãy tìm cách chia đoàn xe thành các nhóm sao cho thời gian mà đoàn xe sang được cầu là nhỏ nhất có thể được.

Một đoàn xe hộ tống có N chiếc đi trên một đoạn đường một chiều đã được bố trí theo thứ tự từ 1 đến N. Mỗi một xe trong đoàn trên thì có một vận tốc là V và trọng lượng là W.

Khi đi qua một chiếc cầu có trọng tải không quá P thì phải chia đoàn xe trên thành các nhóm sao cho tổng khối lượng của mỗi một nhóm là không quá P. Thêm vào nữa là các nhóm phải đi tuần tự. Nghĩa là nhóm thứ i chỉ được đi khi mà toàn bộ xe của nhóm thứ i - 1 đã qua cầu.

Vận tốc đi của mỗi một nhóm là hoàn toàn khác nhau và phụ thuộc vào xe có tốc độ chậm nhất trong nhóm đó.

Hãy tìm cách chia đoàn xe thành các nhóm sao cho thời gian mà đoàn xe sang được cầu là nhỏ nhất có thể được.

Input

- Dòng đầu ghi 3 số N( N ≤ 1000)  P  và L thể hiện: cho số xe, trọng lượng tối đa của cầu và độ dài của cầu. ( P; L ≤10000)

- N dòng kế tiếp, mỗi dòng gồm 2 số W và V thể hiện cho trọng lượng và vận tốc của xe.

Output

- Dòng đầu là tổng thời gian nhỏ nhất để đoàn xe qua cầu chính xác đến hai chữ số phần thập phân.

Example
Input:

10    100   100

40   25

50   20

50   20

70   10

12   50

9    70

49   30

38   25

27   50

19   70 Output: 25.00
Giải thích
Các nhóm đi :
+ Nhóm 1 có 1 xe thời gian 100/25 = 4
+ Nhóm 2 có 2 xe (2,3)        100/20= 5
	+ Nhóm 3 có 3 xe (4,5,6)    100/10=10
	+ Nhóm 4 có 2 xe ( 7,8)      100/25=  4
	+ Nhóm 5 có 2 xe (9,10)     100/50 = 2
 Tổng thời gian qua cầu là 25 


Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2014-04-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:Sưu tầm

hide comments
2020-02-07 09:58:10
ai giup em bai nay voi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.