VOITSORT - VNOI

VOITSORT - VOI 2015 Day 2 - Cây hoán vị

Giới hạn

Thời gian: 1.0s
Bộ nhớ: 1536MB
Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Mùa Giáng Sinh năm nay ấm áp, đôi bạn Đông và Bắc rủ nhau ở nhà cùng nghiên cứu một thuật toán sắp xếp tổ hợp có cấu trúc đặc biệt. Ban đầu Đông chuẩn bị một hoán vị π = ( π ₁ , π ₂ , ..., π _n ) của n số nguyên dương 1, 2, ..., n rồi đưa cho Bắc. Tiếp theo, Đông tìm hoán vị đi ngay sau hoán vị π trong thứ tự từ điển rồi đưa cho Bắc, và cứ tiếp tục như vậy. Nhắc lại là: Hoán vị ρ = ( ρ ₁ , ρ ₂ , … , ρ _n ) được gọi là đi trước hoán vị σ = ( σ ₁ , σ ₂ , …, σ _n ) theo thứ tự từ điển nếu như tồn tại một chỉ số i (1 ≤ i ≤ n ) sao cho:

nếu i = 1 thì ρ _i < σ _i ;
nếu 1 < i ≤ n thì ρ _j = σ _j với j < i và ρ _i < σ _i .

Với mỗi hoán vị π nhận được từ Đông, Bắc tiến hành dựng cây nhị phân T ( π ) có cấu trúc như sau:

Nút gốc của T ( π ) được gán nhãn n là số lớn nhất của π ;
Giả sử π ^left và π ^right lần lượt là dãy con bên trái và bên phải của n trong π . Gọi a là số lớn nhất của dãy π ^left và b là số lớn nhất của dãy π ^right . Khi đó nút gốc của T ( π ) sẽ có hai cây con: cây con trái T ( π ^left ) với gốc được gán nhãn a và cây con phải T ( π ^right ) với gốc được gán nhãn b . Nếu dãy π ^left là rỗng thì nút gốc của T ( π ) không có con trái. Nếu dãy π right là rỗng thì nút gốc của T ( π ) không có con phải;
Nếu dãy π ^left là khác rỗng thì cây con T ( π ^left ) gốc tại a được xây dựng một cách đệ qui đối với dãy con π ^left giống như việc xây dựng cây T ( π );
Nếu dãy π right là khác rỗng thì cây con T ( π ^right ) gốc tại b được xây dựng một cách đệ qui đối với dãy con π ^right giống như việc xây dựng cây T ( π ).

Ví dụ: Với π = (2, 6, 3, 4, 9, 8, 1, 7, 5) thì cây T ( π ) được mô tả như trong hình 1.

Hình 1. Cây T ( π ) tương ứng với hoán vị π = (2, 6, 3, 4, 9, 8, 1, 7, 5)

Cây T ( π ) xây dựng theo qui tắc nêu trên được gọi là cây nhị phân tương ứng với hoán vị π.

Tiếp theo Bắc tiến hành liệt kê các nút của cây T ( π ) theo thứ tự sau và thu được một hoán vị mới gồm các nhãn của các nút được sắp xếp theo trình tự các nút được liệt kê. Nhắc lại là: Việc liệt kê các nút của cây T ( π ) theo thứ tự sau được định nghĩa một cách đệ qui như sau:

Nếu cây T ( π ) chỉ có một nút thì danh sách gồm một nút duy nhất đó là danh sách các nút của cây T ( π ) được liệt kê theo thứ tự sau;
Nếu cây T ( π ) có nhiều hơn một nút thì danh sách các nút của cây T ( π ) được liệt kê theo thứ tự sau là: đầu tiên là các nút của cây con trái của T ( π ) được liệt kê theo thứ tự sau, tiếp đến là các nút của của cây con phải của T ( π ) được liệt kê theo thứ tự sau, cuối cùng là nút gốc.

Ví dụ: Với hoán vị trong ví dụ trên, hoán vị thu được bởi việc liệt kê các nút của cây nhị phân tương ứng với nó T ( π ) theo thứ tự sau là (2, 3, 4, 6, 1, 5, 7, 8, 9).

Đôi bạn xét tính chất TSort sau đây trên tập các hoán vị của các số nguyên dương từ 1 đến n : " Hoán vị π được nói là có tính chất TSort nếu việc liệt kê các nút của cây nhị phân tương ứng với nó T ( π ) theo thứ tự sau cho ta hoán vị đơn vị, nghĩa là hoán vị có dạng (1, 2, ... , n )". Đông và Bắc muốn khảo sát xem những hoán vị như vậy có phải là thường gặp hay không.

Yêu cầu: Cho π là một hoán vị của các số 1, 2, …, n , hãy viết chương trình giúp đôi bạn xác định số lượng hoán vị trong số k hoán vị liên tiếp theo thứ tự từ điển bắt đầu từ π (kể cả π ) thoả mãn tính chất TSort.

Dữ liệu vào:

Dòng đầu gồm hai số nguyên dương n và k ;
Dòng thứ hai gồm n số nguyên dương π ₁ , π ₂ , ..., π _n là các thành phần của hoán vị π . Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

Ghi ra một số nguyên duy nhất là số lượng hoán vị trong số k hoán vị liên tiếp theo thứ tự từ điển bắt đầu từ π (kể cả π ) thoả mãn tính chất TSort.

Ràng buộc:

Có 30% số test tương ứng với các bộ dữ liệu có giới hạn n , k ≤ 100;
Có 30% số test khác tương ứng với các bộ dữ liệu có giới hạn n , k ≤ 10 ³ ;
Có 40% số test còn lại tương ứng với các bộ dữ liệu có giới hạn n ≤ 10 ³ , k ≤ 10 ⁶ .

Ví dụ:

Dữ liệu vào:
4 6
1 3 4 2

Dữ liệu ra:
4

Người up: voj
Nguồn bài: VOI15 day 2