Đề bài
Một bức ảnh là một lưới điểm ảnh (pixel), mỗi pixel được lưu bằng một số nguyên đóng gói màu của nó: red × 65536 + green × 256 + blue, mỗi kênh từ 0 đến 255 (mã màu hex #FF8000 ứng với số nguyên 16744448). Để chuyển ảnh sang màu xám, ta gán cho mỗi pixel cùng một giá trị g ở cả ba kênh, với g là độ sáng của pixel đó:
g = (299 × red + 587 × green + 114 × blue) / 1000, làm tròn đến số nguyên gần nhất, trường hợp đúng nửa thì làm tròn lên.
Nếu chỉ dùng số nguyên, công thức trên trở thành g = (299 × red + 587 × green + 114 × blue + 500) / 1000 với phép chia lấy phần nguyên.
Hãy viết grayscale_filter(pixels).
Đầu vào
pixels: Bức ảnh, mỗi hàng là một danh sách. Các hàng có thể dài ngắn khác nhau.
Đầu ra
Trả về một lưới có cùng hình dạng, trong đó mỗi pixel là g × 65536 + g × 256 + g. Ảnh rỗng thì trả về lưới rỗng.
Ràng buộc
0 ≤ số hàng ≤ 50, 0 ≤ số pixel mỗi hàng ≤ 50
0 ≤ mỗi pixel ≤ 16,777,215
Ví dụ
Đầu vào:
pixels = [
[16744448, 255]
]
Kết quả mong đợi:
expected = [
[9934743, 1907997]
]
Đầu vào:
std::vector<std::vector<long long>> pixels = {
{16744448, 255}
};
Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
{9934743, 1907997}
};
Đầu vào:
long[][] pixels = new long[][] {
new long[] {16744448, 255}
};
Kết quả mong đợi:
long[][] expected = new long[][] {
new long[] {9934743, 1907997}
};
Giải thích
#FF8000 có red 255, green 128, blue 0: (76245 + 75136 + 0 + 500) / 1000 = 151, cho ra 151 × 65793 = 9934743. Màu lam thuần 255 cho (29070 + 500) / 1000 = 29, tức là 1907997.
Đầu vào:
pixels = [
[0, 16777215],
[8421504, 65280]
]
Kết quả mong đợi:
expected = [
[0, 16777215],
[8421504, 9868950]
]
Đầu vào:
std::vector<std::vector<long long>> pixels = {
{0, 16777215},
{8421504, 65280}
};
Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
{0, 16777215},
{8421504, 9868950}
};
Đầu vào:
long[][] pixels = new long[][] {
new long[] {0, 16777215},
new long[] {8421504, 65280}
};
Kết quả mong đợi:
long[][] expected = new long[][] {
new long[] {0, 16777215},
new long[] {8421504, 9868950}
};
Giải thích
Màu đen vẫn là 0 và màu trắng vẫn là 16777215. Màu xám #808080 giữ nguyên 128 (8421504), còn màu lục thuần cho (149685 + 500) / 1000 = 150, tức là 9868950.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Red là (pixel / 65536) % 256, green là (pixel / 256) % 256 và blue là pixel % 256; dùng phép dịch bit và mặt nạ bit cũng được.
Gợi ý 2
Cộng thêm 500 trước khi chia cho 1000 sẽ làm tròn lên ở trường hợp đúng nửa.
Gợi ý 3
Khi đóng gói lại, đặt cùng một giá trị xám vào cả ba kênh.
Độ phức tạp mong đợi
thời gian O(rows × columns), bộ nhớ phụ O(rows × columns)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.