Cod sursa(job #2754681)

Utilizator mirunavrAvram Miruna-Alexandra mirunavr Data 26 mai 2021 12:17:25
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
//Calculam cea mai mica permutare de n elemente pentru care numarul de inversiuni= k (i<j ; sigma(i)>sigma(j)
//nr maxim de inversiuni poate fi C de n luate cate 2 -> n(n-1)/2 -> cautam nrMax unde nrMax(nrMax-1)/2<=k
//pentru a avea numar maxim -> numerele de la 1 la nrMax sunt crescatoare
//afisam n-(nrMax*(nrMax-1)/2-k) pentru a ne ramane numarul de inversiuni
// iar restul in ordine descrescatoare
long long n,k,i,nrMax=1,nr;
int main() {
    f >> n >> k;
    while (nrMax * (nrMax - 1) / 2 < k) {
        nrMax++;
    }
    for (i = 1; i <= n-nrMax; ++i)
        g << i << " ";
    nr=n - (nrMax * (nrMax - 1) / 2 - k);
    g<<nr<<" ";
    for (i = n; i >= n-nrMax+1; --i) {
        if (i != nr)
            g << i << " ";

    }
}