Mã vạch
Đề bài
Mô tả
Code-11 là một hệ mã vạch dùng để mã hóa ký tự, chủ yếu dùng để dán nhãn thiết bị viễn thông. Các ký tự được mã hóa chỉ gồm các chữ số từ 0 đến 9, dấu gạch ngang ("-") và một ký tự đặc biệt start/stop xuất hiện ở đầu và cuối mỗi mã vạch Code-11.
Code-11 là một hệ rời rạc: mỗi ký tự được mã hóa độc lập. Mã của một ký tự gồm năm vùng liền nhau, gọi là các vạch, xen kẽ màu tối và màu sáng, bắt đầu bằng một vạch tối. Mỗi vạch hoặc hẹp hoặc rộng, theo bảng mã dưới đây, trong đó 0 là vạch hẹp và 1 là vạch rộng.
| Ký tự | Mã |
|---|---|
| 0 | 00001 |
| 1 | 10001 |
| 2 | 01001 |
| 3 | 11000 |
| 4 | 00101 |
| 5 | 10100 |
| 6 | 01100 |
| 7 | 00011 |
| 8 | 10010 |
| 9 | 10000 |
| - | 00100 |
| Start/Stop | 00110 |
Chẳng hạn, ký tự 1 được mã hóa bằng một vạch tối rộng, một vạch sáng hẹp, một vạch tối hẹp, một vạch sáng hẹp và cuối cùng là một vạch tối rộng. Mã vạch của các ký tự liên tiếp phải được ngăn cách bởi một vạch sáng hẹp, vạch này chỉ có tác dụng ngăn cách các ký tự.
Mã hóa hai độ rộng như Code-11 có ưu điểm là đơn giản. Vì chỉ cần phân biệt vạch hẹp với vạch rộng, Code-11 chấp nhận sai lệch in ấn khá lớn khi điều kiện in kém.
Để phát hiện lỗi, các mã vạch Code-11 trong bài này có thêm hai ký tự kiểm tra và ở cuối thông điệp (trước ký tự stop). Nếu ký tự cần mã hóa (từ trái sang phải) là thì trọng số của ký tự kiểm tra là
trong đó là trọng số của ký tự : trọng số của các chữ số 0 đến 9 là 0 đến 9, trọng số của dấu gạch ngang là 10. (Phép được thực hiện trước phép .)
Trọng số của ký tự kiểm tra là
trong đó là ký tự kiểm tra . Ký tự kiểm tra là ký tự có trọng số bằng giá trị tính được (trọng số 10 là dấu gạch ngang). Ví dụ, nếu thông điệp cần mã hóa là 123-45 thì ký tự kiểm tra là 5 và ký tự kiểm tra là 2. Mã vạch của tám ký tự 123-4552, đứng sau mã của ký tự start/stop và đứng trước mã của ký tự start/stop, tạo thành mã vạch Code-11 đầy đủ của thông điệp.
Các máy đọc mã vạch đơn giản đo cường độ ánh sáng phản xạ từ mã vạch lên một dãy thẳng gồm hàng trăm cảm biến CCD nhỏ, mỗi cảm biến báo sáng hoặc tối. Phần mềm giải mã xác định các vùng sáng và tối, rồi dùng độ rộng của từng vùng để kiểm tra mã vạch và lấy ra thông tin được mã hóa. Vì hướng của mã vạch không cố định, phần mềm phải giải mã được dù mã vạch được quét từ trái sang phải hay từ phải sang trái.
Nhiệm vụ của bạn là giải mã thông tin thu được khi quét một mã vạch Code-11, cho biết độ rộng của các vùng sáng và tối mà máy đọc phát hiện. Giả sử vạch rộng được thiết kế rộng gấp đôi vạch hẹp. Do máy in không đồng đều, độ rộng thực tế của một vạch có thể lớn hơn hoặc nhỏ hơn độ rộng thiết kế tối đa . Không có thông điệp độ dài (mã vạch chỉ gồm start/stop, các ký tự kiểm tra và các vạch ngăn cách).
Dữ liệu vào
Dữ liệu gồm nhiều bộ test, mỗi bộ là một lần quét. Mỗi bộ bắt đầu bằng số nguyên () là số vùng mà máy đọc phát hiện, tiếp theo là số nguyên (), là số cảm biến trong vùng thứ (trong một vùng, mọi cảm biến báo cùng một cường độ sáng). Dữ liệu của mỗi bộ bắt đầu và kết thúc bằng một vạch tối (không có khoảng sáng ở đầu hay ở cuối).
Sau bộ test cuối cùng là một dòng chứa duy nhất số .
Dữ liệu ra
Với mỗi bộ test, in một dòng gồm số thứ tự bộ test và kết quả giải mã, theo dạng Case i: <kết quả> (bộ test đánh số từ ). Nếu giải mã thành công, in dãy ký tự của thông điệp (không kèm các ký tự kiểm tra). Nếu giải mã thành công nhưng ký tự kiểm tra sai, in bad C. Nếu giải mã thành công, ký tự đúng nhưng ký tự kiểm tra sai, in bad K. In bad code nếu không giải mã được mã vạch do có độ rộng vạch nằm ngoài khoảng cho phép, thiếu hoặc sai ký tự start/stop, hoặc một điều kiện không hợp lệ khác. Làm theo đúng định dạng của ví dụ.
Ràng buộc
- , lẻ (mỗi lần quét bắt đầu và kết thúc bằng vạch tối).
- , mọi là số nguyên.
- Không có thông điệp độ dài .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 59 10 20 20 10 10 10 20 10 10 20 10 10 10 10 20 10 20 10 10 10 20 10 20 10 20 10 20 10 10 10 10 10 20 10 10 10 10 10 10 20 20 10 20 10 10 20 10 10 20 10 10 10 20 10 10 20 20 10 10 35 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 35 10 10 20 20 10 10 20 10 10 10 20 10 10 20 10 10 20 10 10 10 20 10 20 10 20 10 10 10 10 10 10 10 20 20 10 0 |
Case 1: 123-45 Case 2: bad code Case 3: bad K |
Lần quét 1 là mã vạch của thông điệp 123-45 (vạch hẹp 10, vạch rộng 20) với , . Lần quét 2 không có vạch rộng nào nên không có ký tự start/stop. Lần quét 3 đọc được start, 1, 2, 4, 9, stop: thông điệp 12 có đúng nhưng đúng phải là 0, không phải 9. |
| 29 20 40 40 20 20 20 20 20 20 40 40 20 40 20 20 20 40 20 40 20 20 20 40 20 20 38 42 21 19 29 20 40 40 20 20 20 20 20 20 40 40 20 40 20 20 20 40 20 40 20 20 20 40 20 20 38 43 21 19 29 10 10 20 20 10 10 20 10 10 10 20 10 10 20 10 10 20 10 10 10 20 10 20 10 10 10 20 20 10 0 |
Case 1: 1 Case 2: bad code Case 3: bad C |
Lần quét 1 là mã vạch của thông điệp 1 (, ) quét từ phải sang trái; với độ rộng thiết kế 20 cho vạch hẹp, các vạch hẹp 19, 21 và vạch rộng 38, 42 đều nằm đúng ở biên . Lần quét 2 có vạch rộng 43: cần và với độ rộng thiết kế của vạch hẹp, vô lý. Lần quét 3 là thông điệp 1 nhưng ký tự là 2 thay vì 1. |
Bình luận