Chủ tịch K giữ bí mật một ma trận đối xứng \(A\) kích thước \(N\times N\), với các chỉ số từ \(0\) đến \(N-1\) và \(A_{i,i}=0\). Xem \(A_{i,j}\) là trọng số cạnh \(i,j\) của đồ thị vô hướng đầy đủ. Gọi \(X\) là tổng trọng số cây khung nhỏ nhất.

Giá trị \(X\) cũng có thể được xác định bằng quá trình sau. Ban đầu đặt \(x=0\) và tạo đồ thị \(G\) gồm \(N\) đỉnh \(0,1,\ldots,N-1\), chưa có cạnh. Lặp lại \(N-1\) lần:

1. Gọi các đỉnh đang đi đến được từ đỉnh \(0\) là đỉnh gần, các đỉnh còn lại là đỉnh xa. Chọn đỉnh gần \(i\) và đỉnh xa \(j\) sao cho \(A_{i,j}N^2+iN+j\) nhỏ nhất. Luôn có ít nhất một đỉnh mỗi loại và cặp \((i,j)\) được xác định duy nhất.
2. Thêm cạnh nối \(i,j\) vào \(G\).
3. Cộng \(A_{i,j}\) vào \(x\).

Sau \(N-1\) lần lặp, \(X\) là giá trị của \(x\).

Có \(R=\lfloor5120/N\rfloor\) vòng, mỗi vòng có \(N\) người chơi. Trong vòng \(r\), các người chơi \((r,0),(r,1),\ldots,(r,N-1)\) lần lượt tương tác theo thứ tự chỉ số tăng dần. Người chơi \((r,i)\) chỉ biết hàng \(A_i\) của ma trận và \(N\) thông điệp 64-bit nhận từ vòng trước; ở vòng \(0\), cả \(N\) thông điệp đều bằng \(0\). Người chơi hoặc trả lời \(X\) để kết thúc game ngay lập tức, hoặc gửi một thông điệp 64-bit đến từng người chơi của vòng sau. Nếu hết vòng \(R-1\) mà không ai trả lời đúng thì game thất bại. Hãy cài đặt chiến lược để game thành công trong ít vòng nhất có thể.

Đây là bài Communication. Bài nộp C++ phải #include "multi.h" và hiện thực hàm strategy, không viết main. Khi chấm trên LQDOJ, chương trình được chạy trong hai tiến trình cô lập. Hàm chiến lược chỉ được dựa vào các đối số, không được dựa vào trạng thái dùng chung giữa các tiến trình. Không được giao tiếp bằng stdin, stdout hoặc tệp khác; được ghi thông tin gỡ lỗi vào stderr.

Bạn phải hiện thực hàm sau:

std::vector<unsigned long long> strategy(
    int N, int r, int i,
    std::vector<unsigned long long> A,
    std::vector<unsigned long long> B
);

• Nếu đã xác định \(X\), trả về vector độ dài \(1\) chứa \(X\).
• Nếu chưa trả lời, trả về vector độ dài \(N\); phần tử \(j\) là thông điệp gửi đến người chơi \((r+1,j)\). Quy tắc này vẫn áp dụng ở vòng \(R-1\), dù vòng sau không có người chơi.
• Với cùng tham số, hàm phải luôn trả về cùng kết quả.

Trong lời gọi strategy, A[j] là \(A_{i,j}\) và B[j] là thông điệp từ người chơi \((r-1,j)\) gửi cho người chơi \((r,i)\). Mỗi vector có đúng \(N\) phần tử. Ở vòng \(0\), mọi phần tử của B bằng \(0\). Người chơi có thể thống nhất chiến lược trước khi trò chơi bắt đầu, nhưng không được giao tiếp ngoài các thông điệp đã mô tả. Nếu có người trả lời sai \(X\), trò chơi kết thúc thất bại ngay.

Các điều kiện bị chấm sai là:

• Wrong Answer [1]: vector trả về có độ dài khác \(1\) và \(N\).
• Wrong Answer [2]: giá trị \(X\) được trả lời không đúng.
• Wrong Answer [3]: không ai trả lời trước khi vòng \(R-1\) kết thúc.
• Wrong Answer [4]: hàm trả về các giá trị khác nhau khi được gọi với cùng bộ đối số.

Các đối số được bảo đảm có thể xuất hiện khi chơi với một ma trận \(A\) và hàm strategy đã nộp. Được phép khai báo hàm phụ và biến toàn cục, nhưng giá trị trả về không được phụ thuộc vào lần gọi trước hoặc tính ngẫu nhiên lúc chạy.

Biên dịch và chạy thử

Để chạy thử, đặt multi.cpp, multi.h và trình mẫu grader.cpp trong cùng thư mục rồi biên dịch bằng:

g++ -std=gnu++20 -O2 -o grader grader.cpp multi.cpp

