Mohó Márton vállalkozó egy pályázaton meghirdetett munkák között válogat. Ismeri minden munka határidejét, és azt, hogy az adott munka elvégzése mekkora hasznot eredményez. Minden munka elvégzésére 1 napra van szüksége, és egy nap csak egy munkát tud elvégezni. (Megjegyzés Forrás Bence megközelítéséről: egy korrekt vállalkozó a szerdai határidőre vállalt munkát legkésőbb kedden elvégzi. Versenyfeladatokban meg szoktuk engedni, hogy a k. napra vállalt munkát még megcsinálhatjuk a k. napon (persze így csak estére lesz kész).)
FeladatKészíts programot, amely kiszámítja, hogy
BemenetA bemenet szöveges állomány első sora a munkák N (0 < N <= 10000) számát tartalmazza. A további N sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva. Az első szám, H a munka határideje (0 < H < 10000), a második P pedig a munka elvégzésével elérhető haszon (0 < P < 1000). Ha egy munka határideje K, az azt jelenti, hogy ha a munkát elvállaljuk, akkor azt a K-adik napig (a K. napon még lehet) be kell fejezni.
KimenetA kimenet szöveges állomány első sorába az elérhető legnagyobb hasznot kell írni! A második sorba azoknak a munkáknak a sorszámait kell kiírni, amelyek elvégzése az első sorba írt hasznot eredményezi, ha a munkákat ebben a sorrendben végzik el, azaz a sorban az i-edik munkát az i-edik napon.
Példa
Tesztadatok
CímkékA feladat forrása: olimpiai válogatóverseny 2001
Algoritmusok: mohó algoritmus, ütemezés
|
Programozás > Feladatok >
