Chúng ta xây dựng một mạng xã hội gồm \(n\) thành viên, được đánh số \(0, \ldots, n-1\). Một số cặp thành viên sẽ là bạn bè. Nếu thành viên \(x\) trở thành bạn của thành viên \(y\), thì \(y\) cũng trở thành bạn của \(x\).

Các thành viên được thêm vào mạng qua \(n\) giai đoạn, cũng được đánh số từ \(0\) đến \(n-1\). Thành viên \(i\) được thêm ở giai đoạn \(i\). Ở giai đoạn 0, thành viên 0 được thêm vào và là thành viên duy nhất của mạng. Trong mỗi giai đoạn thuộc \(n-1\) giai đoạn tiếp theo, một thành viên được thêm vào bởi một người giới thiệu, có thể là bất kỳ người nào đã có trong mạng. Ở giai đoạn \(i\), với \(0<i<n\), người giới thiệu thêm thành viên \(i\) theo một trong ba cách thức:

• IAmYourFriend: thành viên \(i\) chỉ trở thành bạn của người giới thiệu.
• MyFriendsAreYourFriends: thành viên \(i\) trở thành bạn của tất cả những người đang là bạn của người giới thiệu tại thời điểm đó. Lưu ý, cách thức này không làm \(i\) trở thành bạn của người giới thiệu.
• WeAreYourFriends: thành viên \(i\) trở thành bạn của người giới thiệu và của tất cả những người đang là bạn của người giới thiệu tại thời điểm đó.

Sau khi xây dựng mạng, ta muốn chọn một mẫu thử để khảo sát, tức là chọn một nhóm thành viên. Vì bạn bè thường có những mối quan tâm tương tự, mẫu thử không được chứa bất kỳ cặp thành viên nào là bạn của nhau. Mỗi thành viên có một độ tự tin khi khảo sát, được biểu diễn bằng một số nguyên dương. Ta muốn tìm mẫu thử có tổng độ tự tin lớn nhất.

Ví dụ

Giai đoạn  Người giới thiệu  Cách thức                 Quan hệ bạn bè được thêm
1          0                IAmYourFriend             (1, 0)
2          0                MyFriendsAreYourFriends   (2, 1)
3          1                WeAreYourFriends          (3, 1), (3, 0), (3, 2)
4          2                MyFriendsAreYourFriends   (4, 1), (4, 3)
5          0                IAmYourFriend             (5, 0)

Ban đầu, mạng chỉ chứa thành viên 0. Người giới thiệu ở giai đoạn 1 là thành viên 0, mời thành viên 1 theo IAmYourFriend, nên họ trở thành bạn bè. Người giới thiệu ở giai đoạn 2 vẫn là thành viên 0, mời thành viên 2 theo MyFriendsAreYourFriends; thành viên 1, người bạn duy nhất của người giới thiệu, trở thành người bạn duy nhất của thành viên 2. Ở giai đoạn 3, người giới thiệu là thành viên 1, thêm thành viên 3 theo WeAreYourFriends; thành viên 3 trở thành bạn của thành viên 1 (người giới thiệu), đồng thời là bạn của các thành viên 0 và 2 (bạn của người giới thiệu). Các giai đoạn 4 và 5 cũng được thể hiện trong bảng trên.

Mạng cuối cùng được minh họa dưới đây. Số bên trong mỗi vòng tròn là chỉ số thành viên; số bên cạnh là độ tự tin của thành viên đó.

Các độ tự tin trong hình là:

Thành viên  0   1  2  3   4   5
Độ tự tin   13  3  6  20  10  15

Mẫu thử gồm hai thành viên 3 và 5 có tổng độ tự tin lớn nhất có thể, bằng

Nhiệm vụ

Cho mô tả từng giai đoạn và độ tự tin của từng thành viên, hãy tìm mẫu thử có tổng độ tự tin lớn nhất. Bạn chỉ cần cài đặt hàm findSample(n, confidence, host, protocol).

• n: số thành viên.
• confidence: mảng độ dài \(n\); confidence[i] là độ tự tin của thành viên \(i\).
• host: mảng độ dài \(n\); host[i] là chỉ số người giới thiệu ở giai đoạn \(i\).
• protocol: mảng độ dài \(n\); protocol[i] là mã cách thức dùng ở giai đoạn \(i\), với \(0<i<n\): 0 là IAmYourFriend, 1 là MyFriendsAreYourFriends, 2 là WeAreYourFriends.
• Giai đoạn 0 không có người giới thiệu, nên host[0] và protocol[0] không được xác định. Chương trình của bạn không được truy cập hai phần tử này.
• Hàm phải trả về tổng độ tự tin lớn nhất có thể của một mẫu thử.

Các subtasks

Một số subtasks chỉ dùng một phần trong ba cách thức, như bảng sau. Giới hạn độ tự tin áp dụng cho từng thành viên.

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên friend.c, friend.cpp hoặc friend.pas, cài đặt chương trình con theo đặc tả trên và chữ ký dưới đây. Với C/C++, bạn phải nạp tệp tiêu đề friend.h.

C/C++:

int findSample(int n, int confidence[], int host[], int protocol[]);

Pascal:

function findSample(n: longint; confidence: array of longint; host: array
of longint; protocol: array of longint): longint;

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng 1: n.
• Dòng 2: confidence[0], ..., confidence[n-1].
• Dòng 3: host[1], protocol[1], host[2], protocol[2], ..., host[n-1], protocol[n-1].

Trình chấm mẫu in giá trị trả về của findSample.