Overview

This problem asks you to select only the visitors whose queue numbers are multiples of \(K\) (\(K, 2K, 3K, \ldots\)) and output their lottery ticket numbers \(A_i\) in order.

Analysis

The key point is that the “recipients of prizes” are determined by their queue number (= the order in which they drew). In other words, the people who satisfy the condition are those where \(i\) is a multiple of \(K\), and the value to output is their ticket number \(A_i\).

For example, when \(N=8, K=3\), the target queue numbers are \(3, 6\), so the output is \(A_3, A_6\).

A straightforward approach of checking every person from \(i=1\) to \(N\) and determining “is \(i\) a multiple of \(K\)?” runs in \(O(N)\) and is fast enough. However, a more direct approach of “enumerating only multiples of \(K\)” avoids unnecessary checks and results in cleaner implementation (advancing through \(K, 2K, 3K, \ldots\)).

Also, since \(N\) can be up to \(2\times 10^5\), reading input all at once with sys.stdin.buffer.read() is faster and safer.

Algorithm

1. Read \(N, K\) and the array \(A\) from input.
2. Scan queue numbers \(i = K, 2K, 3K, \ldots\) up to \(N\).
3. For each \(i\), the corresponding ticket number is \(A_i\), but since Python lists are 0-indexed, retrieve A[i-1].
4. Collect the retrieved values in order and output them separated by spaces.
5. If there are no qualifying people (theoretically there is always at least one since \(K \le N\)), outputting an empty string for an empty array causes no issues.

Complexity

• Time complexity: \(O(\lfloor N/K \rfloor)\) (processing only as many people as there are multiples of \(K\))
• Space complexity: \(O(\lfloor N/K \rfloor)\) (storing results for output; the input array \(A\) separately requires \(O(N)\))

Implementation Notes

• Queue numbers are 1-indexed while arrays are 0-indexed, so be careful to use A[i-1].

• Using range(K, N+1, K) naturally enumerates only multiples of \(K\).

• Using join to output everything at once is faster (more stable than printing one by one with print).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))

    res = [str(A[i-1]) for i in range(K, N + 1, K)]
    sys.stdout.write(" ".join(res))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.