Cod sursa(job #2624427)

Utilizator yoanaIoana Grigore yoana Data 4 iunie 2020 20:30:06
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<iostream>
#include<fstream>
/// are cel mult n*(n-1)/2 inversiuni cand numerele sunt in ordine descrescatoare.
///daca K e de forma M*(M-1)/2 permutarea minima lexicografic cu K inversiuni va fi:

///1, 2, 3, ... N-M, N, N-1, N-2, ... N-M+1

///Cele K inversiuni apar in ultimele M elemente. Daca in aceasta permutare mutam un element N-x imediat inaintea lui N numarul de inversiuni scade cu x. Astfel, daca K>M*(M-1)/2 construim permutarea

///1, 2, 3, ... N-M-1, N, N-1, N-2, ... N-M

///(care are (M+1)*M/2 inversiuni) si mutam elementul N-((M+1)*M/2-K) imediat inaintea lui N, astfel scadem numarul de inversiuni la K.

using namespace std;
 ifstream f("farfurii.in");
ofstream g("farfurii.out");

int main()
{
    long long n, m, i, j, k, x, index;
    f>>n>>m;
    k=1;
    while((k*(k+1)/2)<=m)
        k++;
    x=m-(k*(k-1)/2);
    index=n-k;
    for(i=1; i<index; i++)
        g<<i<<' ';
    g<<index+x<<' ';
    for(i=n; i>index+x; i--)
        g<<i<<' ';
    for(i=index+x; i>index; i--)
        g<<i-1<<' ';}