IOI 2014 - Ngày 2

Mao-Kong Gondola là một địa điểm du lịch nổi tiếng ở Đài Bắc. Hệ thống gondola gồm một đường ray vòng tròn, một bến đỗ duy nhất và \(n\) chiếc gondola được đánh số liên tiếp từ \(1\) đến \(n\), chạy quanh đường ray theo một hướng cố định. Sau khi gondola \(i\) đi qua bến, chiếc tiếp theo đi qua bến là gondola \(i+1\) nếu \(i<n\), hoặc gondola \(1\) nếu \(i=n\).

Các gondola có thể bị hỏng. May mắn là ta có vô hạn gondola dự trữ, được đánh số \(n+1, n+2, \ldots\). Khi một gondola bị hỏng, ta thay nó ở đúng vị trí trên đường ray bằng chiếc dự trữ đầu tiên còn sẵn, tức là chiếc có số nhỏ nhất. Ví dụ, nếu có năm gondola và gondola 1 bị hỏng, ta thay nó bằng gondola 6.

Bạn thích đứng ở bến ngắm các gondola đi qua. Một dãy gondola là dãy gồm \(n\) số hiệu của các gondola đi qua bến. Có thể một hoặc nhiều gondola đã bị hỏng và được thay trước khi bạn đến, nhưng không có gondola nào bị hỏng trong lúc bạn quan sát.

Lưu ý rằng cùng một cấu hình gondola trên đường ray có thể cho nhiều dãy gondola, tùy chiếc nào đi qua đầu tiên khi bạn đến bến. Chẳng hạn, nếu chưa có gondola nào bị hỏng thì cả (2, 3, 4, 5, 1) và (4, 5, 1, 2, 3) đều có thể là dãy gondola, nhưng (4, 3, 2, 5, 1) thì không, vì thứ tự xuất hiện không đúng.

Nếu gondola 1 bị hỏng, ta có thể quan sát dãy (4, 5, 6, 2, 3). Nếu tiếp theo gondola 4 bị hỏng, ta thay nó bằng gondola 7 và có thể quan sát dãy (6, 2, 3, 7, 5). Nếu sau đó gondola 7 bị hỏng, ta thay nó bằng gondola 8 và có thể quan sát dãy (3, 8, 5, 6, 2).

Gondola bị hỏng  Gondola thay thế  Dãy gondola có thể quan sát
1               6                 (4, 5, 6, 2, 3)
4               7                 (6, 2, 3, 7, 5)
7               8                 (3, 8, 5, 6, 2)

Một dãy thay thế là dãy gồm số hiệu của các gondola bị hỏng, theo đúng thứ tự chúng bị hỏng. Trong ví dụ trên, dãy thay thế là (1, 4, 7). Dãy thay thế \(r\) tạo ra dãy gondola \(g\) nếu sau khi các gondola bị hỏng theo dãy \(r\), ta có thể quan sát được dãy \(g\).

Kiểm tra dãy gondola

Trong ba subtask đầu tiên, bạn phải kiểm tra dãy đầu vào có phải là một dãy gondola hay không. Các ví dụ dưới đây minh họa các dãy hợp lệ và không hợp lệ. Bạn cần cài đặt hàm valid(n, inputSeq).

• n: độ dài dãy đầu vào.
• inputSeq: mảng độ dài \(n\); inputSeq[i] là phần tử \(i\) của dãy, với \(0 \le i \le n-1\).
• Hàm trả về 1 nếu dãy đầu vào là một dãy gondola, hoặc 0 nếu không phải.

Subtasks 1, 2, 3

Ví dụ

Subtask  inputSeq               Giá trị trả về
1        (1, 2, 3, 4, 5, 6, 7)  1
1        (3, 4, 5, 6, 1, 2)     1
1        (1, 5, 3, 4, 2, 7, 6)  0
1        (4, 3, 2, 1)           0
2        (1, 2, 3, 4, 5, 6, 5)  0
3        (2, 3, 4, 9, 6, 7, 1)  1
3        (10, 4, 3, 11, 12)     0

Ghi chú cho từng ví dụ:

