Cod sursa(job #2892900)

Utilizator EduardSanduSandu Eduard Alexandru EduardSandu Data 23 aprilie 2022 22:12:00
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
using namespace std;

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

// pornim de la ideea ca daca vrem sa facem o permutare minima
// trebuie sa fie de genul 1 2 3 4 20 19 18 17 .... 6 5 4
// adica trebuie sa aiba o portiune crescatoare de lungime maxima la inceput
// iar restul sa fie in ordine descrescatoare

int main()
{
    int n,i,j,k,indicemax, CNT, numar_dif;

    fin>>n>>k;
    for(indicemax = 1; (indicemax * (indicemax-1)) / 2 <k; indicemax++)// de aici incepe portiunea descendenta
    {
        // calculez cat de mare va fi portiunea de numere in ordine descresc.
        // combinari de n luate cate 2 va fi maximul, deci trebuie sa ne incapa in k
    }

    for(i = 1; i<=n-indicemax; i++)
    {
        fout<< i << ' '; //afisam portiunea ascendenta
    }

    CNT = indicemax * (indicemax-1) / 2 - k; // asta este diferenta dintre urmatoarea lungime de
    // portiune descendenta dar pentru care nu mai avem suficiente inversiuni, asa ca scoatem din ea al CNT - lea element
    // spre exemplu, din permutarea 5 4 3 2 1 care are 10 inversiuni, daca il scoatem pe 3 si il punem in fata scapam de 2 inversiuni, pentru ca nu va mai avea
    // cele 2 elemente mai mari in fata lui

    numar_dif = n - CNT; // afisam numarul cu pricina de mai sus

    fout << numar_dif << ' ';

    for(i = n; i >= n - indicemax + 1; i--)
    {
       if(numar_dif != i) // afisam portiunea descrescatoare fara numarul neserios gasit mai sus
            fout << i << ' ';
    }

    return 0;
}