Giảm màu
Đề bài
Mô tả
Mỗi điểm ảnh trong một bức ảnh kỹ thuật số có thể được biểu diễn bằng ba số nguyên trong đoạn từ đến , cho biết cường độ của các màu đỏ, xanh lá và xanh dương. Để nén ảnh hoặc tạo hiệu ứng nghệ thuật, nhiều công cụ chỉnh sửa ảnh có thao tác "giảm màu" (posterize) hoạt động như sau. Mỗi kênh màu được xét riêng; bài toán này chỉ quan tâm đến kênh màu đỏ. Thay vì cho phép mọi số nguyên từ đến ở kênh đỏ, ảnh sau khi giảm màu chỉ cho phép tối đa số nguyên trong đoạn này. Cường độ đỏ ban đầu của mỗi điểm ảnh được thay bằng số gần nó nhất trong các số được phép. Công cụ chỉnh sửa ảnh chọn tập số nguyên sao cho tổng bình phương sai số trên mọi điểm ảnh của ảnh gốc là nhỏ nhất.
Nếu có điểm ảnh với cường độ đỏ ban đầu và số nguyên được phép , tổng bình phương sai số được định nghĩa là
Nhiệm vụ của bạn là tính tổng bình phương sai số nhỏ nhất có thể đạt được, khi biết tham số và mô tả cường độ đỏ của các điểm ảnh trong một bức ảnh.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên là số giá trị đỏ khác nhau xuất hiện trong ảnh gốc, và là số giá trị đỏ khác nhau được phép trong ảnh sau khi giảm màu.
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và , trong đó là một cường độ đỏ và là số điểm ảnh có cường độ đỏ bằng . Các dòng này được cho theo thứ tự tăng dần của giá trị đỏ.
Dữ liệu ra
In ra tổng bình phương sai số khi chọn tập giá trị nguyên được phép một cách tối ưu.
Ràng buộc
- , .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 50 20000 150 10000 |
66670000 | Chỉ được dùng một giá trị; chọn : sai số là . |
| 2 2 50 20000 150 10000 |
0 | Chọn hai giá trị và , mọi điểm ảnh giữ nguyên màu. |
| 4 2 0 30000 25 30000 50 30000 255 30000 |
37500000 | Chọn và : ba giá trị đầu dồn về , sai số . |
Bình luận