Problem Summary

Takahashi and Aoki sing \(N\) songs. The \(i\)-th song has \(A_i\) lines of lyrics. Takahashi sings the odd-numbered lines and Aoki sings the even-numbered lines. Find the number of songs whose last line (line \(A_i\)) is sung by Takahashi.

Solution

Since Takahashi sings line 1 and they alternate one line at a time, line number \(k\) is sung by Takahashi if \(k\) is odd and by Aoki if \(k\) is even. Therefore, the last line (line \(A_i\)) is sung by Takahashi if and only if \(A_i\) is odd.

So we simply count the indices \(i\) for which \(A_i\) is odd.

Proof of Correctness

Lemma: Line number \(k\) (\(1 \leq k \leq A_i\)) is sung by Takahashi when \(k\) is odd and by Aoki when \(k\) is even.

Proof: By induction on \(k\). For \(k = 1\), Takahashi sings it (by the problem statement). For \(k \geq 2\), the singer alternates from the singer of line \(k - 1\): if \(k - 1\) is odd (Takahashi), then \(k\) is even and sung by Aoki; if \(k - 1\) is even (Aoki), then \(k\) is odd and sung by Takahashi. Both cases match the lemma’s claim.

Theorem: The algorithm outputs exactly the number of songs whose last line is sung by Takahashi.

Proof: By the lemma, the last line of song \(i\) (line \(A_i\)) is sung by Takahashi if and only if \(A_i\) is odd. The algorithm counts precisely the indices \(i\) with odd \(A_i\), which equals the required answer.

Complexity

• Time: \(O(N)\), since each \(A_i\) is examined once.
• Space: The Python implementation reads the whole input at once and uses \(O(N)\) space; the C++ implementation reads each \(A_i\) one at a time and checks it immediately, using only \(O(1)\) auxiliary space (a counter).

Implementation Notes

• There is no tie-breaking; we only count.
• Since \(A_i \geq 1\), edge cases such as “songs with zero lines” cannot occur.