Cod sursa(job #3134383)

Utilizator teosimirasTeofil Simiras teosimiras Data 28 mai 2023 22:40:14
Problema Farfurii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>

int main() {
    std::ifstream fisier_intrare("farfurii.in");
    std::ofstream fisier_iesire("farfurii.out");

    long long int numar_total_elemente = 0, suma_inversiuni = 0, numar_curent = 1, elemente_ramanente = 0, numar_urmator = 0;
    
    fisier_intrare >> numar_total_elemente >> suma_inversiuni;
    
    // Cât timp suma_inversiuni este mai mare decât numărul maxim de elemente care pot urma numărul curent
    while (suma_inversiuni > (numar_total_elemente - numar_curent) * (numar_total_elemente - numar_curent - 1) / 2) {
        // Scriem valoarea curentă a lui numar_curent în fisierul de ieșire și apoi creștem numar_curent cu 1
        fisier_iesire << numar_curent << " ";
        numar_curent++;
    }
    // Calculăm câte elemente trebuie să urmeze numărul curent astfel încât suma totală a acestora să fie egală cu suma_inversiuni
    elemente_ramanente = suma_inversiuni - (numar_total_elemente - numar_curent) * (numar_total_elemente - numar_curent - 1) / 2;
    numar_urmator = numar_curent + elemente_ramanente;

    // Scriem în fisierul de ieșire numărul următor care, urmat de elemente_ramanente elemente mai mici decât el, va face suma să fie suma_inversiuni
    fisier_iesire << numar_urmator << " ";
    
    // Apoi completăm restul permutării cu numerele care au rămas, în ordine descrescătoare, excluzând numărul pe care tocmai l-am scris
    for (int i = numar_total_elemente; i >= numar_curent; i--)
        if (i != numar_urmator) {
            fisier_iesire << i << " ";
        }
}