SPOJ.com - Problem GOODMEAL

GOODMEAL - Eat a Good Meal

You’re hungry, and you’re about to be executed. You’re planning your last meal, and you want to be sure you maximize your enjoyment. Pizza, for example, provides a 7/10 enjoyment level per slice, but takes up 20% of your available stomach space per slice. Fudge, on the other hand, provides a 9/10 enjoyment level per square and uses only 2% of your available stomach space, but you can only eat 3 squares before you get sick of it.

Given a potential menu by your captors, including the enjoyment level it provides per unit, the stomach space required per unit, and the maximum number of units you can enjoy, plan the perfect final meal.

Input:
First line is an integer, representing the number of different items on the menu.
Each subsequent line is one menu item, formatted as “name spacePerUnit enjoymentPerUnit maxUnits”.

Output:
The maximum amount of enjoyment you can get from the available menu within 100 stomach space, as an integer.

Input	Output
3 Pizza 20 7 5 Fudge 2 9 3 Soda 5 3 3	61
4 Burrito 10 4 10 Apple 5 5 2 Pie 5 8 2 Cookies 2 4 4	70
4 Steak 20 8 1 Potato 10 4 2 Vegetables 10 1 10 Sundae 15 6 2	31

Submit solution!

Added by:	Ben Dilts
Date:	2012-10-12
Time limit:	0.400s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64

hide comments



2012-10-17 17:46:48 :D Re: Francky. No, solving problems it not required and that's very good, because some prominent problems setters have 0 submissions. Of course that often leads to weak entries, but SPOJ philosophy is to give easy access to problem setting and moderate what comes. I guess there should be a better difficulty grouping (not just classical/tutorial), but it's not for me to decide. I also would like to see more variety and hard problems. This one is pretty standard, but with 2000+ tasks some similarities are unavoidable and small variations are acceptable. As for moving to tutorial, I myself move only the problems don't need an actual algo (only trivial/brute-force approach). I bigger issue here is that the test cases seem to be very, VERY weak. So yes for now moving it to tutorial. If cases they are made stronger (i.e. bigger), I'll move it back.
2012-10-17 15:36:57 Andres R. Arrieche S. [UCLA-ve] @Ashish it is just one test case
2012-10-17 13:52:17 Ashish How do I know if input has finished?
2012-10-17 11:36:04 Aman Gupta Why are all the new problems without constraints?
2012-10-17 11:35:45 Francky WA** BANK isn't yet a very similar problem ??? There's no need to multiply same problems. --- I thought we need to solve some few problems before becoming a problemsetter, it avoid such derangements. You didn't solve any at that time !!!