C - Yamanote Line Game Editorial by rui_er


There is an \(\mathcal O(N^2)\) solution (which is mentioned in the official editorial) that Takahashi always declares the minimum number Takahashi can. Here is an \(\mathcal O(N)\) one.

We can declare \(N+1\) first, which is the median of \(1\dots 2N+1\). Then Takahashi can perform a mimic go, by declaring \(2N+2-x\) when Aoki declares \(x\). For each \(x\ne N+1\), \(x\ne 2N+2-x\), so we never declare a number twice.

C++ Code

posted:
last update: