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 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ợ 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 đoạn và trao cho nhà tài trợ, sao cho mỗi nhà tài trợ nhận được ít nhất 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 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 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ừ ở vị trí lên ở vị trí ), còn hàm của Hal++ thì ngược lại (giảm từ xuống ). 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í ), 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í hoặc 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: (), số nhà tài trợ (đánh số từ đến ), và (), chiều dài tấm biển.
Mỗi dòng trong dòng tiếp theo bắt đầu bằng số nguyên (), 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 cặp số nguyên (, ), 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 không vượt quá , và mỗi nhà tài trợ có ít nhất một dương.
Dữ liệu ra
In ra cặp số (), nghĩa là đoạn của tấm biển được trao cho nhà tài trợ (quy ước , , và phải bằng ). Các giá trị phải là số nguyên trong đoạn và mỗi số nguyên xuất hiện đúng một lần, còn các 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 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 tổng diện tích của họ nếu sai số tuyệt đối hoặc tương đối không quá .
Ràng buộc
- , .
- , tổng các không vượt quá .
- , ; mỗi nhà tài trợ có ít nhất một .
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ợ ) là , của Hal++ (nhà tài trợ ) là . Hal++ nhận với giá trị , Orakle nhận với giá trị . |
| 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 với đỉnh cao tại , tổng diện tích . Mỗi đoạn chứa đúng diện tích dưới tam giác này. |
Bình luận