Pagini recente » Cod sursa (job #1320202) | Cod sursa (job #667863) | Cod sursa (job #866575) | Cod sursa (job #1764205) | Cod sursa (job #2892899)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("farfurii.in");
ofstream fout("farfurii.out");
// pornim de la ideea ca daca vrem sa facem o permutare minima
// trebuie sa fie de genul 1 2 3 4 20 19 18 17 .... 6 5 4
// adica trebuie sa aiba o portiune crescatoare de lungime maxima la inceput
// iar restul sa fie in ordine descrescatoare
int main()
{
int n,i,j,k,indicemax, CNT, numar_dif;
fin>>n>>k;
for(i = 1; (i * (i-1)) / 2 <k; i++)
{
// calculez cat de mare va fi portiunea de numere in ordine descresc.
// combinari de n luate cate 2 va fi maximul, deci trebuie sa ne incapa in k
}
indicemax = i; // de aici incepe portiunea descendenta
for(i = 1; i<=n-indicemax; i++)
{
fout<< i << ' '; //afisam portiunea ascendenta
}
CNT = indicemax * (indicemax-1) / 2 - k; // asta este diferenta dintre urmatoarea lungime de
// portiune descendenta dar pentru care nu mai avem suficiente inversiuni, asa ca scoatem din ea al CNT - lea element
// spre exemplu, din permutarea 5 4 3 2 1 care are 10 inversiuni, daca il scoatem pe 3 si il punem in fata scapam de 2 inversiuni, pentru ca nu va mai avea
// cele 2 elemente mai mari in fata lui
numar_dif = n - CNT; // afisam numarul cu pricina de mai sus
fout << numar_dif << ' ';
for(i = n; i >= n - indicemax + 1; i--)
{
if(numar_dif != i) // afisam portiunea descrescatoare fara numarul neserios gasit mai sus
fout << i << ' ';
}
return 0;
}