Problem
Cho tập hợp n số tự nhiên khác nhau. Một hoán vị của các phần tử của tập hợp này được gọi là hoán vị k nếu với hai phần tử lân cận bất kỳ của hoán vị này, ước chung lớn nhất của chúng ít nhất là k. Ví dụ: nếu tập hợp các phần tử S = {6, 3, 9, 8} được cho, thì hoán vị {8, 6, 3, 9} là hoán vị 2 và hoán vị {6, 8, 3, 9} – không.
Hoán vị {p
1, p
2, …, p
n} sẽ ít hơn về mặt từ điển so với hoán vị {q
1< /sub>, q2, …, qn} nếu tồn tại số nguyên dương i (1 ≤ i ≤ n) sao cho pj = qj khi j < tôi và pi < qi.
Ví dụ, hãy sắp xếp tất cả các hoán vị k của tập hợp trên theo thứ tự từ điển. Ví dụ: có chính xác bốn hoán vị 2 của S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} và {9, 3, 6 , 8} . Theo đó, hoán vị 2 đầu tiên theo thứ tự từ điển là tập hợp {3, 9, 6, 8} và &ndash thứ tư; đặt {9, 3, 6, 8}.
Bạn được yêu cầu viết một chương trình cho phép bạn tìm hoán vị k thứ m theo thứ tự này.
Đầu vào
Tệp đầu vào trong dòng đầu tiên chứa ba số tự nhiên – n (1 ≤ n ≤ 16), m và k (1 ≤ m, k ≤ 109). Dòng thứ hai chứa n số tự nhiên phân biệt không quá 109. Tất cả các số trong các dòng được phân tách bằng dấu cách.
Dấu ấn
Cần phải xuất hoán vị k thứ m của tập hợp đã cho hoặc –1 nếu không có gì trong tệp đầu ra.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4 1 2
6 8 3 9
| 3 9 6 8 |
| 2 |
4 4 2
6 8 3 9
| 9 3 6 8 |
| 3 |
4 5 2
6 8 3 9
| -1 |