Overview

This is a problem where you need to find visitors whose registration numbers are multiples of \(K\) in order, and output their lottery ticket numbers.

Analysis

The key points in this problem are as follows:

1. Relationship between registration numbers and array indices: The registration number of the visitor who drew the lottery \(i\)-th is \(i\). Since array \(A\) is 0-indexed, the lottery ticket number of the visitor with registration number \(i\) is stored in \(A[i-1]\).

2. Condition for receiving a prize: Visitors whose registration numbers are multiples of \(K\), namely those who drew the lottery \(K\)-th, \(2K\)-th, \(3K\)-th, \(\ldots\), receive prizes.

3. Order of output: You need to output in the order prizes are given, that is, in ascending order of registration numbers (\(K, 2K, 3K, \ldots\)).

Let’s verify with a concrete example: - For \(N = 5, K = 2\) and \(A = [10, 20, 30, 40, 50]\) - Registration number 1 → lottery ticket number 10 - Registration number 2 → lottery ticket number 20 ← multiple of \(K\), so receives a prize - Registration number 3 → lottery ticket number 30 - Registration number 4 → lottery ticket number 40 ← multiple of \(K\), so receives a prize - Registration number 5 → lottery ticket number 50 - Output: 20 40

Since this problem simply requires processing registration numbers that are multiples of \(K\) in order, a straightforward approach is sufficiently fast.

Algorithm

1. Look at registration numbers \(i\) from \(1\) to \(N\) in order
2. Determine whether \(i\) is a multiple of \(K\) (whether \(i \mod K = 0\))
3. If it is a multiple of \(K\), add the corresponding lottery ticket number \(A[i-1]\) to the result list
4. Finally, output the result list separated by spaces (output nothing if empty)

Alternative solution: There is also a method to directly enumerate multiples of \(K\).

for i in range(K, N + 1, K):
    result.append(A[i - 1])

This method loops while incrementing by \(K\) as \(K, 2K, 3K, \ldots\), so no condition check is needed.

Complexity

• Time complexity: \(O(N)\)
  • Because we loop from \(1\) to \(N\) to check each registration number
  • For the alternative solution, it becomes \(O(N/K)\), but in the worst case (\(K=1\)), it is \(O(N)\)
• Space complexity: \(O(N/K)\)
  • The size of the list storing results (at most \(\lfloor N/K \rfloor\) elements)

Implementation Notes

• Be careful about index offset: Registration numbers start from \(1\), but Python arrays start from \(0\), so the lottery ticket number corresponding to registration number \(i\) is A[i-1].

• Output when empty: According to the problem statement, “if there are no visitors to give prizes to, output nothing,” so we confirm the list is not empty with if result: before outputting.

• print(*result): This is a convenient way to output list elements separated by spaces.

  Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))

result = []
for i in range(1, N + 1):
    if i % K == 0:
        result.append(A[i - 1])

if result:
    print(*result)

This editorial was generated by claude4.5opus.