Official

B - Balls of Three Colors Editorial by evima


Let us find the minimum number of operations needed to end up with only red balls.

Assume \(G \geq B\) without loss of generality. Let us focus on the difference between the numbers of green balls and blue balls. No operation changes this value modulo \(3\). From the fact that this value eventually becomes \(0\), it is necessary that \(G \equiv B \bmod 3\).

When \(G \equiv B \bmod 3\), we can turn all balls into red balls by the following sequence of operations.

  • Convert a green ball and blue ball into red balls \(B\) times.
  • Do the following \((G-B)/3\) times.
    • Convert a red ball and green ball into blue balls.
    • Convert a green ball and blue ball into red balls.
    • Convert a green ball and blue ball into red balls.

Here, there are \(G\) operations in total. We can easily see that this is the minimum number needed.

We have found the number of operations needed to end up with only red balls, so let us do the same for blue and green balls and print the minimum of the numbers found. The time complexity is \(O(1)\) per case.

posted:
last update: