5
$\begingroup$

You have recently caught N Pokemon and you also have M Pokemon candy bars. You can evolve any of your Pokemon by paying X candy bars. Alternatively, you can sell any of your Pokemon for a price of Y candy bars. You cannot sell an evolved Pokemon.

Compute the maximum number of Pokemon you can evolve.

Improve this question
$\endgroup$
5
  • 25
    $\begingroup$ You can evolve Z Pokemons :D $\endgroup$ – Bálint Budavölgyi May 11 '18 at 12:15
  • $\begingroup$ This seems less like a puzzle and more like a simple math problem. Maybe math.SE would be a better place to ask. $\endgroup$ – BlueRaja - Danny Pflughoeft May 11 '18 at 17:00
  • 2
    $\begingroup$ Honestly it sounds like a reworded homework problem...I can't see this as a puzzle and it will not be received well on Math.SE $\endgroup$ – kaine May 11 '18 at 17:37
  • 1
    $\begingroup$ Two people commented that this looks like a math problem, not a puzzle. Two people agreed enough to upvote one of those comments. At a minimum, one of these people has enough reputation to cast close votes. And yet there are just two downvotes, and zero votes to close. If you think it doesn't belong here, you're part of this community — you have a voice, and a vote: use it. (@kaine, $@$BlueRaja, et al) $\endgroup$ – Rubio♦ May 12 '18 at 11:56
  • $\begingroup$ @Rubio: I would close-vote if I were able to. The best I can do is flag, which I did. $\endgroup$ – BlueRaja - Danny Pflughoeft May 17 '18 at 17:16
10
$\begingroup$

Let's say $E$ is the maximum number of Pokemons we can evolve and $S$ is the number of Pokemons we sell, then we have:

(A): $E = \left\lfloor\frac{M+YS}{X}\right\rfloor \le \frac{M+YS}{X}$
(B): $S+E \le N$

(B) gives

$S \le N-E$
$\frac{M+YS}{X} \le \frac{M+Y(N-E)}{X}$

So replacing the first part with $E$ thanks to (A) we obtain

$E \le \frac{M+Y(N-E)}{X}$
$E + \frac{Y(E-N)}{X} \le \frac{M}{X}$
$E\left(\frac{Y}{X}+1\right) - \frac{YN}{X} \le \frac{M}{X}$
$E \le \frac{\frac{M}{X} + \frac{YN}{X}}{\frac{Y}{X}+1}$
$E \le \frac{M+YN}{Y+X}$

Which means, for us to get the highest possible value for E, that:

$E = \left\lfloor\frac{M+YN}{Y+X}\right\rfloor$
But with the limitation, as @BlueHairedMeerkat pointed out in the comments, that E cannot exceed N, such as the actual, more exact answer would be
$E = \text{Min}\left(\left\lfloor\frac{M+YN}{Y+X}\right\rfloor, N\right)$

As an example:

Let's say we have 6 Pokemons (N) and 11 Candy bars (M). We can evolve a Pokemon for 4 candies (X) and sell one for 3 candies (Y). Trivially, we find that selling 2 Pokemons (for 6 candies) gives us a total of 17 candies in order to evolve the 4 Pokemons we have left (with one candy left). What says the formula?
$E = \left\lfloor\frac{11+3*6}{3+4}\right\rfloor = \left\lfloor\frac{29}{7}\right\rfloor = \lfloor4.142...\rfloor = 4$
So it seems quite right (at least with this example).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Technically, it's the smaller of that and N; if M is very large relative to X and Y, and N is small, your formula will give a value larger than the number of Pokemon you have. (e.g. M = 10, N = X = Y = 1, your formula gives 5, but you only have 1 Pokemon.) $\endgroup$ – BlueHairedMeerkat May 11 '18 at 14:08
  • $\begingroup$ @BlueHairedMeerkat Indeed, I will correct it, thank you! $\endgroup$ – Keelhaul May 11 '18 at 14:13
3
$\begingroup$

The maximum number we can evolve is

$E=\frac{M+YS}{X}$.

Also, the maximum number we can evolve from the other way around is

$E=\frac{Y(N-S)}{Y}=\frac{-YS+YN}{Y}$.

The mediant of these two is

$$\frac{M+YS}{X} \oplus \frac{-YS+YN}{Y} = \frac{M+YN}{X+Y}$$

which gives the optimum number of evolves.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How do you get the maximum number you can sell? And how can this be different than N? $\endgroup$ – Keelhaul May 11 '18 at 14:17
  • $\begingroup$ maximum number you can sell is N-E, assuming E is the most you can evolve. $\endgroup$ – JMP May 11 '18 at 14:28
  • $\begingroup$ Yes, but how does that fit with your second line? $\endgroup$ – Keelhaul May 11 '18 at 14:31
  • $\begingroup$ we have defined E in two ways, and taken the mediant (after a few edits!) $\endgroup$ – JMP May 11 '18 at 14:38
1
$\begingroup$

I know some other people have answered, but I'm going to take a stab at it before looking at other answers.

Let $s$ be the number of sold Pokémon. Then we'll define $P(s)$ to be the potential number of Pokémon we can evolve. Meaning if $N$ was infinite, how many we could evolve after selling $s$. $P(s) = \frac{M}{X} + \frac{Ys}{X}$ This is because we start with $M$ bars, and we get $Y$ for each sale, and we make $s$ sales. So our total number of bars is $M + Ys$. Since it takes $X$ bars to evolve on Pokémon, we divide by $X$ to get our final answer.

Now, let $T(s)$ be the total number of Pokémon we have left after making $s$ sales. Then $T(s) = N - s$.

Now, the total number of evolutions we can do after making $s$ sales is $E(s) = min(P(s), T(s))$. If our potential evolutions is less than or equal to the number of Pokémon we have left, we can carry out all the potential evolutions. If the potential evolutions is greater than the total number of Pokémon we have left, we can evolve all remaining Pokémon. So now all that's left is to find the maximum of $E(s)$.

$P(s)$ is an increasing linear function, and $T(s)$ is a decreasing linear function. So this means that their intersection will be the maximum of $E(s)$. We can find this by setting them equal to each other and solving for $s$.

This gives us $s = \frac{N - \frac{M}{X}}{1 + \frac{X}{Y}}$. This is not always an integer, so to find the optimal number of sales, we merely round this to the nearest integer. If it is equally close to two integers, (ends in $.5$, then rounding either way gives the same result, and they are both valid answers.

Now we have the optimal number of sales, so plug this back into $E(s)$ to get the maximum number of evolutions. We get $min\left(\frac{M}{X} + \frac{Y \cdot round\left(\frac{N - \frac{M}{X}}{1 + \frac{X}{Y}} \right)}{X}, N - round\left(\frac{N - \frac{M}{X}}{1 + \frac{X}{Y}}\right)\right)$.

This can also be a non-integer, but we can't round it to the nearest integer. If, for example, by making the optimal number of sales, we can get $3.8$ evolutions, there's no way to get $4$ evolutions. So we have to always round down. So my final answer for the maximum number of evolutions is $floor\left(min\left(\frac{M}{X} + \frac{Y \cdot round\left(\frac{N - \frac{M}{X}}{1 + \frac{X}{Y}} \right)}{X}, N - round\left(\frac{N - \frac{M}{X}}{1 + \frac{X}{Y}}\right)\right)\right)$.

This looks longer than the other answers, so I've probably overcomplicated things, but oh well. I'm pretty sure it's right.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.