Problem E
Gym Nut
Everyone knows the real reason why people work out. Not for
health reasons, or to maintain one’s youthful and athletic
frame, or because it’s fun. People work out excessively because
they want to annoy the crap out of everyone by being as
condescending as possible about it. Depending on how obsessed
one is about working out, different individuals have different
aggregate-nuisance, or AG-NU scores.
Most gym nuts don’t realize that this is not actually a good
trait, and your buddy Bob is no different. He knows you can
code, so he wanted you to devise an algorithm that can help him
maximize his AG-NU. Bob does a few different exercises, and
each one of them is assigned a different NU score. The total
score of all the exercises he does is called an AG-NU score.
While it would make sense to just do the exercises with the
highest NU scores, but Bob only has so much energy. Bob has a
maximum amount of energy that he can spend. If he chooses to do
back to back workouts, he loses energy by some cooldown factor.
Taking an hour off doesn’t add points to his AG-NU score, but
it resets his energy back to his max. This factor is multiplied
by the maximum energy he could have spent in the previous
workout to determine how much energy he can spend in the next
one. Bob gives you a list of exercises that he can do every
five minutes, and the maximum possible energy he could spend
for each of those workouts. For a given workout, Bob spends as
much energy as he can, the minimum of his max energy at the
time or the max energy for the exercise.
It’s your job to maximize his AG-NU (equivilant to energy
spent) within the constraints of how much energy he has.
Input
There are three lines of input to this program.
Line $1$: Composed of two
space-separated integers ($e$ $n$). $e$ ($10
\leq e \leq 10\, 000$) is the amount of energy that this
Bob can expend during an exercise, measured in some arbitrary
unit of energy. It decreases by a factor of $c$ if Bob chooses to not take a break
after the previous workout. $n$ ($1
\leq n \leq 1\, 000$) is the total number of workouts
Bob can complete if he completes every one. The energies for
the workouts are listed on line $3$. Line $2$: Composed of one real number with
up to two decimal places ($c$). $c$ is the cooldown factor mentioned
above ($0 \leq c \leq 1$).
Line $3$: Composed of
$n$ space-separated
integers ($1 \leq x \leq 1\,
000$). They represent the exercise available for Bob to
do each $5$ minutes. He
can decide to do the exercise and gain NU points equal to the
lesser of his current max energy or the energy of the exercise,
or he can take a break to reset his max energy.
Output
The output is always composed of one line. Line $1$: Bob’s optimal AG-NU value. This is a real number that is correct within a relative or absolute error of $10^{-6}$. It represents the total amount of energy that Bob has expended by completing the optimal workout routine for the given exercises.
| Sample Input 1 | Sample Output 1 |
|---|---|
100 4 0.5 100 60 40 20 |
187.5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
100 4 0.5 50 50 10 50 |
150.0 |
