solution

Thuật toán Luhn được dùng rộng rãi để sinh và kiểm tra chữ số kiểm tra (check digit) nhằm phát hiện lỗi nhập liệu khi xác thực số thẻ ngân hàng, mã định danh, IMEI, ...

Cho một chuỗi số gốc $S$ (chưa có chữ số kiểm tra), cần tìm chữ số $d \in \{0,\dots,9\}$ để khi thêm $d$ vào cuối $S$ (tạo thành $S' = S \| d$), chuỗi $S'$ thoả thuật toán Luhn:

• Đánh số vị trí các chữ số của $S'$ từ phải sang trái, bắt đầu từ 1 (vị trí 1 chính là $d$).
• Với mỗi chữ số ở vị trí chẵn (2, 4, 6, ...): nhân đôi giá trị; nếu kết quả $\ge 10$ thì trừ đi 9.
• Với mỗi chữ số ở vị trí lẻ (1, 3, 5, ...): giữ nguyên.
• Tổng tất cả các giá trị (sau biến đổi) của $S'$ phải chia hết cho 10.

Hãy in ra chuỗi $S' = S \| d$.

Ví dụ: $S =$ "7992739871" thì $d = 3$, kết quả in ra là "79927398713".