Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Minimal Ball Cost

Rick Grimes wants to buy some gifts for his son, Coral. He decides to buy some crystal balls. But he is confused because of the deal offered by the shopkeeper. Help him by writing a program.

He wants B black balls and W white balls.
The cost of each black ball is X units.
The cost of each white ball is Y units.
The cost of converting each black ball into white and vice versa is Z units.

Print the minimum cost to get the required number white and black balls.


Line 1: Five numbers B, W, X, Y, Z
Output
One integer showing the minimum cost to get the required number of white and black of balls.
Constraints
0≤ X,Y,Z,B,W≤ 10000

Solution

Without changing the color, the cost is given by

\[r = BX + WY\]

As we can color \(k\) elements from black to white and vice versa when negative, we can express this in terms of a shift parameter \(k\)

\[
\begin{array}{rl}
r &= (B-k)X + (W+k)Y + |k|Z\\
  &= BX - kX + WY + kY + |k|Z\\
  &= BX + WY + k(Y-X) + |k|Z\\
\end{array}
\]

We're interested in the minimum on the interval \([-W, B]\) only. As we work with two lines, we must consider the end-points on the interval for \(k\) only, which are the three points at \(-W, B, 0\). Based on this observation, we get:

\[BX+WY + \min(B(Y-X) + |B|Z, W(X-Y) + |W|Z, 0)\]

Looking at the problem statement reminds us, that 0≤ B,W≤ 10000, which allows us to remove the absolute values:

\[BX+WY + \min(B(Y - X + Z), W(X - Y + Z), 0)\]

A JavaScript implementation can then be formulated analogously:

[B, W, X, Y, Z] = readline().split(" ");

print(B * X + W * Y + Math.min(
    B * (Y - X + Z),
    W * (X - Y + Z),
    0));

Go to overview