Chia sẻ băng thông công bằng
Đề bài
Mô tả
Với ước mơ cách mạng hóa ngành công nghệ và làm cho thế giới tốt đẹp hơn, Ging vừa chuyển đến Thung lũng Silicon để thành lập công ty khởi nghiệp của riêng mình, Katbook.
Katbook cho phép người dùng tải xuống ảnh mèo. Katbook có thể truyền bit mỗi giây.
Có loài mèo, đánh số từ đến . Ảnh của loài mèo thứ có tỉ lệ nhu cầu là . Điều này có nghĩa là, nếu không có ràng buộc nào khác, loài mèo thứ nên nhận được "phần công bằng" bằng của tổng băng thông .
Tuy nhiên, do giới hạn về hạ tầng, băng thông dành cho loài mèo thứ phải nằm trong đoạn từ đến .
Bạn vừa được Ging tuyển làm kỹ sư mạng ở Katbook. Nhiệm vụ đầu tiên của bạn là tìm cách phân bổ băng thông "công bằng" nhất thỏa mãn các ràng buộc trên. Cụ thể hơn, gọi là băng thông dành cho việc tải ảnh loài mèo thứ . Bạn cần tìm các số thực sao cho:
- ,
- ,
- Đặt ( là băng thông "công bằng" nếu không có ràng buộc về và ), giá trị nhỏ nhất có thể.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (, ).
Trong dòng tiếp theo, dòng thứ chứa ba số nguyên , và (, , ).
Đảm bảo tồn tại ít nhất một cách phân bổ hợp lệ. Có thể chứng minh rằng với các ràng buộc này, nghiệm tối ưu là duy nhất.
Dữ liệu ra
In ra dòng, dòng thứ là băng thông dành cho việc tải ảnh loài mèo thứ . Đáp án được chấp nhận khi và chỉ khi sai số tương đối hoặc tuyệt đối so với nghiệm tối ưu không vượt quá .
Cụ thể, với mỗi dòng, gọi số bạn in ra là và đáp án của ban giám khảo là . Đáp án của bạn được chấp nhận khi và chỉ khi .
Ràng buộc
- ,
- , ,
- Tồn tại ít nhất một cách phân bổ hợp lệ
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 10 0 10 1 0 10 1 0 10 1 |
3.33333333 3.33333333 3.33333333 |
Mỗi loài mèo nhận đúng phần công bằng, bằng tổng băng thông. |
| 3 10 0 1 1000 2 8 2 2 8 1 |
1.00000000 6.00000000 3.00000000 |
Loài mèo thứ nhất có nhu cầu lớn hơn nhiều và lẽ ra nhận gần hết băng thông, nhưng bị giới hạn tối đa là . Phần còn lại chia theo tỉ lệ , nên loài thứ hai nhận bit mỗi giây và loài thứ ba nhận bit mỗi giây. |
Bình luận