Državno natjecanje 2018. godine za 3. i 4. razred Srednje Škole - 1. zadatak - Dan 1

Organizatori natjecanja odlučili su počastiti natjecatelje sljedećim inovativnim zadatkom:

Zadan je broj N i niz od N različitih prirodnih brojeva Ai (1 ≤ Ai ≤ N). Odredite broj inverzija u nizu. Inverzija je par brojeva iz niza (Ai, Aj) za koje vrijedi i < j i Ai > Aj.

Taman prije početka natjecanja, kad je već sve trebalo biti spremno, organizatori su shvatili da su zbog greške na hard disku izgubili niz brojeva u ulaznoj datoteci jednog test podatka. Kako bi ispravili grešku, odlučili su rekonstruirati niz na temelju jedinih sačuvanih podataka - duljine niza N i konačnog rješenja za taj test primjer, broja K.

ULAZNI PODACI

U jedinom retku nalaze se cijeli brojevi N (1 ≤ N ≤ 10^6 ) i K (0 ≤ K ≤ N ⋅ (N - 1) / 2).

Napomena: Obratite pažnju da broj K ne stane uvijek u 32-bitni tip podataka. Preporučuje se korištenje long long u C/C++.

IZLAZNI PODACI

U jedan redak ispišite niz od N različitih prirodnih brojeva Ai (1 ≤ Ai ≤ N), odvojenih razmakom, za koji je broj inverzija jednak K. Ako postoji više mogućih rješenja, ispišite bilo koje. Možete pretpostaviti da će rješenje uvijek postojati.

PRIMJERI TEST PODATAKA

ulaz

5 6

izlaz

2 5 4 1 3

ulaz

8 7

izlaz

3 2 1 6 4 7 8 5

ulaz

6 15

izlaz

6 5 4 3 2 1

Objašnjenje

Pojašnjenje prvog primjera: U nizu se nalaze sljedeće inverzije: (2, 1), (5, 4), (5, 1), (5, 3), (4, 1) i (4, 3).