Az I/S. 69. feladat (2023. február)

I/S. 69. Adott egy $\displaystyle N$ elemű $\displaystyle T$ tömb, melynek $\displaystyle i$-edik elemét $\displaystyle T[i]$-vel jelöljük (1-től indexelve). Egy $\displaystyle (i,j)$ számpárt inverziónak nevezünk, ha $\displaystyle 1 \le i < j \le N$ és $\displaystyle T[i] > T[j]$. Szeretnénk a tömbben előforduló inverziók számát csökkenteni, és ehhez pontosan egy elemét törölhetjük a tömbnek. Adjuk meg, hogy minimum mennyi az inverziók száma a $\displaystyle T$ tömbben, miután annak egy tetszőleges elemét töröltük.

A bemenet első sorában az $\displaystyle N$ szám található, a tömb hossza. A második sorban $\displaystyle N$ szám található szóközzel elválasztva, a tömb elemei. A kimenet egyetlen sorában egy szám szerepeljen: a törléssel kapható legkisebb inverziószám.

Minták:

Magyarázat (1. példa): ha töröljük a tömb 5. elemét, akkor az új tömb: $\displaystyle [4, 4, 2, 5, 5]$, melyben az inverziók száma 2, és ez a legkisebb elérhető inverziószám.

Korlátok: $\displaystyle 2 \le N \le 10^{5}$; $\displaystyle 1 \le T[i] \le 10^{5}$ egész számok. Időkorlát: 0,4 mp.

Értékelés: a pontok 30%-a kapható, ha a program helyes kimenetet ad az $\displaystyle {N \le 100}$ esetekben. További 30% kapható, ha a program helyes kimenetet ad az $\displaystyle {N \le 1000}$ esetekben.

Beküldendő egy is69.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2023. március 16-án LEJÁRT.

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Zádor-Nagy Zsombor.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
1 pontot kapott:	3 versenyző.

A KöMaL 2023. februári informatika feladatai