• (1, 2, 3, 4, 5, 6, 7) và (3, 4, 5, 6, 1, 2) đều hợp lệ.
• (1, 5, 3, 4, 2, 7, 6) không hợp lệ vì 1 không thể xuất hiện ngay trước 5.
• (4, 3, 2, 1) không hợp lệ vì 4 không thể xuất hiện ngay trước 3.
• (1, 2, 3, 4, 5, 6, 5) không hợp lệ vì có hai gondola cùng số hiệu 5.
• (2, 3, 4, 9, 6, 7, 1) có thể được tạo ra bởi dãy thay thế (5, 8).
• (10, 4, 3, 11, 12) không hợp lệ vì 4 không thể xuất hiện ngay trước 3.

Dãy thay thế

Trong ba subtask tiếp theo, bạn phải dựng một dãy thay thế có thể tạo ra dãy gondola đã cho. Bất kỳ dãy thay thế nào thỏa mãn đều được chấp nhận. Bạn cần cài đặt hàm replacement(n, gondolaSeq, replacementSeq).

• n: độ dài dãy gondola.
• gondolaSeq: mảng độ dài \(n\), được bảo đảm là một dãy gondola; gondolaSeq[i] là phần tử \(i\) của dãy, với \(0 \le i \le n-1\).
• Hàm trả về \(l\), độ dài dãy thay thế.
• replacementSeq: mảng đủ lớn để chứa dãy thay thế; bạn phải gán phần tử \(i\) của dãy thay thế vào replacementSeq[i], với \(0 \le i \le l-1\).

Subtasks 4, 5, 6

Ví dụ

Subtask  gondolaSeq             Giá trị trả về  replacementSeq
4        (3, 1, 4)             1               (2)
4        (5, 1, 2, 3, 4)       0               ()
5        (2, 3, 4, 9, 6, 7, 1) 2               (5, 8)

Đếm số dãy thay thế

Trong bốn subtask tiếp theo, bạn phải đếm số dãy thay thế có thể tạo ra dãy đã cho, lấy phần dư khi chia cho 1 000 000 009. Dãy đầu vào có thể là một dãy gondola hoặc không. Bạn cần cài đặt hàm countReplacement(n, inputSeq).

• n: độ dài dãy đầu vào.
• inputSeq: mảng độ dài \(n\); inputSeq[i] là phần tử \(i\) của dãy, với \(0 \le i \le n-1\).
• Nếu dãy đầu vào là một dãy gondola, hãy đếm số dãy thay thế tạo ra nó. Số lượng này có thể cực kỳ lớn; hàm phải trả về phần dư khi chia số đó cho \(1\,000\,000\,009\).
• Nếu dãy đầu vào không phải là một dãy gondola, hàm phải trả về 0.
• Nếu dãy đầu vào là một dãy gondola nhưng không có gondola nào bị hỏng, hàm phải trả về 1.

Subtasks 7, 8, 9, 10

Ví dụ

Subtask  inputSeq                Giá trị trả về  Dãy thay thế
7        (1, 2, 7, 6)            2               (3, 4, 5) hoặc (4, 5, 3)
8        (2, 3, 4, 12, 6, 7, 1)  1               (5, 8, 9, 10, 11)
9        (4, 7, 4, 7)            0               inputSeq không phải dãy gondola
10       (3, 4)                  2               (1, 2) hoặc (2, 1)

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên gondola.c, gondola.cpp hoặc gondola.pas. Tệp phải cài đặt cả ba chương trình con trên, ngay cả khi bạn chỉ định giải một số subtasks. Sử dụng các chữ ký dưới đây; với C/C++, bạn phải nạp tệp tiêu đề gondola.h.

C/C++:

int valid(int n, int inputSeq[]);
int replacement(int n, int gondolaSeq[], int replacementSeq[]);
int countReplacement(int n, int inputSeq[]);

Pascal:

