Programozás‎ > ‎Feladatok‎ > ‎

Pályázatok

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).)

Feladat

Készíts programot, amely kiszámítja, hogy
  • mekkora az elérhető legnagyobb összhaszon,
  • mely munkákat végezzük el, hogy az összhaszon a lehető legnagyobb legyen!

Bemenet

A 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.

Kimenet

A 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

Bemenet  Kimenet
6
3 60
4 40
1 10
3 30
7 70
4 20
220
6 4 1 2 5


Tesztadatok

palyazat.zip /Uray János javította, 2010-ben/

Címkék

A feladat forrása: olimpiai válogatóverseny 2001
Algoritmusok: mohó algoritmus, ütemezés