Pagini recente » Cod sursa (job #586467) | Cod sursa (job #2380643) | Cod sursa (job #1666197) | Cod sursa (job #1273262) | Cod sursa (job #2903379)
#include <fstream>
int main() {
std::ifstream ifs("farfurii.in");
int n, k;
ifs >> n >> k;
ifs.close();
std::ofstream ofs("farfurii.out");
// Smallest combination that is greather than k
int reversed_len = 2;
long long comb = 1;
while (comb <= k) {
comb = comb + reversed_len;
++reversed_len;
}
// Reverse the last reversed_len numbers to create comb inversions
// Now we need to remove (comb - k) inversions to reach k, by moving a
// number from the reversed sequence before the sequence.
// Print non-reversed
for (int i = 1; i <= n - reversed_len; ++i) {
ofs << i << ' ';
}
// 1-indexed
int moved_num = n - (comb - k);
if (moved_num > 0) {
ofs << moved_num << ' ';
}
// Print remaining reversed
for (int i = n; i >= n - reversed_len + 1; --i) {
if (i != moved_num) {
ofs << i << ' ';
}
}
ofs << '\n';
ofs.close();
return 0;
}
// 2C2 = 1
// 3C2 = 2C2 + 2 = 1 + 2 = 3
// 4C2 = 3C2 + 3 = 3 + 3 = 6
// 5C2 = 4C2 + 4 = 6 + 4 = 10
// 1 2 3 7 6 5 4 => 6 inv
// 1 2 7 6 5 4 3 => 10 inv