Cod sursa(job #2753607)

Utilizator StarkillerCalin Stafie Starkiller Data 23 mai 2021 18:12:13
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 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;
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;
    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;
}