Pagini recente » Cod sursa (job #2400114) | Cod sursa (job #2240183) | Cod sursa (job #13067) | Cod sursa (job #2142218) | Cod sursa (job #3133804)
//#include <iostream>
#include <fstream>
#include<vector>
using namespace std;
std::ifstream cin("farfurii.in");
std::ofstream cout("farfurii.out");
int gauss(int val){
return (val * (val-1))>>1;
}
int main() {
/*cerinta problemei este echivalenta cu:
Sa se afiseze cea mai mica permutare lexicografic cu n inversiuni.
Se stie ca o permutare desccrescatoare(n, n-1, ... 3, 2, 1) n*(n-1)/2 inversiuni, cele mai multe pt o permutare cu n elemente
Astfel daca numarul de tacamuri k este de forma x*(x-1)/2, cu x nr. natural, atunci permutarea ceruta va arata astfel:
1 2 ... n-x n n-1 .. n-x+1
Daca K>x*(x-1)/2 atunci construim
1 2 ... n-x-1 n n-1 .. n-x+1 n-x care are x*(x-1)/2 inversiuni
Mutam elementul n-((x+1)*n/2-k) inaintea lui n, scazand in acest fel numarul de inversiuni la k.
*/
long long n,k, val = 0,aux = 0;
cin>>n>>k;
while(gauss(val)<=k)val++;
for(long long i=1; i <= n-val;i++)cout<<i<<" ";
if(gauss(val)>k) {
aux = n - (gauss(val) - k);
cout<<aux<<" ";
}
for(long long i=n;i> n-val;i--)cout<<i<<" ";
return 0;
}