Cod sursa(job #2754196)

Utilizator vasiliumirunamariaVasiliu Miruna-Maria vasiliumirunamaria Data 25 mai 2021 13:37:26
Problema Farfurii Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#define N 100001

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


int n, k;

int main()
{
    int i, j, p;
    int t;

    fin >> n >> k;
    

    //nr maxim de inversiuni este n* (n - 1) /2 ->asta daca elementele sunt ordonate descrescator

    //avem nevoie de un numar cu k de inversiuni (sau imediat urmator) -> t
    t = 0;
    while (t * (t - 1) / 2 <= k)
        t++;

    //afisam crescator ce avem pana la n - t
    for (i = 1; i <= n - t; i++)
    {
        fout << i << " ";
        p = i;
    }

    //daca t * (t - 1) / 2 > k afisam un element de mijloc
    //care sa avem exact k perm
   
    
    int mij = -1;
    if (t * (t - 1) / 2 > k)
    {
        mij = p + (t * (t - 1) / 2) - k + 1;
        fout << mij << " ";
        p = n - t + 2;
    }
    else p = n - t + 1;

    //afisam restul descrescator
    j = n;
    for (i = p; i <= n; i++)
    {
        if (j == mij)
            j--;

        fout << j << " ";
        j--;
    }
        




   


    return 0;
}