Pagini recente » Cod sursa (job #2576738) | Cod sursa (job #1460947) | Cod sursa (job #1399077) | Cod sursa (job #1574870) | Cod sursa (job #2753268)
#include <iostream>
using namespace std;
// Toate long long ca sa nu se poata ajunge la un overflow (diff. dintre 90p si 100p)
long long n, k, combN = 1, adjust;
int main() {
freopen("farfurii.in", "r", stdin);
freopen("farfurii.out", "w", stdout);
cin >> n >> k;
// Calculeaza de ce n ai nevoie astfel incat combinari de n luate cate 2 sa-l poata cuprinde pe k
while (combN * (combN - 1) / 2 < k) {
combN++;
}
// E nevoie doar de combN numere pentru a avea numarul k de inversiuni. Deci primele n-combN nu ne intereseaza,
// asa ca le punem in ordine crescatoare (ca sa nu creeze cumva inversiuni).
for (long long i = 1; i <= n - combN; i++) {
cout << i << " ";
}
// combN * (combN-1) / 2 e foarte probabil sa fie Strict mai mare decat k. Deci trebuie sa mutam un element din
// pozitia lui obisnuita (din sirul descrescator), pentru ca efectul lui asupra numarului de inversiuni sa fie
// atenuat. Acel numar este adjust.
adjust = n - ((combN * (combN - 1)) / 2 - k);
cout << adjust << " ";
// Afiseaza restul numerelor (excluzandu-l pe adjust) in ordine descrescatoare,
// pentru a obtine numarul dorit de inversiuni
for (long long i = n; i > n - combN; i--) {
if (i != adjust) {
cout << i << " ";
}
}
return 0;
}