Fişierul intrare/ieşire:	mojosort.in, mojosort.out	Sursă	Lot Seniori Tulcea 2018, baraj 1
Autor	Bogdan Iordache	Adăugată de	Tiberiu Musat •Tiberiu02
Timp execuţie pe test	5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Mojosort

Ameţit după petrecerea răufăcătorilor, Mojo Jojo s-a dus la Profi să îşi cumpere N banane numerotate cu indici distincţi de la 1 la N (acestea formează o permutare). Cu cât indicele unei banane este mai mare, cu atât banana este mai gustoasă. Ca orice altă maimuţă de speţă nobilă, Mojo Jojo preferă să păstreze ce e mai bun la sfârşit. Din acest motiv, acesta şi-ar dori să le mănânce în ordine de la banana cu indicele cel mai mic (banana cu indicele 1), până la banana cu indicele N.

Din păcate, Mojo este mult prea ameţit ca să stea să sorteze banane după bunul plac, motiv pentru care le va mânca în ordinea în care le-a cumpărat. Fiind un geniu în bananologie, Mojo a definit costul unei astfel de permutări ca fiind numărul de inversiuni. Înainte de a se apuca de mâncat, Mojo s-a hotărât să minimizeze numărul de inversiuni ale permutării având la dispoziţie două tipuri de operaţii:

• Monkey Shot: Mojo alege două elemente consecutive din permutare şi le inversează
• Monkey Punch: Mojo dă cu pumnul în masă şi toate bananele se permută random cu probabilitate uniformă (se dă random shuffle la permutare)

Deşi Mojo Jojo este un geniu în algoritmică şi programare competitivă, acesta nu se simte suficient de bine cât să deducă o strategie optimă de minimizare a numărului de inversiuni într-o permutare. Dându-se un număr natural K, Mojo Jojo poate să aplice maxim K operaţii descrise mai sus. Calculaţi expected value ale numărului de inversiuni dacă Mojo ar aplica o strategie optimă.

Date de intrare

Fişierul de intrare $$mojosort.in$$ conţine pe prima linie T, reprezentând numărul de teste. Urmează apoi T perechi de linii: pe prima dintre acestea se citesc două numere întregi N şi K, cu semnificaţia din enunţ, iar pe cea de a doua linie se citesc N numere întregi distincte, despărţite prin câte un spaţiu, reprezentând indicii bananelor în ordinea în care le-a cumpărat Mojo Jojo.

Date de ieşire

În fişierul de ieşire mojosort.out va conţine răspunsul pentru fiecare din cele T
teste. Puteţi alege să afişaţi aceste numere în două moduri:

• mojo-mode: afişaţi un număr R = P * Q^-1 modulo 10⁹ + 7, unde prin X^-1 s-a notat inversul modular al lui X faţă de 10⁹ + 7, iar răspunsul este P / Q, cu P şi Q numere naturale, prime între ele
• jojo-mode: afişaţi un număr real reprezentând răspunsul exact cu o eroare de cel mult 10^-6

Dacă alegeţi să afişaţi în mojo-mode vreun rezultat, afişaţi pe prima linie a fişierului mesajul “mojo”. Altfel, afişaţi mesajul “jojo”. Toate cele T rezultate trebuie afişate conform modelului selectat.

Restricţii

• 1 ≤ N, T ≤ 300
• 0 ≤ K ≤ 1 000 000 000
• Dacă alegeţi jojo-mode veţi obţine 60% din punctajul testului respectiv.
• Pentru 40% din teste avem N ≤ 50 şi T ≤ 50

Exemplu

.

Cum se trimit solutii?