Problem
Bir dizi n farklı doğal sayı verildiğinde. Bu kümenin elemanlarının bir permütasyonuna, bu permütasyonun herhangi iki komşu elemanı için en büyük ortak bölenleri en az k ise, k-permütasyonu denir. Örneğin, S = {6, 3, 9, 8} öğelerinin kümesi verilirse, {8, 6, 3, 9} permütasyonu 2'li bir permütasyondur ve {6, 8, 3, 9} – hayır.
{p
1, p
2, …, p
n} permütasyonu sözlüksel olarak {q
1< permütasyonundan daha az olacaktır /sub>, q2, …, qn} eğer i (1 ≤ i ≤ n) pozitif bir tam sayı varsa, öyle ki pj = qj olduğunda j < i ve pi < qi.
Örnek olarak, yukarıdaki kümenin tüm k-permütasyonlarını sözlük sırasına göre sıralayalım. Örneğin, S'nin tam olarak dört 2-permütasyonu vardır: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} ve {9, 3, 6 , 8} Buna göre, sözlük sırasına göre ilk 2-permütasyon {3, 9, 6, 8} kümesidir ve dördüncü - ndash; {9, 3, 6, 8} ayarlayın.
Bu sırayla m-inci k-permütasyonunu bulmanızı sağlayan bir program yazmanız gerekmektedir.
Girdi
İlk satırdaki giriş dosyası, üç doğal sayı içerir – n (1 ≤n ≤16), m ve k (1 ≤m, k ≤109). İkinci satır, 109'u geçmeyen n farklı doğal sayı içerir. Satırlardaki tüm sayılar boşluklarla ayrılmıştır.
Künye
Verilen kümenin m-inci k-permütasyonunu veya çıktı dosyasında hiç yoksa -1'i çıkarmak gerekir.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |