Cod sursa(job #1838711)

Utilizator BLz0rDospra Cristian BLz0r Data 1 ianuarie 2017 16:59:51
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
using namespace std;

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

/*
*   problema cere defapt generarea
*   permutarii minim lexicografica, cu L inversiuni
*   permutarea se imparte in 3 parti:   - elementele 1, 2, 3, ... x nemodificate
*                                       - un element din multimea x+1 ... N
*                                       - restul elementelor ramase, in ordine descrescatoare
*/

int main(){

    int N;
    long long K;

    fin >> N >> K;

    // plecand de la permutarea identica,
    // incerc sa las cat mai multe elemente de la inceput nefolosite
    int i = 0;
    while (1LL * i * (i + 1) / 2 < K)
        i++;

    int ramase = 1LL * i * (i + 1) / 2 - K; // numarul de inversiuni ramase de facut cu elementul special

    // pot afisa primele elemente de care nu am nevoie
    for (int j = 1; j <= N - i - 1; ++j)
        fout << j << " ";

    // afisez elementul special
    fout << N - ramase << " ";

    // restul elementelor trebuie sa genereze numar maxim de inversiuni
    for (int j = N; j >= N - i; --j)
        if (j != N - ramase)
            fout << j << " ";

    return 0;
}