Editorial for CIW '26 P3 - Gumball Machine - Olympiads Online Judge

Editorial for CIW '26 P3 - Gumball Machine

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

The key observation is that the total number of gumballs dispensed equals $AB$ ~AB~. Initially, when $A = B = 0$ ~A = B = 0~, 0 gumballs are dispenesed.

When we press the $A$ ~A~ button, the total number of gumballs dispensed becomes $AB + B = (A+1)B$ ~AB + B = (A+1)B~. Similarly, when we press the $B$ ~B~ buttom, the total number of gumballs dispensed becomes $A + AB = A(B+1)$ ~A + AB = A(B+1)~.

Thus we want to find integers $A,B$ ~A,B~ such that $AB = N$ ~AB = N~ and $A + B$ ~A + B~ is minimized. Note that the smaller of $A$ ~A~ and $B$ ~B~ is at most $\sqrt N$ ~\sqrt N~, so by iterating through $1, 2, \ldots, \sqrt N$ ~1, 2, \ldots, \sqrt N~ and checking if they divide $N$ ~N~, we can find the pair $(A,B)$ ~(A,B)~ which minimizes $A + B$ ~A + B~.

Time Complexity: $O(\sqrt N)$ ~O(\sqrt N)~

Comments

There are no comments at the moment.