Cod sursa(job #3133804)

Utilizator stefanmo03Mocanu Stefan stefanmo03 Data 26 mai 2023 23:25:18
Problema Farfurii Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
//#include <iostream>
#include <fstream>
#include<vector>
using namespace std;
std::ifstream cin("farfurii.in");
std::ofstream cout("farfurii.out");

int gauss(int val){
    return (val * (val-1))>>1;
}
int main() {
    /*cerinta problemei este echivalenta cu:
    Sa se afiseze cea mai mica permutare lexicografic cu n inversiuni.
     Se stie ca o permutare desccrescatoare(n, n-1, ... 3, 2, 1) n*(n-1)/2 inversiuni, cele mai multe pt o permutare cu n elemente
     Astfel daca numarul de tacamuri k este de forma x*(x-1)/2, cu x nr. natural, atunci permutarea ceruta va arata astfel:
     1 2 ... n-x n n-1 .. n-x+1
     Daca K>x*(x-1)/2 atunci construim
     1 2 ... n-x-1 n n-1 .. n-x+1 n-x care are x*(x-1)/2 inversiuni
     Mutam elementul  n-((x+1)*n/2-k) inaintea lui n, scazand in acest fel numarul de inversiuni la k.
     */
    long long n,k, val = 0,aux = 0;
    cin>>n>>k;
    while(gauss(val)<=k)val++;

    for(long long i=1; i <= n-val;i++)cout<<i<<" ";

    if(gauss(val)>k) {
        aux = n - (gauss(val) - k);
        cout<<aux<<" ";
    }

    for(long long i=n;i> n-val;i--)cout<<i<<" ";
    return 0;
}