Overview

When distributing \(N\) types of sweets equally among \(M\) people, we need to find the quotient (number per person) and remainder for each type. This can be solved by performing basic division (integer division and modulo).

Analysis

Reading the problem statement carefully, we can see that for each type of sweet with count \(A_i\), we need to find the quotient \(Q_i\) and remainder \(R_i\) when dividing by the number of friends \(M\).

• Quotient \(Q_i = \lfloor A_i / M \rfloor\): the number of sweets each person receives
• Remainder \(R_i = A_i \mod M\): the number of sweets left over after distribution

For example, consider the case where \(A_i = 10\) and \(M = 3\). When distributing 10 sweets among 3 people, each person receives \(\lfloor 10 / 3 \rfloor = 3\) sweets, and \(10 \mod 3 = 1\) sweet remains. Indeed, \(10 = 3 \times 3 + 1\) holds.

No special algorithm is needed for this problem — simply performing division for each \(A_i\) is sufficient. Although \(N\) can be up to \(2 \times 10^5\), we only perform \(O(1)\) operations per element, so there are no time concerns.

Algorithm

1. Read \(N\) and \(M\).
2. Read the array \(A\).
3. For each \(A_i\), compute \(Q_i = A_i \div M\) (integer division) and \(R_i = A_i \mod M\) (modulo).
4. For each \(i\), output \(Q_i\) and \(R_i\) on one line.

Complexity

• Time complexity: \(O(N)\) — We only compute one division and one modulo operation for each type of sweet.
• Space complexity: \(O(N)\) — We store the input array and a list of output strings.

Implementation Notes

• Output optimization: In Python, calling print \(N\) times can be slow. Instead, we accumulate the output in a list and print it all at once using '\n'.join(out) at the end. Since \(N\) can be up to \(2 \times 10^5\), this optimization is effective in reducing execution time.

• Input optimization: Using sys.stdin.readline allows faster input reading compared to the standard input().

• In Python, the // operator performs floor (integer) division and the % operator returns the remainder. Since \(A_i \geq 0\) and \(M \geq 1\), we don’t need to worry about division behavior with negative numbers.

  Source Code

import sys
input = sys.stdin.readline

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

out = []
for a in A:
    out.append(f"{a // M} {a % M}")
print('\n'.join(out))

This editorial was generated by claude4.6opus-thinking.