 |
Az I/S. 33. feladat (2019. február) |
I/S. 33. Egy adatsokaságban \(\displaystyle N\) féle adat van. Tudjuk minden adatról, hogy hányszor szerepel az adatsokaságban, és tudjuk azt is, hogy egy adott típusú adat törlése vagy beszúrása mennyibe kerül. Adjuk meg minden adattípusra, hogy minimum milyen költséggel érhető el adatok törlésével és beszúrásával, hogy ez az adattípus (is) az adatsokaság módusza legyen.
Bemenet: az első sorban az adattípusok \(\displaystyle N\) száma szerepel. A második sorban \(\displaystyle N\) darab szám: az \(\displaystyle i\). szám azt mondja meg, hogy az \(\displaystyle i\). adattípus hányszor szerepel az adatsokaságban. A harmadik sorban \(\displaystyle N\) darab szám van: az \(\displaystyle i\). szám azt mondja meg, hogy az \(\displaystyle i\). adattípusú adat beszúrása vagy törlése mennyibe kerül.
Kimenet: egy sorba írjunk ki \(\displaystyle N\) darab számot: az \(\displaystyle i\). szám annak a minimális költsége, ami szükséges ahhoz, hogy az \(\displaystyle i\). adattípus módusz legyen.
Példa:
Korlátok: \(\displaystyle 2\le N\le {10}^{5}\), \(\displaystyle 0\le \text{a}\) 2. és 3. bemeneti sorban levő \(\displaystyle \text{számok} \le {10}^{9}\). Időlimit: 0,5 mp.
Értékelés: a pontok 20%-a kapható, hogyha \(\displaystyle N\le 100\), a 2. és 3. bemeneti sorban levő \(\displaystyle \text{számok}\le 100\); további 10% kapható, ha a 2. sor számai egyenlők; további 20% kapható, ha \(\displaystyle N\le 1000\); további 10% kapható, ha a 2. és 3. bemeneti sorban levő \(\displaystyle \text{számok}\le {10}^{6}\); további 40% kapható az eredeti korlátokra.
Beküldendő egy is33.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ő környezetben futtatható.
(10 pont)
A beküldési határidő 2019. március 11-én LEJÁRT.
Statisztika:
5 dolgozat érkezett. 10 pontot kapott: Csertán András, Horcsin Bálint, Noszály Áron. 9 pontot kapott: Szente Péter. 6 pontot kapott: 1 versenyző.
A KöMaL 2019. februári informatika feladatai