trang chủ / đề bài / icpcwf24_a

Biển quảng cáo

Đề bài

Mô tả

Mỗi năm, ICPC (International Collegiate Programming Contest) có rất nhiều nhà tài trợ. Nhà tài trợ vui thì cuộc thi mới vui, nên ban tổ chức dự định dựng một tấm biển quảng cáo dài ở một bên khu vực thi, để các nhà tài trợ đáng yêu có thể đặt quảng cáo lên đó.

Có tổng cộng n nhà tài trợ tuyệt vời, nên để công bằng, ban tổ chức muốn chia cho mỗi nhà tài trợ 1/n diện tích của tấm biển. Tuy nhiên, việc này phức tạp hơn vì mỗi nhà tài trợ có thể đánh giá các phần của tấm biển khác nhau.

Chẳng hạn, có nhà tài trợ muốn đặt quảng cáo gần lối vào khu vực thi, có thể nằm ở góc, nơi mọi thí sinh chắc chắn nhìn thấy khi bước vào. Mặt khác, có nhà tài trợ lại chỉ muốn đặt quảng cáo ở giữa, chỗ dễ được lên sóng livestream hơn. (Đừng hỏi chuyện gì xảy ra nếu lối vào nằm ở giữa! Đó chỉ là một ví dụ thôi.)

Sau khi nói chuyện với tất cả các nhà tài trợ, ban tổ chức thấy rằng mức ưa thích của mỗi nhà tài trợ có thể mô hình hóa bằng một hàm tuyến tính từng khúc liên tục, với miền xác định là chiều dài tấm biển. Với thông tin này, ban tổ chức muốn chia tấm biển thành n đoạn và trao cho n nhà tài trợ, sao cho mỗi nhà tài trợ nhận được ít nhất 1/n giá trị của tấm biển theo đánh giá của chính họ. Nói cách khác, diện tích dưới đồ thị hàm giá trị của mỗi nhà tài trợ trên đoạn họ nhận phải ít nhất bằng 1/n tổng diện tích dưới đồ thị hàm giá trị của chính họ.

Ví dụ thứ nhất: tấm biển dài 10 và có hai nhà tài trợ, Orakle Software và Hal++, hàm giá trị của mỗi bên chỉ gồm một khúc. Hàm giá trị của Orakle cho thấy công ty này càng thích các phần của tấm biển càng về bên phải (tăng từ 0 ở vị trí 0 lên 5 ở vị trí 10), còn hàm của Hal++ thì ngược lại (giảm từ 10 xuống 0). Diện tích dưới mỗi hàm là tổng giá trị của tấm biển theo góc nhìn của từng nhà tài trợ. Nếu cắt tấm biển ở chính giữa (vị trí 5), giao nửa trái cho Hal++ và nửa phải cho Orakle, thì mỗi bên nhận được hơn một nửa tổng diện tích của mình, nên đây là một cách chia hợp lệ. Còn nhiều cách chia hợp lệ khác (ví dụ cắt ở vị trí 4 hoặc 6 cũng được, nếu trao đúng các đoạn cho đúng nhà tài trợ).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên: n (1≤n≤5000), số nhà tài trợ (đánh số từ 1 đến n), và l (1≤l≤106), chiều dài tấm biển.

Mỗi dòng trong n dòng tiếp theo bắt đầu bằng số nguyên m (2≤m≤5000), số điểm xác định hàm giá trị của nhà tài trợ đó. Phần còn lại của dòng chứa m cặp số nguyên (a1,b1),…,(am,bm) (0=a1<a2<…<am=l, 0≤bi≤100), mỗi cặp là một đầu mút của một khúc của hàm tuyến tính từng khúc. Tổng tất cả các m không vượt quá 500000, và mỗi nhà tài trợ có ít nhất một bi dương.

Dữ liệu ra

In ra n cặp số (li,fi) (1≤i≤n), nghĩa là đoạn [li−1,li] của tấm biển được trao cho nhà tài trợ fi (quy ước l0=0, l0<l1<l2<…<ln, và ln phải bằng l). Các giá trị fi phải là số nguyên trong đoạn [1,n] và mỗi số nguyên xuất hiện đúng một lần, còn các li có thể là số thực. Nếu có nhiều cách chia, in ra cách bất kỳ. Nếu không có cách chia nào, in ra impossible.

Bạn không cần tối ưu gì thêm, chỉ cần mỗi nhà tài trợ nhận được ít nhất 1/n tổng diện tích của mình. Diện tích mỗi nhà tài trợ nhận được được phép nhỏ hơn 1/n tổng diện tích của họ nếu sai số tuyệt đối hoặc tương đối không quá 10−8.

Ràng buộc

  • 1≤n≤5000, 1≤l≤106.
  • 2≤m≤5000, tổng các m không vượt quá 500000.
  • 0=a1<a2<…<am=l, 0≤bi≤100; mỗi nhà tài trợ có ít nhất một bi>0.

Ví dụ

Input Output Giải thích
2 10
2 0 0 10 5
2 0 10 10 0
5 2
10 1
Tổng giá trị của Orakle (nhà tài trợ 1) là 25, của Hal++ (nhà tài trợ 2) là 50. Hal++ nhận [0,5] với giá trị 37,5≥25, Orakle nhận [5,10] với giá trị 18,75≥12,5.
5 100
5 0 0 10 0 20 1 30 0 100 0
5 0 0 10 0 20 1 30 0 100 0
5 0 0 10 0 20 1 30 0 100 0
5 0 0 10 0 20 1 30 0 100 0
5 0 0 10 0 20 1 30 0 100 0
16.3245553203 1
18.9442719100 2
21.0557280900 3
23.6754446797 4
100 5
Năm nhà tài trợ có cùng hàm giá trị: một "tam giác" trên [10,30] với đỉnh cao 1 tại 20, tổng diện tích 10. Mỗi đoạn chứa đúng diện tích 2 dưới tam giác nà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