Nén bit
Đề bài
Mô tả
Mục đích của nén dữ liệu là giảm sự dư thừa trong dữ liệu được lưu trữ hoặc truyền đi. Điều này làm tăng mật độ dữ liệu thực tế và tăng tốc độ truyền dữ liệu. Một cách có thể dùng để nén một thông điệp nhị phân bất kỳ như sau:
Thay mỗi dãy cực đại gồm chữ số liên tiếp bằng biểu diễn nhị phân của , nếu việc thay thế đó làm thông điệp ngắn đi.
Ví dụ, dạng nén của dữ liệu 11111111001001111111111111110011 là 10000010011110011. Dữ liệu gốc dài bit, còn dữ liệu nén chỉ dài bit.
Nhược điểm của cách này là đôi khi quá trình giải nén cho ra nhiều hơn một kết quả, khiến ta không thể khôi phục được thông điệp gốc. Hãy viết chương trình xác định xem có khôi phục được thông điệp gốc từ dữ liệu nén hay không, khi biết độ dài của thông điệp gốc (), số chữ số trong thông điệp gốc () và dữ liệu nén.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test gồm hai dòng: dòng thứ nhất chứa hai số nguyên và , dòng thứ hai chứa dữ liệu nén (một xâu gồm các ký tự 0 và 1).
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ test, in một dòng gồm số thứ tự của bộ test (bắt đầu từ ) và một trong các thông báo YES, NO hoặc NOT UNIQUE, theo đúng định dạng như ví dụ:
YES: khôi phục được thông điệp gốc (có đúng một thông điệp phù hợp).NO: dữ liệu nén đã bị hỏng, không có thông điệp gốc nào phù hợp.NOT UNIQUE: có nhiều hơn một thông điệp có thể là thông điệp gốc.
Ràng buộc
- Thông điệp gốc dài không quá Kbyte: .
- .
- Dữ liệu nén dài từ đến bit.
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 32 26 10000010011110011 9 7 1010101 14 14 111111 0 0 |
Case #1: YES Case #2: NOT UNIQUE Case #3: NO |
Bộ 1: đây là ví dụ ở trên, với , chỉ có đúng một thông điệp phù hợp là 11111111001001111111111111110011. Bộ 2: có ba thông điệp dài với chữ số cho ra 1010101: 111110101 (đọc 101 là ), 101111101 và 101011111. Bộ 3: thông điệp gồm chữ số được nén thành 1110, không thể cho ra 111111. |
| 3 2 110 6 5 11011 4 3 10 0 0 |
Case #1: YES Case #2: NOT UNIQUE Case #3: NO |
Ví dụ tự thêm. Bộ 1: dãy 11 không được thay (biểu diễn nhị phân 10 của không ngắn hơn), nên 110 là thông điệp 110. Bộ 2: mỗi 11 có thể là 11 giữ nguyên hoặc là dạng nén của 111; với có hai thông điệp 110111 và 111011. Bộ 3: 10 chỉ có thể là 1 rồi 0 (dãy hai chữ số không bao giờ được nén thành 10), tức thông điệp 10 có , . |
Bình luận