Cod sursa(job #2301216)

Utilizator CristyXtremeSimion Cristian CristyXtreme Data 12 decembrie 2018 19:11:05
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
// Cautam numarul x astfel incat k sa fie cuprins intre suma primilor x - 1 termeni si a x termeni
// construim sirul 1 2 .. (n - x - 1) (n) (n - 1) ... (n - x) in acest moment numarul inversiunilor este  k' = x * (x + 1) / 2
// tot ce trebuie sa facem in continuare e sa inseram intre (n - x - 1) si (n) elementul care scazut din k' ne va da exact k inversiuni
// se observa ca elementul este n - (k' - k) si cum k' - k <= x se garanteaza ca trebuie sa luam un singur elemente

#include <stdio.h>

using namespace std;

int main() {
	freopen("farfurii.in", "r", stdin);
	freopen("farfurii.out", "w", stdout);
	long long int n, k;
	scanf("%lld %lld", &n, &k);
	long long int x = 1;
	while (k > x * (x - 1) / 2)
        x++;
    for (long long int i = 1; i <= n - x; i++)
        printf("%lld ", i);
    x--;
    long long int K = x * (x + 1) / 2, nr = n - (K - k);
    printf("%lld ", nr);
    for (long long int i = n; i >= n - x; i--)
        if (i != nr)
            printf("%lld ", i);
	return 0;
}