Cod sursa(job #2753609)

Utilizator StarkillerCalin Stafie Starkiller Data 23 mai 2021 18:16:17
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, k, numarul_de_numere_care_trebuie_inversate = 1;
int main()
{
    fin >> n >> k;
    while (numarul_de_numere_care_trebuie_inversate * (numarul_de_numere_care_trebuie_inversate - 1) / 2 < k)
        ++numarul_de_numere_care_trebuie_inversate;
    int rest = n - numarul_de_numere_care_trebuie_inversate;
    for (int i = 1 ; i <= rest ; ++i)
        gout << i << " ";

    // trebuie sa determinam elementul care "nu respecta ordinea"
    int nr_total_inversiuni = numarul_de_numere_care_trebuie_inversate * (numarul_de_numere_care_trebuie_inversate - 1) / 2;

    if (nr_total_inversiuni == k)
            for (int i = n ; i > rest; --i)
                gout << i << " ";
    else
    {
            int numar_inversiuni_in_plus = nr_total_inversiuni - k;
            int intrus = n - numar_inversiuni_in_plus;
            gout << intrus << " "; // scapam de cele 'numar_inversiuni_in_plus' inversiuni daca afisam mai intai 'intrus'

            for (int i = n ; i > rest; --i)
                if (i != intrus)
                    gout << i << " ";
    }

    return 0;
}