Cod sursa(job #2755272)

Utilizator bananamandaoneTudor Cosmin Oanea bananamandaone Data 26 mai 2021 22:29:55
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

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

long long n, k;

int main()
{
    long long i, ninv, p;

    fin >> n >> k;

    if(k == n * (n - 1) / 2)
        for(i = n; i >= 1; i--)
            fout << i << " ";
    else
    {

        // ninv = n ul pentru care folosesc toate numerele ca sa fac k inversiuni
        ninv = 1;
        while(ninv * (ninv - 1) / 2 < k)
            ninv++;

        // primele numere pana la pozitia care nu interfereaza cu
        // cele ninv inversiuni le afisez crescator
        for(i = 1; i <= n - ninv; i++)
            fout << i << " ";


        // p = numarul de inversiuni de care trebuie sa scap
        p = ninv * (ninv - 1) / 2 - k;
        // daca il mut pe (n - p) in stanga (in secventa ramasa)
        // scap de exact p inversiuni
        fout<< n - p <<" ";

        // le afisez in continuare descrescator pe celelalte
        for(i = n; i > n - ninv; i--)
                if(i != n - p)
                    fout << i << " ";
    }

    fin.close();
    fout.close();
    return 0;
}