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] CVP đơn giản: điểm lattice gần đích nhất

    Closest Vector Problem (CVP): cho vector đích ttt, tìm điểm lattice gần ttt nhất theo khoảng cách Euclid. Vét cạn hệ số trong [−C,C][-C,C][−C,C]:

    v=∑aca ba,cực tiểu ∥v−t∥2.v = \sum_{a} c_a\, b_a, \qquad \text{cực tiểu } \lVert v - t\rVert^2.v=∑a​ca​ba​,cực tiểu ∥v−t∥2.

    Nếu có nhiều điểm cùng khoảng cách, chọn điểm ứng với vector hệ số nhỏ nhất theo thứ tự từ điển.

    Ví dụ: cơ sở (1,0),(0,1)(1,0),(0,1)(1,0),(0,1), t=(3,4)t=(3,4)t=(3,4): điểm gần nhất là (3,4)(3,4)(3,4).

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

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

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

      1≤k≤51 \le k \le 51≤k≤5; 1≤dim≤61 \le dim \le 61≤dim≤6; 1≤C≤51 \le C \le 51≤C≤5.

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

      Một dòng gồm dim số nguyên là toạ độ điểm lattice gần nhất.

    Ví dụ:

    Đầu vào:

    2 2 5
1 0
0 1
3 4

    Đầu ra:

    3 4

    Giải thích:

    Với cơ sở chuẩn, điểm gần (3,4) nhất chính là (3,4), khoảng cách 0.

    Đang tải editor...