trang chủ / đề bài / icpc19_reg_f

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 t bit mỗi giây.

Có n loài mèo, đánh số từ 1 đến n. Ảnh của loài mèo thứ i có tỉ lệ nhu cầu là di. Đ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ứ i nên nhận được "phần công bằng" bằng di∑j=1ndj của tổng băng thông t.

Tuy nhiên, do giới hạn về hạ tầng, băng thông dành cho loài mèo thứ i phải nằm trong đoạn từ ai đến bi.

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 xi là băng thông dành cho việc tải ảnh loài mèo thứ i. Bạn cần tìm các số thực xi sao cho:

  • ai≤xi≤bi,
  • ∑i=1nxi=t,
  • Đặt yi=t·di∑j=1ndj (yi là băng thông "công bằng" nếu không có ràng buộc về ai và bi), giá trị ∑i=1n(xi−yi)2yi nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và t (1≤n≤105, 1≤t≤106).

Trong n dòng tiếp theo, dòng thứ i chứa ba số nguyên ai, bi và di (0≤ai≤bi≤106, 0<bi, 1≤di≤106).

Đả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 n dòng, dòng thứ i là băng thông dành cho việc tải ảnh loài mèo thứ i. Đá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á 10−6.

Cụ thể, với mỗi dòng, gọi số bạn in ra là a và đáp án của ban giám khảo là b. Đáp án của bạn được chấp nhận khi và chỉ khi |a−b|max(1,|b|)≤10−6.

Ràng buộc

  • 1≤n≤105, 1≤t≤106
  • 0≤ai≤bi≤106, 0<bi, 1≤di≤106
  • 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 13 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à 1. Phần còn lại chia theo tỉ lệ 2:1, nên loài thứ hai nhận 6 bit mỗi giây và loài thứ ba nhận 3 bit mỗi giây.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0