Pagini recente » Cod sursa (job #2705856) | Cod sursa (job #223944) | Cod sursa (job #1881268) | Cod sursa (job #745995) | Cod sursa (job #2753326)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
/* practic problema se reduce la gasirea primei permutari in ordine lexicografica
care are k inversiuni
pentru a obtine prima permutare in ordine lexicografica trebuie sa pastram
cat mai multe elemente de la inceputul permutarii fixe (sa inceapa cu cel
mai mic nr posibil)
numarul maxim de inversiuni este n * (n - 1) / 2
*/
int main()
{
long long n, k, nr = 1, i, d;
/// nr -> nr de numere ce trebuie inversate
fin>>n>>k;
fin.close();
while(nr * (nr - 1) / 2 < k)
++ nr;
for(i = 1; i <= n - nr; ++ i) /// restul n-nr numere raman neschimbate
fout<<i<<" ";
if(nr * (nr - 1) / 2 == k) /// daca avem nr de inversiuni dorite afisam direct numerele descrescator
for(i = n; i > n - nr; i --)
fout << i << " ";
else{
d = nr * (nr - 1) / 2 - k; /// d-> nr de inversiuni in plus
fout<< n - d<<" "; /// daca afisam n - dif mai intai scapam de cele dif inversiuni
for(i = n; i > n - nr; i --)
if(i != n - d)
fout << i << " ";
}
fout.close();
return 0;
}