Initially you are given $3$ numbers $(a,b,c)$. Find two numbers with the smallest difference, and add the difference to the multiset. Keep repeating this operation until difference is zero. Numbers can be up to $10^{18}$. Program needs to output how many iteration is needed for algorithm to finish.
Example: If initial numbers is (234, 532, 245)
First move: Add (245-234) -> (234, 532, 245, 11)
Second move: Same -> (234, 532, 245, 11, 11)
Third move: Add zero. Finished.
At first I thought this will require some clever algorithm because it needs to give answer within 0.5s. But it turns out that for most random test case with numbers up to $10^{18}$, it just needs around $3$-$5$ moves, so pure simulation works just fine.
My question: Is there a closed form formula for this, or maybe a way to prove upper bound on number of moves needed given some initial configuration (like the worst possible case that results in most number of iterations) Thanks.
Original source: http://acm.timus.ru/problem.aspx?space=1&num=1777. No need to read problem description, just skip to input and output sample.
Ok so this is a "while" kind of algorithm (sorry for the lack of a better term).
The exit condition is that the difference between two numbers is $0$.
The initial set is $(a,b,c)$
Then, while the exit condition is not met, we keep adding the lowest difference amongst elements of the set.
Let's assume we work with relative integers, I think you can see that for any number $n$ we add to the set, $$|n| \le min\{ |a-b|,|a-c|,|b-c| \} = N$$
That is $n \in A, A =\{k\in \mathbb{Z}, -N\le k\le N\} $
And $A$ is a finite set (I'm not sure of the english term, I mean there is a finite number of elements)
So we can deduce that there is a maximum number of steps ($2N$ for relative integers, $N$ for integers) we can do before we introduce the same number twice and that would mean that we meet the exit condition.