Editorial

Summary

We are given an \(H \times W\) grid where each cell is T (a treasure) or . (nothing). For each row, we output o if the row contains at least one T, and x otherwise, producing a single string of length \(H\) built from the top row down.

Algorithm

Read each row \(S_i\) one by one and check whether it contains the character T.

• If it does, append o to the answer string.
• If it does not, append x.

After processing all rows, print the resulting string of length \(H\).

In C++, the check is S.find('T') != string::npos; in Python it is 'T' in S.

Proof of Correctness

Claim: The \(i\)-th character of the output string is o if and only if \(S_i\) contains at least one T.

Proof: The algorithm processes each row \(i\) independently. In the \(i\)-th iteration it examines only \(S_i\) and appends o if a T is found, x otherwise. Scanning the string inspects every character of \(S_i\), so a T is detected whenever one exists and is never detected when none exists. Hence the \(i\)-th output character matches the specification exactly. Characters are appended in top-to-bottom row order, so the output has the required order and length \(H\). ■

Complexity

• Time: \(O(HW)\), including reading the input.
• Space: \(O(H + W)\) for C++ and \(O(HW)\) for Python, including stored input and output arrays or strings.