Cod sursa(job #2903372)

Utilizator AndreiAncutaAndrei Ancuta AndreiAncuta Data 17 mai 2022 15:34:46
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>

int main() {
    std::ifstream ifs("farfurii.in");

    int n, k;
    ifs >> n >> k;
    ifs.close();

    // 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.

    std::ofstream ofs("farfurii.out");

    // Print non-reversed
    for (int i = 1; i <= n - reversed_len; ++i) {
        ofs << i << ' ';
    }

    // 1-indexed
    int moved_num = n - (comb - k);
    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