Cod sursa(job #2754676)

Utilizator mirunavrAvram Miruna-Alexandra mirunavr Data 26 mai 2021 12:12:04
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 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
int 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 << " ";
    g << n - (nrMax * (nrMax - 1) / 2 - k) << " ";
    nr=n - (nrMax * (nrMax - 1) / 2 - k);
    for (i = n; i >= n-nrMax+1; i--) {
        if (i != nr)
            g << i << " ";

    }
}