Pagini recente » Cod sursa (job #2384450) | Cod sursa (job #3224140) | Cod sursa (job #3137048) | Cod sursa (job #2767155) | Cod sursa (job #1838709)
#include <fstream>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
/*
* problema cere defapt generarea
* permutarii minim lexicografica, cu L inversiuni
* permutarea se imparte in 3 parti: - elementele 1, 2, 3, ... x nemodificate
* - un element din multimea x+1 ... N
* - restul elementelor ramase, in ordine descrescatoare
*/
int main(){
long long N, K;
fin >> N >> K;
// plecand de la permutarea identica,
// incerc sa las cat mai multe elemente de la inceput nefolosite
int i = 0;
while (i * (i + 1) / 2 < K)
i++;
int ramase = i * (i + 1) / 2 - K; // numarul de inversiuni ramase de facut cu elementul special
// pot afisa primele elemente de care nu am nevoie
for (int j = 1; j <= N - i - 1; ++j)
fout << j << " ";
// afisez elementul special
fout << N - ramase << " ";
// restul elementelor trebuie sa genereze numar maxim de inversiuni
for (int j = N; j >= N - i; --j)
if (j != N - ramase)
fout << j << " ";
return 0;
}