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].