CF1889D Game of Stacks

You have $ n $ stacks $ r_1,r_2,\ldots,r_n $ . Each stack contains some positive integers ranging from $ 1 $ to $ n $ . Define the following functions: ``` function init(pos): stacks := an array that contains n stacks r[1], r[2], ..., r[n] return get(stacks, pos) function get(stacks, pos): if stacks[pos] is empty: return pos else: new_pos := the top element of stacks[pos] pop the top element of stacks[pos] return get(stacks, new_pos) ``` You want to know the values returned by $ \texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)} $ . Note that, during these calls, the stacks $ r_1,r_2,\ldots,r_n $ don't change, so the calls $ \texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)} $ are independent.

N/A

N/A

In the first example: - When you call $ \texttt{init(1)} $ , set $ \texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]} $ , and then call $ \texttt{get(stacks, 1)} $ . - $ \texttt{stacks[1]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[1]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[3,1,2],[1,2,1]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[3,1],[1,2,1]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 1} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[3],[1,2,1]] $ , and then call $ \texttt{get(stacks, 1)} $ . - $ \texttt{stacks[1]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[1]} $ , which makes $ \texttt{stacks} $ become $ [[1],[3],[1,2,1]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 3} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1],[],[1,2,1]] $ , and then call $ \texttt{get(stacks, 3)} $ . - $ \texttt{stacks[3]} $ is not empty, set $ \texttt{new_pos := 1} $ , and pop the top element of $ \texttt{stacks[3]} $ , which makes $ \texttt{stacks} $ become $ [[1],[],[1,2]] $ , and then call $ \texttt{get(stacks, 1)} $ . - $ \texttt{stacks[1]} $ is not empty, set $ \texttt{new_pos := 1} $ , and pop the top element of $ \texttt{stacks[1]} $ , which makes $ \texttt{stacks} $ become $ [[],[],[1,2]] $ , and then call $ \texttt{get(stacks, 1)} $ . - $ \texttt{stacks[1]} $ is empty, return $ 1 $ . - When you call $ \texttt{init(2)} $ , set $ \texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]} $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1,2,2],[3,1],[1,2,1]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 1} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1,2,2],[3],[1,2,1]] $ , and then call $ \texttt{get(stacks, 1)} $ . - $ \texttt{stacks[1]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[1]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[3],[1,2,1]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 3} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[],[1,2,1]] $ , and then call $ \texttt{get(stacks, 3)} $ . - $ \texttt{stacks[3]} $ is not empty, set $ \texttt{new_pos := 1} $ , and pop the top element of $ \texttt{stacks[3]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[],[1,2]] $ , and then call $ \texttt{get(stacks, 1)} $ . - $ \texttt{stacks[1]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[1]} $ , which makes $ \texttt{stacks} $ become $ [[1],[],[1,2]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is empty, return $ 2 $ . - When you call $ \texttt{init(3)} $ , set $ \texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]} $ , and then call $ \texttt{get(stacks, 3)} $ . - $ \texttt{stacks[3]} $ is not empty, set $ \texttt{new_pos := 1} $ , and pop the top element of $ \texttt{stacks[3]} $ , which makes $ \texttt{stacks} $ become $ [[1,2,2],[3,1,2],[1,2]] $ , and then call $ \texttt{get(stacks, 1)} $ . - $ \texttt{stacks[1]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[1]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[3,1,2],[1,2]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[3,1],[1,2]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 1} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1,2],[3],[1,2]] $ , and then call $ \texttt{get(stacks, 1)} $ . - $ \texttt{stacks[1]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[1]} $ , which makes $ \texttt{stacks} $ become $ [[1],[3],[1,2]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is not empty, set $ \texttt{new_pos := 3} $ , and pop the top element of $ \texttt{stacks[2]} $ , which makes $ \texttt{stacks} $ become $ [[1],[],[1,2]] $ , and then call $ \texttt{get(stacks, 3)} $ . - $ \texttt{stacks[3]} $ is not empty, set $ \texttt{new_pos := 2} $ , and pop the top element of $ \texttt{stacks[3]} $ , which makes $ \texttt{stacks} $ become $ [[1],[],[1]] $ , and then call $ \texttt{get(stacks, 2)} $ . - $ \texttt{stacks[2]} $ is empty, return $ 2 $ .