Nỗi buồn
Đề bài
Mô tả
Chúc mừng Doggie!
(Demen)
Doggie làm việc với các hỗn hợp lỏng gồm Thủy ngân (Hg) và Tacos (Ts). Một hỗn hợp được biểu diễn bởi cặp chứa gam Hg và gam Ts.
Doggie đang có sẵn hỗn hợp. Anh ấy cũng có thể mua thêm một số lượng hữu hạn bất kỳ các hỗn hợp mới. Mua một hỗn hợp chứa gam Hg và gam Ts tốn chi phí , trong đó và có thể là các số thực không âm bất kỳ. Trong phần dưới đây, hỗn hợp thứ (có sẵn hoặc mua thêm) chứa gam Hg và gam Ts.
Để tạo ra một hỗn hợp, Doggie lấy một tỉ lệ một cách độc lập từ mỗi hỗn hợp mà anh ấy sở hữu, dù là hỗn hợp có sẵn hay hỗn hợp mua thêm. Các tỉ lệ không cần có tổng bằng . Kết quả chứa đúng gam Hg và gam Ts.
Doggie đang cân nhắc hỗn hợp mục tiêu có thể dùng cho thí nghiệm của mình, nhưng anh ấy chưa quyết định sẽ tạo ra hỗn hợp nào. Trong giai đoạn thí nghiệm sau này, cửa hàng sẽ không còn hỗn hợp nào để bán, nên anh ấy không thể mua thêm. Anh ấy muốn mua đủ ngay bây giờ để đảm bảo có thể tạo ra bất kỳ mục tiêu nào mà mình chọn sau này. Anh ấy sẽ chỉ tạo ra một mục tiêu, và có thể chọn các tỉ lệ sau khi đã quyết định tạo mục tiêu nào. Kết quả phải chứa đúng lượng Hg và lượng Ts của mục tiêu đó.
Hãy giúp Doggie chọn các hỗn hợp cần mua sao cho mọi mục tiêu đều có thể được tạo ra, đồng thời tổng chi phí của các hỗn hợp mua thêm là nhỏ nhất.
Dữ liệu vào
Dòng đầu tiên chứa bốn số nguyên , , và (; ).
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (): số gam Hg và Ts trong một hỗn hợp có sẵn.
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (): số gam Hg và Ts trong một hỗn hợp mục tiêu.
Dữ liệu ra
In ra một số thực: tổng chi phí nhỏ nhất để mua các hỗn hợp mới.
Đáp án của bạn được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá . Cụ thể, gọi đáp án của bạn là và đáp án của ban giám khảo là ; đáp án được chấp nhận khi và chỉ khi .
Ràng buộc
- .
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 1 1 1 2 3 4 5 6 7 8 9 10 80 80 100 100 |
145.000000000000 | Năm hỗn hợp có sẵn chứa tổng cộng gam Hg và gam Ts. Nếu sau này Doggie chọn mục tiêu chứa gam mỗi chất, anh ấy cần thêm ít nhất gam Hg và gam Ts, nên phải tốn ít nhất . Doggie có thể mua một hỗn hợp chứa đúng gam Hg và gam Ts. Nếu chọn mục tiêu , anh ấy dùng toàn bộ sáu hỗn hợp; nếu chọn mục tiêu , anh ấy dùng của mỗi hỗn hợp. Vậy đáp án là . |
| 3 3 3 1 6 4 0 0 0 2 2 1 1 3 4 5 |
1.833333333333 | Đáp án là . |
Bình luận