trang chủ / đề bài / icpcwf20_n

Vector của chúng ta là gì, Victor?

Đề bài

Mô tả

Vector nhúng (embedding) là một công cụ phổ biến trong các hệ thống học máy. Các khái niệm phức tạp của thế giới thực (ví dụ các từ trong từ điển) được ánh xạ thành các vector số thực. Nếu phép nhúng được huấn luyện tốt, các khái niệm liên quan sẽ nằm gần nhau trong không gian vector, nên những câu hỏi như "hai từ này có đồng nghĩa không?" có thể quy về các phép kiểm tra toán học đơn giản.

Bạn được Tiệm Kem Ngày Xưa thuê xây dựng một mô hình nhúng cho các hương vị kem, để khi hết một vị, tiệm có thể gợi ý cho khách những vị liên quan. Sau bốn tháng huấn luyện phép nhúng trên sáu trung tâm dữ liệu đám mây, cuối cùng bạn đã có mô hình hương vị hoàn hảo! Bạn đã sẵn sàng cách mạng hóa ngành kem trên con phố của mình và, dám nói luôn, cả khu phố! Cho đến khi bạn vô tình làm rơi ít kem miễn phí lên bàn phím và xóa mất một nửa dữ liệu. Tiệm không đủ tiền chi 30 tỷ rúp để huấn luyện lại mô hình, nên bạn đang gặp rắc rối.

May mắn là bạn vẫn còn nhiều kết quả huấn luyện nằm rải rác. Với một vector đã bị xóa, dữ liệu huấn luyện cho biết nó cách một số vector hương vị đã biết bao xa. Độ gần nhau của hai vector A và B chính là khoảng cách Euclid thông thường (tức là độ dài của vector A−B).

Hãy viết chương trình khôi phục một vector nhúng phù hợp với các kết quả huấn luyện.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên d và n: d là số chiều của các vector, n là số kết quả huấn luyện của vector bị xóa mà bạn muốn khôi phục.

Mỗi dòng trong n dòng tiếp theo mô tả một kết quả huấn luyện bằng d+1 số thực x1,…,xd và e: x1,…,xd là tọa độ của một vector đã biết, còn e là khoảng cách Euclid từ vector đó đến vector bị xóa.

Chương trình của bạn chỉ được chấm trên các ví dụ dưới đây và trên các input được sinh theo quy trình sau. Đầu tiên chọn d và n. Sau đó chọn ngẫu nhiên n vector input và 1 vector output, mỗi vector có d chiều; d·(n+1) tọa độ này độc lập và phân phối đều trong đoạn [−100;100]. Tiếp theo tính khoảng cách Euclid từ mỗi vector input đến vector output. Cuối cùng vector output bị bỏ đi. Mọi phép tính dùng số thực dấu phẩy động độ chính xác kép (double). Các số thu được theo quy trình này xuất hiện trong input với 17 chữ số sau dấu thập phân.

Dữ liệu ra

In ra d số thực, tọa độ của một vector bất kỳ có khoảng cách đến mỗi vector huấn luyện bằng khoảng cách đã cho, với sai số tuyệt đối hoặc tương đối không quá 10−5.

Ràng buộc

  • 1≤d≤500, 1≤n≤500.
  • −100≤xi≤100, 0≤e≤5000.

Ví dụ

Input Output Giải thích
2 3
0 0 2.5
3 0 2.5
1.5 0.5 2.5
1.5 -2 Điểm (1,5;−2) cách (0;0), (3;0) và (1,5;0,5) đúng 2,5.
2 2
0 0 2
4 -4 6
1.414213562373 1.414213562373 Điểm (2;2) cách (0;0) đúng 2 và cách (4;−4) đúng 6. Vector (−2;−2) cũng là một đáp án đúng.
4 3
0 1 2 3 2
1 2 -1 7 5
1 0.3 3.4 1.2 3.3
1 2 3 4 Có vô số đáp án, in vector nào thỏa mãn cũng được.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0