Pagini recente » Cod sursa (job #2359556) | Cod sursa (job #2158816) | Cod sursa (job #701353) | Cod sursa (job #2675457) | Cod sursa (job #2747173)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
int n,k;
int main()
{
fin>>n>>k;
//trebuie sa gasesc permutarea cu k inversiuni
if(k==0) //permutarea finala nu are nicio inversiune
{
for(int i=1;i<=n;++i)
fout<<i<<" ";
return 0;
}
//idee: plec de la permutarea identica: 1,2,...,n si o alterez cu swapuri ca sa obtin k inversiuni
//caut valoarea M minima astfel incat M(M-1)/2 >= k ca sa pot pastra niste elemente de la inceput "blocate"
int M=1;
while(M*(M-1)/2 < k) M++;
//las primele n-M valori neschimbate, iar pe urmatoarele le pun in ordine descrescatoare, astfel obtinand M*(M-1)/2 inversiuni
// urmand sa fac swapuri ca sa aduc la k inversiuni
for(int i=1;i<=n-M;++i)
fout<<i<<" ";
if(M*(M-1)/2==k) //nu mai trebuie sa fac niciun swap pentru ca sunt exact k inversiuni
for(int i=n;i>=n-M+1;--i)
fout<<i<<" ";
else
{
int dif=M*(M-1)/2-k;
//in subsecventa n,n-1,....,n-M+1 din secventa finala mare (1,2,...,n-M,n,n-1,...n-dif,n-dif-1,...,n-M+1)ar trebui
//sa permut spre dreapta subsecventa n,n-1,...,n-dif (n-dif-1,...,n-M+1 raman blocate)
//adica sa dau swap mereu cu elementul din stanga pornind de la valoarea n-dif
//pentru a scadea inversiunile adaugate in plus si a pastra cea mai mica dpdv lexicografic permutare
//deci sa obtin in final (1,2,...,n-M,n-dif,n,n-1,...n-dif+1,n-dif-1,...,n-M+1)
fout<<n-dif<<" ";
for(int i=n;i>=n-M+1;--i)
if(i!=n-dif)
fout<<i<<" ";
}
return 0;
}