Cod sursa(job #2901220)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 13 mai 2022 12:40:02
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
// Nu las comentarii in cod de obicei, dar acum simt nevoia sa explic :)
/*
Problema se reduce la gasirea unei permutari cu K inversiuni.
Pentru fiecare numar pe care-l fixam,
dupa el putem avea combinari de 'fixat' luate cate 2 si combinari de 'fixat' - 1 luate cate 2 inversiuni.
Odata gasit 'fixat', putem sa cautam numerele noastre.
*/
#include <fstream>

using namespace std;

ifstream in("farfurii.in");
ofstream out("farfurii.out");

long long N, K, fixat, rest, poz, i;

int main()
{
    in >> N >> K;
    for(;fixat * (fixat + 1) / 2 < K; ++fixat);
    for(i = 1; i <= N - fixat - 1; ++i)
        out << i << " ";
    rest = fixat * (fixat + 1) / 2 - K;
    out << N - rest << " ";
    for(int j = N; j >= i; --j)
        if(j != N - rest)
            out << j << " ";
    return 0;
}