Mô tả
Trung tâm dữ liệu NAS Long Thành mỗi ngày nhận hàng nghìn gói tin từ các trạm cảm biến. Để tránh nhiễu đường truyền, kỹ sư phòng vận hành áp dụng một quy trình mã hóa đơn giản: lấy thông điệp gốc (một số nguyên không âm), dịch phải đi k bit, sau đó XOR kết quả với một mặt nạ m để tạo ra gói tin đã mã hóa. Trong phòng máy, quy trình này gọi là "dịch phải k lần với mặt nạ lẫn".
Nhiệm vụ của bạn là viết chương trình khôi phục lại thông điệp gốc từ gói tin đã mã hóa, biết trước số lần dịch k và mặt nạ m dùng trong phiên truyền đó.
Quy tắc mã hóa (đã được phòng vận hành xác nhận):
- Lấy thông điệp gốc
x. - Tính
shifted = x >> k(dịch phảikbit, các bit bên phải bị loại bỏ). - Tính
encoded = shifted ^ m(XOR bitwise với mặt nạm).
Bạn cần làm ngược lại: cho encoded, k, m, hãy tìm x.
Quan trọng: vì bước dịch phải làm mất k bit thấp nhất của x, nên với mỗi encoded có thể tồn tại nhiều x cho ra cùng kết quả. Phòng vận hành yêu cầu chọn x nhỏ nhất không âm thỏa mãn điều kiện mã hóa, đảm bảo tính chuẩn hóa khi nạp vào kho dữ liệu.
Đầu vào
Ba số nguyên không âm encoded, k, m, cách nhau bởi khoảng trắng — lần lượt là gói tin đã mã hóa, số lần dịch phải và mặt nạ XOR.
encoded:0 ≤ encoded ≤ 10^9k:0 ≤ k ≤ 30m:0 ≤ m ≤ 10^9
Đầu ra
In ra một số nguyên duy nhất — thông điệp gốc x nhỏ nhất không âm thỏa mãn (x >> k) ^ m == encoded.