Cod sursa(job #3133821)

Utilizator Maria_VerdesVerdes Maria-Ioana Maria_Verdes Data 27 mai 2023 00:54:40
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>

using namespace std;

ifstream f("farfurii.in");
ofstream g("farfurii.out");

long long int gauss(int x)
{
    return x * (x - 1) / 2; // vrem de fapt gauss(x - 1)
}

int main()
{
    int n, inv = 0; //nr de numere de care avem nevoie pt realizarea inversiunilor
    long long int k;
    f >> n >> k;
    f.close();
    while(gauss(inv) < k) //gauss(inv) numarul de inversiuni pe care le realizam cu inv nr
        inv++;
    for(int i = 1; i <= n - inv; i++)
        g << i << ' ';
    //daca am trecut peste k, va trebui sa scadem nr de inversiuni => mutam o val la stanga
    int dif = gauss(inv) - k;
    int val = n - dif; //valoarea care ne da numarul dif de inversiuni
    g << val << ' '; //daca nu am trecut peste k afisam n, deci e ok
    //afisam restul valorilor descrescator pt a obtine numarul de inversiuni
    for(int i = n; i > n - inv; i--)
        if(i != val)
            g << i << ' ';
    g.close();
    return 0;
}