Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

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ị π = (π1π2, ..., π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ị ρ = (ρ1ρ2, , ρn) được gọi là đi trước hoán vị σ = (σ1σ2, …, σ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 ρ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 π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 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(π).

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


Photo

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.

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 k;
  • Dòng thứ hai gồm n số nguyên dương π1, π2, ..., π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 ≤ 103;
  • 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 ≤ 103, k ≤ 106.

Ví dụ:

 Dữ liệu vào:

 4 6

 1 3 4 2

 Dữ liệu ra:

 4


Được gửi lên bởi:VOJ Team
Ngày:2015-01-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VOI15 day 2

hide comments
2017-12-27 16:02:31
it+ quicksort
2017-09-18 11:34:38


THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/1174/voisort-spoj/



2017-08-15 14:54:53
Xem lời giải:
https://vietcodes.github.io/code/45/
2016-12-27 16:36:15
it 60 điểm tròn +=+
2016-12-26 09:03:07
ahihi :)
2016-12-16 09:38:20
Tôi tìm ra cách sinh hoán vị O(1) + cách kiểm tra O(1) + Input O(1), ez trâu AC.
2016-12-08 04:37:40 le tuan dung
Tôi là Lê Tuấn Dũng. Xin chào các fan hâm mộ.
2016-12-08 04:33:38
Còn tôi phát hiện ra cách kiểm tra hoán vị thỏa mãn O(1). Trâu Cũng AC.
2016-12-08 04:32:33
Tôi phát minh ra cách sinh hoán vị O(1). Trâu cũng AC.
2016-06-03 11:33:47
bach sanh dieu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.