Pagini recente » Cod sursa (job #1152295) | Cod sursa (job #1087336) | Cod sursa (job #1508029) | Cod sursa (job #100029) | Cod sursa (job #2753773)
#include <fstream>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
/**
* problema se reduce la a determina cea mai mica permutare de n elemente din punct de vedere
* lexicografic pentru care numarul de inversiuni este k
* numarul de inversiuni este maxim n * (n - 1) / 2, deci cautam cate un t maxim astfel incat
* t * (t - 1) / 2 <= k
* numerele de la 1 la t vor aparea in ordine crescatoare, iar daca t * (t - 1) / 2 > k, trebuie
* sa afisam imediat dupa n - (t * (t - 1) / 2 - k) pentru a pastra numarul de inversiuni dorit,
* dupa care afisam restul numerelor in ordine descrescatoare
* @return
*/
int main() {
long long n, k, t = 1;
fin >> n >> k;
fin.close();
while (t * (t - 1) / 2 < k) {
++t;
}
for (long long i = 1; i <= n - t; ++i) {
fout << i << ' ';
}
long long dif = n - (t * (t - 1) / 2 - k);
fout << dif << ' ';
for (long long i = n; i > n - t; --i) {
if (i != dif) {
fout << i << ' ';
}
}
fout.close();
return 0;
}