Cod sursa(job #2753326)

Utilizator MateiDorian123Nastase Matei MateiDorian123 Data 22 mai 2021 14:07:59
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
/* practic problema se reduce la gasirea primei permutari in ordine lexicografica
   care are k inversiuni

   pentru a obtine prima permutare in ordine lexicografica trebuie sa pastram
   cat mai multe elemente de la inceputul permutarii fixe (sa inceapa cu cel
   mai mic nr posibil)

   numarul maxim de inversiuni este n * (n - 1) / 2
*/

int main()
{
    long long n, k, nr = 1, i, d;
    /// nr -> nr de numere ce trebuie inversate

    fin>>n>>k;
    fin.close();

    while(nr * (nr - 1) / 2 < k)
        ++ nr;


    for(i = 1; i <= n - nr; ++ i) /// restul n-nr numere raman neschimbate
        fout<<i<<" ";

    if(nr * (nr - 1) / 2 == k) /// daca avem nr de inversiuni dorite afisam direct numerele descrescator
         for(i = n; i > n - nr; i --)
            fout << i << " ";
    else{
        d = nr * (nr - 1) / 2 - k; /// d-> nr de inversiuni in plus
        fout<< n - d<<" "; /// daca afisam n - dif mai intai scapam de cele dif inversiuni

        for(i = n; i > n - nr; i --)
                if(i != n - d)
                    fout << i << " ";
    }

    fout.close();
    return 0;
}