Pagini recente » Cod sursa (job #2546181) | Cod sursa (job #832609) | Cod sursa (job #2137959) | Cod sursa (job #1347987) | Cod sursa (job #2749719)
#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;
}
}