Cod sursa(job #2753773)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 24 mai 2021 12:56:18
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

using namespace std;

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

/**
 * problema se reduce la a determina cea mai mica permutare de n elemente din punct de vedere
 * lexicografic pentru care numarul de inversiuni este k
 * numarul de inversiuni este maxim n * (n - 1) / 2, deci cautam cate un t maxim astfel incat
 * t * (t - 1) / 2 <= k
 * numerele de la 1 la t vor aparea in ordine crescatoare, iar daca t * (t - 1) / 2 > k, trebuie
 * sa afisam imediat dupa n - (t * (t - 1) / 2 - k) pentru a pastra numarul de inversiuni dorit,
 * dupa care afisam restul numerelor in ordine descrescatoare
 * @return
 */

int main() {
    long long n, k, t = 1;

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

    while (t * (t - 1) / 2 < k) {
        ++t;
    }

    for (long long i = 1; i <= n - t; ++i) {
        fout << i << ' ';
    }

    long long dif = n - (t * (t - 1) / 2 - k);
    fout << dif << ' ';

    for (long long i = n; i > n - t; --i) {
        if (i != dif) {
            fout << i << ' ';
        }
    }

    fout.close();
    return 0;
}