Cod sursa(job #2753268)

Utilizator truscalucaLuca Trusca truscaluca Data 22 mai 2021 09:37:38
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>

using namespace std;

// Toate long long ca sa nu se poata ajunge la un overflow (diff. dintre 90p si 100p)
long long n, k, combN = 1, adjust;

int main() {
    freopen("farfurii.in", "r", stdin);
    freopen("farfurii.out", "w", stdout);

    cin >> n >> k;

    // Calculeaza de ce n ai nevoie astfel incat combinari de n luate cate 2 sa-l poata cuprinde pe k
    while (combN * (combN - 1) / 2 < k) {
        combN++;
    }

    // E nevoie doar de combN numere pentru a avea numarul k de inversiuni. Deci primele n-combN nu ne intereseaza,
    // asa ca le punem in ordine crescatoare (ca sa nu creeze cumva inversiuni).
    for (long long i = 1; i <= n - combN; i++) {
        cout << i << " ";
    }

    // combN * (combN-1) / 2 e foarte probabil sa fie Strict mai mare decat k. Deci trebuie sa mutam un element din
    // pozitia lui obisnuita (din sirul descrescator), pentru ca efectul lui asupra numarului de inversiuni sa fie
    // atenuat. Acel numar este adjust.
    adjust = n - ((combN * (combN - 1)) / 2 - k);
    cout << adjust << " ";

    // Afiseaza restul numerelor (excluzandu-l pe adjust) in ordine descrescatoare,
    // pentru a obtine numarul dorit de inversiuni
    for (long long i = n; i > n - combN; i--) {
        if (i != adjust) {
            cout << i << " ";
        }
    }

    return 0;
}