Cod sursa(job #3134009)

Utilizator Adela_PetrePetre Adela Adela_Petre Data 27 mai 2023 21:11:18
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <iostream>
using namespace std;

ifstream in("farfurii.in");
ofstream out("farfurii.out");
int main(){
    int N, K, v;
    in >> N >> K;
    in.close();
    v = 0;
    while (v * (v - 1) / 2 < K)
        v++;
    //cel putin k inversiuni se pot obtine cu v numere
    for (int i = 1; i <= N - v; i++) //afisam crescator celelalte numere, care nu sunt implicate in inversiuni, pentru a genera cel mai mic lexicografic sir
        out << i << ' ';
    int total_inversiuni = (v * (v - 1) / 2); // trebuie sa scapam de total_inversiuni - k inversiuni
    int numar_mutat = total_inversiuni - K;
    numar_mutat = N - numar_mutat; // trebuie sa afisam in continuarea primelor "v" numere numarul cu ordinul "numar_mutat" incepand de la dreapta, pentru a obtine fix k permutari
    out << numar_mutat << " "; //daca erau fix k permutari, am fi avut oricum n, n - 1, n - 2, .... pentru ca "numar_mutat" ar lua valoarea n
    //afisam descrescator numerele care vor crea cele k permutari:
    for (int i = N; i > N - v; i--)
        //verificam sa nu afisam din nou "numar_mutat
        if (i != numar_mutat)
            out << i << ' ';
    out.close();
    return 0;
}