Pagini recente » Cod sursa (job #362420) | Cod sursa (job #660190) | Cod sursa (job #639259) | Cod sursa (job #2907244) | Cod sursa (job #2624425)
#include<iostream>
#include<fstream>
/// are cel mult n*(n-1)/2 inversiuni cand numerele sunt in ordine descrescatoare.
///daca K e de forma M*(M-1)/2 permutarea minima lexicografic cu K inversiuni va fi:
///1, 2, 3, ... N-M, N, N-1, N-2, ... N-M+1
///Cele K inversiuni apar in ultimele M elemente. Daca in aceasta permutare mutam un element N-x imediat inaintea lui N numarul de inversiuni scade cu x. Astfel, daca K>M*(M-1)/2 construim permutarea
///1, 2, 3, ... N-M-1, N, N-1, N-2, ... N-M
///(care are (M+1)*M/2 inversiuni) si mutam elementul N-((M+1)*M/2-K) imediat inaintea lui N, astfel scadem numarul de inversiuni la K.
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
int main()
{
long long n, m, i, j, k, x, index;
f>>n>>m;
k=1;
while((k*(k+1)/2)<=m)
k++;
x=m-(k*(k-1)/2);
index=n-k;
for(i=1; i<poz; i++)
g<<i<<' ';
g<<index+x<<' ';
for(i=n; i>index+x; i--)
g<<i<<' ';
for(i=index+x; i>index; i--)
g<<i-1<<' ';}