Revizia anterioară Revizia următoare
| 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 ...
Date de ieşire
În fişierul de ieşire mojosort.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| mojosort.in | mojosort.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
