CF1179E Alesya and Discrete Math

We call a function good if its domain of definition is some set of integers and if in case it's defined in $ x $ and $ x-1 $ , $ f(x) = f(x-1) + 1 $ or $ f(x) = f(x-1) $ . Tanya has found $ n $ good functions $ f_{1}, \ldots, f_{n} $ , which are defined on all integers from $ 0 $ to $ 10^{18} $ and $ f_i(0) = 0 $ and $ f_i(10^{18}) = L $ for all $ i $ from $ 1 $ to $ n $ . It's an notorious coincidence that $ n $ is a divisor of $ L $ . She suggests Alesya a game. Using one question Alesya can ask Tanya a value of any single function in any single point. To win Alesya must choose integers $ l_{i} $ and $ r_{i} $ ( $ 0 \leq l_{i} \leq r_{i} \leq 10^{18} $ ), such that $ f_{i}(r_{i}) - f_{i}(l_{i}) \geq \frac{L}{n} $ (here $ f_i(x) $ means the value of $ i $ -th function at point $ x $ ) for all $ i $ such that $ 1 \leq i \leq n $ so that for any pair of two functions their segments $ [l_i, r_i] $ don't intersect (but may have one common point). Unfortunately, Tanya doesn't allow to make more than $ 2 \cdot 10^{5} $ questions. Help Alesya to win! It can be proved that it's always possible to choose $ [l_i, r_i] $ which satisfy the conditions described above. It's guaranteed, that Tanya doesn't change functions during the game, i.e. interactor is not adaptive

N/A

N/A

In the example Tanya has $ 5 $ same functions where $ f(0) = 0 $ , $ f(1) = 1 $ , $ f(2) = 2 $ , $ f(3) = 3 $ , $ f(4) = 4 $ and all remaining points have value $ 5 $ . Alesya must choose two integers for all functions so that difference of values of a function in its points is not less than $ \frac{L}{n} $ (what is $ 1 $ here) and length of intersection of segments is zero. One possible way is to choose pairs $ [0 $ , $ 1] $ , $ [1 $ , $ 2] $ , $ [2 $ , $ 3] $ , $ [3 $ , $ 4] $ and $ [4 $ , $ 5] $ for functions $ 1 $ , $ 2 $ , $ 3 $ , $ 4 $ and $ 5 $ respectively.