Feladat: I/S.33 Korcsoport: - Nehézségi fok: -
Füzet: 2019/február, 101. oldal  PDF  |  MathML 

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Egy adatsokaságban 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 N száma szerepel. A második sorban N darab szám: az i. szám azt mondja meg, hogy az i. adattípus hányszor szerepel az adatsokaságban. A harmadik sorban N darab szám van: az i. szám azt mondja meg, hogy az i. adattípusú adat beszúrása vagy törlése mennyibe kerül.
Kimenet: egy sorba írjunk ki N darab számot: az i. szám annak a minimális költsége, ami szükséges ahhoz, hogy az i. adattípus módusz legyen.
Példa:

 
Standard bemenetStandard kimenet    (a  /  jel sortörést helyettesít)110 17 3 0 64 71 24 27 16 0 14   8 4 5 8 1 1 2 2 4 8 11 6 1 2 17 24 4 5 4 1 2
 

Korlátok: 2≤N≤105, 0≤a 2. és 3. bemeneti sorban levő számok≤109. Időlimit: 0,5 mp.
Értékelés: a pontok 20%-a kapható, hogyha N≤100, a 2. és 3. bemeneti sorban levő számok≤100; további 10% kapható, ha a 2. sor számai egyenlők; további 20% kapható, ha N≤1000; további 10% kapható, ha a 2. és 3. bemeneti sorban levő számok≤106; 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ó.