CF995C Leaving the Bar

For a vector $ \vec{v} = (x, y) $ , define $ |v| = \sqrt{x^2 + y^2} $ . Allen had a bit too much to drink at the bar, which is at the origin. There are $ n $ vectors $ \vec{v_1}, \vec{v_2}, \cdots, \vec{v_n} $ . Allen will make $ n $ moves. As Allen's sense of direction is impaired, during the $ i $ -th move he will either move in the direction $ \vec{v_i} $ or $ -\vec{v_i} $ . In other words, if his position is currently $ p = (x, y) $ , he will either move to $ p + \vec{v_i} $ or $ p - \vec{v_i} $ . Allen doesn't want to wander too far from home (which happens to also be the bar). You need to help him figure out a sequence of moves (a sequence of signs for the vectors) such that his final position $ p $ satisfies $ |p| \le 1.5 \cdot 10^6 $ so that he can stay safe.

N/A

N/A