Overview

We check whether the number of lines of lyrics \(A_i\) in each song is odd, and count the number of songs with an odd number of lines.

Analysis

For every song, Takahashi starts singing first and they alternate singing \(1\) line at a time, so the lines each person is responsible for are as follows:

• Takahashi: Lines \(1, 3, 5, \ldots\) (odd-numbered lines)
• Aoki: Lines \(2, 4, 6, \ldots\) (even-numbered lines)

Therefore, the condition for Takahashi to sing the last line (the \(A_i\)-th line) is that \(A_i\) is odd.

For example, if the numbers of lines of lyrics are \(3, 4, 7\), Takahashi sings the last line in the songs with \(3\) and \(7\) lines, and Aoki sings the last line in the song with \(4\) lines. Thus, the answer is \(2\).

Naively, this problem can also be solved by simulating the alternating singers line by line for each song. While this would easily run within the time limit under these constraints, a simulation is unnecessary if we simply check the parity of the number of lines.

Note that Takahashi always starts singing first whenever a new song begins. If you continue the alternation across songs as a single sequence, you may get an incorrect answer.

Algorithm

1. Read the number of songs \(N\) and the array \(A\) storing the number of lines for each song.
2. For each line count \(A_i\), check whether the remainder when divided by \(2\) is \(1\).
3. Count the number of songs where the remainder is \(1\), and output the result.

Since this check is equivalent to the condition that “Takahashi sings the last line,” the counted value is the required answer.

Complexity

• Time complexity: \(O(N)\) — We check the number of lines for each song once.
• Space complexity: \(O(N)\) — We store the input line counts in a list. The additional space used for counting is \(O(1)\).

Implementation Notes

• In Python, you can check whether x is odd using x % 2 == 1.

• sum(1 for x in a if x % 2 == 1) counts the number of odd elements by adding \(1\) for each odd element.

• Even if no songs satisfy the condition, sum correctly returns \(0\).

  Source Code

# 問題文から独立に実装: 行数が奇数なら最後の行は高橋君
n = int(input())
a = list(map(int, input().split()))
print(sum(1 for x in a if x % 2 == 1))

This editorial was generated by gpt-6-astra-medium.