 |
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:
| Bemenet (a / jel sortörést helyettesít) | Kimenet |
| 6 / 4 4 2 5 1 5 | 2 |
| 4 / 4 3 2 1 | 3 |
| 4 / 1 2 3 4 | 0 |
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