Solution

Points are awarded only while Takahashi keeps answering correctly starting from the first problem. In other words, once the first \(A_i = 0\) appears, every problem from that point on (including that problem itself) earns no points.

Therefore, if \(k\) is the number of consecutive \(1\)’s at the beginning of the sequence, the answer is the string consisting of \(k\) copies of o followed by \(N - k\) copies of x.

In the implementation we keep a flag ok and scan the problems in order. When an \(A_i = 0\) appears we set ok to false, and it stays false afterwards. For each problem we append o if ok is true, otherwise x.

Proof of correctness

Problem \(i\) earns a point if and only if all of problems \(1\) through \(i\) were answered correctly, i.e. \(A_1 = A_2 = \cdots = A_i = 1\).

• For \(i \le k\): by the definition of \(k\), \(A_1, \ldots, A_k\) are all \(1\), so \(A_1 = \cdots = A_i = 1\) holds and the point is awarded. The flag ok remains true during this range, so the algorithm outputs o.
• For \(i > k\): since \(A_{k+1} = 0\) and \(k+1 \le i\), the condition \(A_1 = \cdots = A_i = 1\) fails and no point is awarded. The algorithm sets ok to false at \(i = k+1\) and never resets it, so it outputs x. Since \(A_{k+1} = 0\) itself is a wrong answer, x is correct there as well.

Hence the correct character is produced for every problem. The output is uniquely determined, so no tie-breaking rule is needed.

Complexity

• Time: \(O(N)\)
• Space: the C++ version reads input as a stream and uses \(O(1)\) extra space besides the output string (\(O(N)\) including it). The Python version reads all input at once, so it uses \(O(N)\) space.