Cod sursa(job #2754881)

Utilizator iustin.pericicaPericica Iustin iustin.pericica Data 26 mai 2021 17:21:47
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>

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

int main(){

    int n, k;
    fin>>n>>k;

    // avem nevoie sa cautam numarul de inversiuni minim care sa cuprinda numarul k. C de n luate cate 2 = n*(n-1)/2.

    int pornire = 1;
    while((pornire*(pornire-1)/2) < k){
        pornire++;
    }
    for(int i = 1;i<n-pornire+1;++i){
        fout<<i<<" ";
        // afisam toate numerele care nu fac nicio inversiune
    }

    long long x = n - ((pornire * (pornire - 1))/2 - k);
    fout<<x<<" ";
    // pentru ca mutand un element din ,,permutarea" care ne intereseaza dpdv semantic la stanga se scade o schimbare de semn, mutand x pozitii se scad x mutari de semn
    // astfel mutam un element din permutarea n, n-1, n - 2, ..... n - pornire + 1 la stanga, pozitia elementului este chiar diferenta dintre combinare - k

    for(int i = n;i>n-pornire;--i){
        if(x != i){
            fout<<i<<" ";
        }
    }

    return 0;
}