Overview

Check whether the number of lyric lines 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 line by line, so the singer of each line is as follows:

• Odd-numbered lines: Takahashi
• Even-numbered lines: Aoki

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

For example, if \(A_i = 3\), the order is “Takahashi → Aoki → Takahashi”, so Takahashi sings the last line. On the other hand, if \(A_i = 4\), Aoki sings the last line.

Simulating line by line will comfortably pass within the time limit under these constraints. However, since the singer of the last line is determined solely by the parity of the number of lines, it is not necessary to check every line.

Also, note that Takahashi starts singing first for each song. Carrying over the alternating order from the previous song may lead to an incorrect answer.

Algorithm

1. Read the number of songs \(N\) and the number of lyric lines for each song, \(A_1, A_2, \ldots, A_N\).
2. For each \(A_i\), check whether the remainder when divided by \(2\) is \(1\).
3. Count the number of songs where the remainder is \(1\), and print the result.

For example, if the line counts are \([3, 4, 1, 6, 5]\), the odd numbers are \(3, 1, 5\) (a total of \(3\)), so the answer is \(3\).

Complexity

• Time complexity: \(O(N)\)
  We inspect the line count of each song once.
• Space complexity: \(O(N)\)
  In the provided code, the read input is stored in data. The additional space required for the tallying itself is \(O(1)\).

Implementation Notes

• int(data[i]) % 2 == 1 checks whether the number of lines is odd. % is the modulo operator, which calculates the remainder of division.

• Since data[0] is the number of songs \(N\), we iterate from data[1] to data[n], where the line counts are stored. Because Python’s range is exclusive of the upper bound, we write range(1, n + 1).

• sum(1 for ... if ...) counts the number of matching songs by adding \(1\) each time the condition is satisfied.

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    count = sum(1 for i in range(1, n + 1) if int(data[i]) % 2 == 1)
    print(count)

main()

---

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