Pagini recente » Cod sursa (job #839812) | Cod sursa (job #941863) | Cod sursa (job #1093916) | Cod sursa (job #952961) | Cod sursa (job #2428686)
// Determinarea permutarii de lungime N cu K inversuri
// minima lexicografic O(N^2)
#include <iostream>
#include <fstream>
#define MAXN 100001
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
int N, K, maxInv;
bool viz[MAXN] = {false};
// Gasirea al x-lea element care nu a fost folosit
int firstAvailable(int x) {
for (int i = 1; i <= N; ++i) {
if (viz[i] == false) {
--x;
if (x == 0) {
viz[i] = true;
return i;
}
}
}
return 0;
}
int main()
{
f >> N >> K;
for (int i = 1; i <= N; ++i) {
maxInv = (N - i)*(N - i - 1) / 2;
if (K <= maxInv) {
g << firstAvailable(1) << ' ';
} else {
g << firstAvailable(K - maxInv + 1) << ' ';
K = maxInv;
}
}
return 0;
}