function valid(n: longint; inputSeq: array of longint): integer;
function replacement(n: longint; gondolaSeq: array of longint;
var replacementSeq: array of longint): longint;
function countReplacement(n: longint; inputSeq: 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: T, số thứ tự subtask mà chương trình định giải, với \(1 \le T \le 10\).
• Dòng 2: n, độ dài dãy đầu vào.
• Dòng 3: nếu T là 4, 5 hoặc 6, chứa gondolaSeq[0], ..., gondolaSeq[n-1]; nếu không, chứa inputSeq[0], ..., inputSeq[n-1].

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.

Jian-Jia đang lên kế hoạch cho kỳ nghỉ tiếp theo tại Đài Loan. Trong kỳ nghỉ, cậu di chuyển giữa các thành phố và tham quan các điểm du lịch trong những thành phố đó.

Có \(n\) thành phố, tất cả nằm dọc theo một con đường cao tốc, được đánh số liên tiếp từ \(0\) đến \(n-1\). Với thành phố \(i\) thỏa mãn \(0<i<n-1\), hai thành phố liền kề là \(i-1\) và \(i+1\). Thành phố duy nhất liền kề với thành phố 0 là thành phố 1; thành phố duy nhất liền kề với thành phố \(n-1\) là thành phố \(n-2\).

Mỗi thành phố có một số điểm du lịch. Jian-Jia có \(d\) ngày nghỉ và muốn tham quan nhiều điểm du lịch nhất có thể. Cậu đã chọn sẵn thành phố xuất phát. Trong mỗi ngày, Jian-Jia hoặc di chuyển đến một thành phố liền kề, hoặc tham quan tất cả các điểm du lịch của thành phố đang ở, nhưng không thể làm cả hai. Jian-Jia không bao giờ tham quan các điểm du lịch trong cùng một thành phố hai lần, ngay cả khi cậu đến thành phố đó nhiều lần. Hãy giúp cậu lập kế hoạch để tham quan được nhiều điểm du lịch khác nhau nhất.

Ví dụ

Giả sử Jian-Jia có 7 ngày nghỉ, có 5 thành phố với số điểm du lịch như bảng dưới đây, và cậu xuất phát từ thành phố 2.

Thành phố  Số điểm du lịch
0          10
1          2
2          20
3          30
4          1

Ngày thứ nhất, Jian-Jia tham quan 20 điểm du lịch ở thành phố 2. Ngày thứ hai, cậu di chuyển từ thành phố 2 đến thành phố 3. Ngày thứ ba, cậu tham quan 30 điểm du lịch ở thành phố 3. Cậu dùng ba ngày tiếp theo để đi từ thành phố 3 đến thành phố 0, rồi tham quan 10 điểm du lịch ở thành phố 0 vào ngày thứ bảy.

Ngày  Hoạt động
1     Tham quan các điểm du lịch ở thành phố 2
2     Di chuyển từ thành phố 2 đến thành phố 3
3     Tham quan các điểm du lịch ở thành phố 3
4     Di chuyển từ thành phố 3 đến thành phố 2
5     Di chuyển từ thành phố 2 đến thành phố 1
6     Di chuyển từ thành phố 1 đến thành phố 0
7     Tham quan các điểm du lịch ở thành phố 0

Tổng số điểm du lịch được tham quan là

Đây là số điểm du lịch lớn nhất có thể tham quan trong 7 ngày nếu xuất phát từ thành phố 2.

Nhiệm vụ

Hãy cài đặt hàm findMaxAttraction(n, start, d, attraction) để tính số điểm du lịch lớn nhất Jian-Jia có thể tham quan.

• n: số thành phố.
• start: chỉ số thành phố xuất phát.
• d: số ngày nghỉ.
• attraction: mảng độ dài \(n\); attraction[i] là số điểm du lịch ở thành phố \(i\), với \(0 \le i \le n-1\).
• Hàm phải trả về số điểm du lịch lớn nhất Jian-Jia có thể tham quan.

Các subtasks

Trong tất cả các subtasks, số điểm du lịch ở mỗi thành phố là không âm và

Các ràng buộc bổ sung:

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên holiday.c, holiday.cpp hoặc holiday.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 đề holiday.h.

Lưu ý: kết quả có thể rất lớn; kiểu trả về của findMaxAttraction là số nguyên 64 bit.

C/C++:

long long int findMaxAttraction(int n, int start, int d,
int attraction[]);

Pascal:

function findMaxAttraction(n, start, d : longint;
attraction : array of longint): int64;

Trình chấm mẫu

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

• Dòng 1: n, start, d.
• Dòng 2: attraction[0], ..., attraction[n-1].

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