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 nearest plane: CVP bằng GSO

    Thuật toán mặt phẳng gần nhất của Babai giải CVP tốt hơn phép làm tròn, dùng cơ sở trực giao Gram-Schmidt ba∗b^*_aba∗​. Duyệt các chiều từ cao xuống thấp; ở mỗi bước chiếu phần dư www lên ba∗b^*_aba∗​ và trừ đi bội nguyên gần nhất của bab_aba​:

    ca=⌊⟨w,ba∗⟩⟨ba∗,ba∗⟩⌉,w←w−ca ba.c_a = \Big\lfloor \frac{\langle w, b^*_a\rangle}{\langle b^*_a, b^*_a\rangle}\Big\rceil, \qquad w \leftarrow w - c_a\, b_a.ca​=⌊⟨ba∗​,ba∗​⟩⟨w,ba∗​⟩​⌉,w←w−ca​ba​.

    Điểm lattice trả về là v=t−wcuoˆˊiv = t - w_{\text{cuối}}v=t−wcuoˆˊi​. Quy ước 0.50{.}50.5 làm tròn lên.

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

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

      Dòng 1: k dim. Tiếp theo k dòng cơ sở B. Dòng cuối: dim số của đích t.

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

      1≤k=dim≤61 \le k = dim \le 61≤k=dim≤6; cơ sở độc lập tuyến tính; toạ độ nguyên trong [−30,30][-30,30][−30,30].

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

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

    Ví dụ:

    Đầu vào:

    2 2
1 0
0 1
3 4

    Đầu ra:

    3 4

    Giải thích:

    Cơ sở trực chuẩn: mỗi chiều làm tròn thẳng (3,4).

    Đang tải editor...