trang chủ / đề bài / icpcwf17_f

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ừ 0 đến 255, 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ừ 0 đến 255 ở kênh đỏ, ảnh sau khi giảm màu chỉ cho phép tối đa k 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 k 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ó n điểm ảnh với cường độ đỏ ban đầu r1,…,rn và k số nguyên được phép v1,…,vk, tổng bình phương sai số được định nghĩa là

∑i=1nmin1≤j≤k(ri−vj)2.

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ố k 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 d là số giá trị đỏ khác nhau xuất hiện trong ảnh gốc, và k là số giá trị đỏ khác nhau được phép trong ảnh sau khi giảm màu.

Mỗi dòng trong d dòng tiếp theo chứa hai số nguyên r và p, trong đó r là một cường độ đỏ và p là số điểm ảnh có cường độ đỏ bằng r. 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 k giá trị nguyên được phép một cách tối ưu.

Ràng buộc

  • 1≤d≤256, 1≤k≤d.
  • 0≤r≤255, 1≤p≤226.

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 v1=83: sai số là 20000·332+10000·672=21780000+44890000=66670000.
2 2
50 20000
150 10000
0 Chọn hai giá trị 50 và 150, mọi điểm ảnh giữ nguyên màu.
4 2
0 30000
25 30000
50 30000
255 30000
37500000 Chọn 25 và 255: ba giá trị đầu dồn về 25, sai số 30000·(252+0+252)=37500000.

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