Có thể dùng sh compile.sh thay cho lệnh trên. Nếu biên dịch thành công, tệp thực thi grader được tạo ra. Trình mẫu chạy trong một tiến trình và khác trình chấm thật. Chỉ trình mẫu đọc stdin và ghi stdout; các hàm của bài nộp vẫn phải tuân thủ quy tắc không giao tiếp bằng các luồng này.

Đầu vào của trình mẫu bắt đầu bằng số ván \(T\). Với mỗi ván, nhập dữ liệu theo dạng:

N
A_0,1 A_0,2 ... A_0,N-1
A_1,2 A_1,3 ... A_1,N-1
...
A_N-2,N-1

Trình mẫu in \(T\) dòng. Nếu ván thứ \(t\) thành công, dòng thứ \(t\) có dạng Accepted: 22, trong đó số là số vòng đã dùng. Nếu vi phạm điều kiện chấm sai, dòng đó có dạng Wrong Answer [4], với mã lỗi tương ứng. Nếu nhiều điều kiện cùng bị vi phạm, chỉ một điều kiện được báo.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của strategy, không đọc stdin. Định dạng dữ liệu để chạy thử với trình mẫu được mô tả ở trên.

Dữ liệu ra

Submission không có standard output. Kết quả được trả qua vector của strategy.

Ràng buộc

• \(2\le N\le256\).
• \(0\le A_{i,j}<2^{48}\).
• \(A_{i,i}=0\) và \(A_{i,j}=A_{j,i}\).
• Mỗi thông điệp là số nguyên trong \([0,2^{64})\).
• Trong một lần chạy, grader có thể chơi nhiều game và gọi strategy nhiều nhất \(10\,240\) lần.
• Các lời gọi strategy không nhất thiết xuất hiện theo thứ tự vòng tăng dần; kết quả chỉ được phụ thuộc vào đúng năm đối số của lời gọi.

Phân nhóm

Trong mỗi phân nhóm, nếu có testcase không hợp lệ, quá thời gian hoặc trả lời sai thì được \(0\) điểm. Nếu mọi testcase hợp lệ, đặt \(S\) là số vòng lớn nhất trong các game của phân nhóm. Nếu trả lời ở vòng \(r\) thì số vòng đã dùng là \(r+1\). Lỗi thực thi hoặc vượt giới hạn bộ nhớ trong bất kỳ test nào cũng làm điểm phân nhóm bằng \(0\).

Với phân nhóm 3, luôn nhận đủ điểm khi mọi game hợp lệ. Nếu \(S>6\), trang thi chính thức có thể hiển thị Output is partially correct, nhưng điều này không làm thay đổi điểm phân nhóm \(3\). Với các phân nhóm khác: \(S\le6\) nhận \(100\%\) điểm; \(7\le S\le9\) nhận \((100-20(S-6))\%\); \(10\le S\le19\) nhận \((40-S)\%\); \(S\ge20\) nhận \(20\%\).

1. \(5\) điểm: \(N\le64\), mọi \(A_{i,j}\le1\).
2. \(10\) điểm: mọi \(A_{i,j}\le1\).
3. \(15\) điểm: \(N\le64\).
4. \(40\) điểm: mọi \(A_{i,j}<2^{20}\).
5. \(15\) điểm: mọi \(A_{i,j}<2^{40}\).
6. \(15\) điểm: không có ràng buộc thêm.

Ví dụ giao tiếp

Sample grader nhận một game có \(N=3\) qua dữ liệu vào sau:

1
3
1 2
3

Sau dòng \(T=1\) và dòng \(N=3\), các dòng còn lại là tam giác trên của ma trận.

grader ghi nhận chuỗi lời gọi và giá trị trả về minh họa sau:

Trong vòng \(0\), người chơi \((0,0)\) gửi lần lượt các giá trị \(0,1,2\) đến \((1,0),(1,1),(1,2)\); người chơi \((0,1)\) gửi \(3,4,5\) đến ba người chơi đó theo cùng thứ tự; người chơi \((0,2)\) gửi \(6,7,8\) theo cùng thứ tự. Chưa ai trả lời nên trò chơi chuyển sang vòng \(1\). Người chơi \((1,0)\) nhận lần lượt \(0,3,6\) từ ba người chơi vòng trước và trả lời đúng \(X=3\). Trò chơi kết thúc thành công ngay lúc đó, sau \(2\) vòng.

Ví dụ này thỏa mãn các bài toán con \(3,4,5,6\). Khi chạy thử, sample-01-in.txt tương ứng với ví dụ này; sample-02-in.txt thỏa mọi bài toán con; sample-03-in.txt thỏa các bài toán con \(3,4,5,6\); sample-04-in.txt thỏa các bài toán con \(4,5,6\).

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 1, bài Multi Communication 2, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.