Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Babai rounding: giải CVP xấp xỉ

    Thuật toán làm tròn của Babai giải CVP xấp xỉ khi cơ sở vuông khả nghịch. Viết đích ttt theo cơ sở: t=x Bt = x\,Bt=xB với xxx hữu tỉ (giải hệ tuyến tính). Làm tròn từng thành phần về số nguyên gần nhất (quy ước 0.50{.}50.5 làm tròn lên), rồi trả về điểm lattice:

    v=⌊x⌉⋅B.v = \lfloor x \rceil \cdot B.v=⌊x⌉⋅B.

    Ví dụ: B=I2B=I_2B=I2​, t=(3,4)t=(3,4)t=(3,4): x=(3,4)x=(3,4)x=(3,4), v=(3,4)v=(3,4)v=(3,4).

    • Định dạng đầu vào:

      Dòng 1: n. Tiếp theo n dòng, mỗi dòng n số nguyên là cơ sở vuông B. Dòng cuối: n số của t.

    • Ràng buộc đầu vào:

      1≤n≤81 \le n \le 81≤n≤8; B khả nghịch; toạ độ nguyên trong [−50,50][-50,50][−50,50].

    • Định dạng đầu ra:

      Một dòng gồm n số nguyên là điểm lattice Babai.

    Ví dụ:

    Đầu vào:

    2
1 0
0 1
3 4

    Đầu ra:

    3 4

    Giải thích:

    x=(3,4) nguyên sẵn ⇒ điểm lattice (3,4).

    Đang tải editor...