Cod sursa(job #2749719)

Utilizator ionut31Ioan Ionescu ionut31 Data 7 mai 2021 19:35:57
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.28 kb

#include <fstream>
#include <iostream>

using namespace std;

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

int main()
{
    long long N, K;
    long long inv_max; //inv_max este numarul maxim de inversiuni ale unei permutari cu numere de la 1 la N
                //(avem nr maxim de inversiuni atunci cand numerele sunt in ordine descrescatoare N, N-1,..., 2, 1) =>
                // inv_max = N-1 + N-2 + ... + 2 + 1 (suma lui Gauss cu numere de la 1 pana la N-1)

    fin >> N >> K;

    //calculam inv_max
    inv_max = (N-1)*N/2;

    if(K == 0) //daca nu avem nevoie de nicio inversiune, atunci afisam numerele in ordine crescatoare
    {
        for(int i = 1; i <= N; ++i)
            fout << i << " ";
        return 0;
    }
    else if(K == inv_max) //daca avem nevoie de numarul maxim de inversiuni, atunci afisam numerele in ordine descrescatoare
    {
        for(int i = N; i >= 1; --i)
            fout << i << " ";
        return 0;
    }
    else //numarul de inversiuni de care avem nevoie este intre 0 si inv_max
    {
        int i = 1;
        //Plecam de la numarul maxim de inversiuni inv_max(care apare atunci cand numerele sunt in ordine descrescatoare)
        //si alteram sirul descrescator de numere, renuntand la inversiuni astfel:
        //Luam pe rand numere de la coada si le plasam in sirul pe care il alcatuim(care va reprezenta rezultatul final),
        //cat timp ramanem  in urma acestor mutari cu un numar de
        //inversiuni suficient de mare pentru a satisface necesarul de inversiuni K;
        //pentru inceput, mutand ultimul numar de la coada, care este 1, renuntam la N-1 inversiuni, apoi mutand al doilea numar,
        //care este 2, renuntam la inca N-2 inversiuni si asa mai departe
        //cat timp ramanem cu suficiente inversiuni cat sa acoperim necesarul K
        //(pe caz general, la pasul i renuntam la N-i inversiuni)

        while(inv_max - (N - i) >= K)
        {
            inv_max -= (N - i);
            fout << i << " ";
            ++i;
        }
        i--; //pt ca in while se va creste i si inainte de pasul care nu se va face(pasul la care se opreste while-ul)

        if(inv_max == K) //while-ul s-a oprit cand am ajuns la numarul necesar de inversiuni
        {
            //atunci afisez numerel ramase
            //(pana la numerele care au fost deja afisate)
            //in ordine inversa pentru a genera numarul necesar de inversiuni ramase
            for (int j = N; j > i; --j)
                fout << j << " ";
        }
        else if(inv_max > K) //while-ul s-a oprit cand: 1) inca mai avem inversiuni in plus sau 2) nu s-a intrat in while
        {
            //1) Dupa executarea while-ului, am renuntat la numarul maxim de inversiuni la care se putea renunta,
            //mutand elementele de la coada in fata(asta va genera cea mai mica solutie in sens lexicografic).
            //Acum trebuie sa aflam pozitia care genereaz acel numar de inversiuni care inca este in plus
            //si sa mut elementul respectiv in fata(sa il afisez urmatorul in solutie), pentru a nu mai produce
            //acele inversiuni.

            //2) Daca nu se intra in while
            // (se intra automat pe ramura else if pt ca inv_max ramane cate este, deci mai mare decat K),
            //inseamna ca nu pot renunta la atatea inversiuni la cate s-ar renunta mutand
            //elementul din coada inceputul sirului, asa ca aflu direct
            //pozitia care imi produce inversiunile care sunt in plus, dupa care afisez restul de numere in ordine
            //descrescatoare pentru a genera cele K inversiuni necesare.

            long long inv = N - (inv_max - K);//calculez pozitia care imi genereaza inversiunile care sunt in plus
                                             //(numarul de inversiuni care sunt in plus = inv_max - K) si o afisez
            fout << inv << " ";

            //afisez numerel ramase
            //(in afara de pozitia care imi genera inversiuni in plus si pana la numerele care au fost deja afisate)
            //in ordine inversa pentru a genera numarul necesar de inversiuni ramase
            for (int j = N; j > i; --j)
                if (j != inv)
                    fout << j << " ";
        }
        return 0;
    }

}