Đề bài

Cho hai vectơ \(v_1 = (x_1, x_2, ..., x_n)\) và \(v_2 = (y_1, y_2, ..., y_n)\). Tích vô hướng của hai vectơ này là một số duy nhất, được tính bằng \(x_1y_1 + x_2y_2 + ... + x_ny_n\).

Giả sử bạn được phép hoán vị các tọa độ của mỗi vectơ theo ý muốn. Hãy chọn hai hoán vị sao cho tích vô hướng của hai vectơ mới là nhỏ nhất có thể và xuất ra giá trị tích vô hướng tối thiểu đó.

Dữ liệu vào

Dòng đầu tiên của tệp dữ liệu vào chứa số nguyên \(T\) - số lượng bộ dữ liệu (test case). Với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa số nguyên \(n\).
• Hai dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên, lần lượt là tọa độ của \(v_1\) và \(v_2\).

Dữ liệu ra

Với mỗi bộ dữ liệu, xuất ra một dòng:

Case #X: Y

Ràng buộc

Phân nhóm

• Tập kiểm thử 1 (Small dataset - Công khai):
• \(T = 1000\)
• \(1 \le n \le 8\)
• \(-1000 \le x_i, y_i \le 1000\)
• Tập kiểm thử 2 (Large dataset - Ẩn):
• \(T = 10\)
• \(100 \le n \le 800\)
• \(-100000 \le x_i, y_i \le 100000\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Case #1: -25
Case #2: 6

Nguồn

Google Code Jam 2008, Vòng 1A, bài Minimum Scalar Product.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.