Overview

Given the quantities \(A_i\) of \(N\) types of sweets, this problem asks you to find, for each type, the quotient (number per person) and remainder (number of leftover sweets that cannot be evenly distributed) when dividing by the number of people \(M\).

Analysis

The condition stated in the problem, “\(A_i = M \times Q_i + R_i\) and \(0 \le R_i < M\)”, is exactly the definition of the “quotient” and “remainder” in integer division. Therefore, the answer can be obtained simply by dividing each \(A_i\) by \(M\).

For example, if \(A_i = 10\) sweets are distributed among \(M = 3\) people, then \(10 \div 3 = 3\) remainder \(1\), so the quotient is \(Q_i = 3\) and the remainder is \(R_i = 1\). This can be easily computed using the division operator and the modulo operator (remainder operator) that are standard in programming languages.

However, in this problem, the number of sweet types \(N\) can be as large as \(2 \times 10^5\). Therefore, if you naively read input line by line with input() and call print() \(N\) times, the I/O processing may take too long and result in a Time Limit Exceeded (TLE) verdict. To prevent this, optimizations for performing I/O in bulk are necessary.

Algorithm

1. Read the entire input at once and split it by whitespace and newlines, storing the results in an array (list).
2. Obtain \(N\) and \(M\) from the first two elements.
3. For each of the subsequent \(N\) elements (each \(A_i\)), perform the following operations in order:
   • Calculate the quotient \(Q_i\) and remainder \(R_i\) of dividing \(A_i\) by \(M\).
   • Format the result as a string "Q_i R_i" and append it to an output array.
4. After all calculations are complete, join the output array with newline characters and print it all at once.

Complexity

• Time complexity: \(O(N)\) For each \(A_i\), we only perform one division and one remainder calculation, each of which completes in constant time \(O(1)\). Since this is repeated \(N\) times, the overall execution time is \(O(N)\).
• Space complexity: \(O(N)\) We use an array to hold all the input data at once and another array to hold the output results, requiring \(O(N)\) memory.

Implementation Notes

• Using the divmod function: Python has a convenient built-in function divmod(a, b) that computes and returns both the quotient and remainder simultaneously. Using this, you can write it concisely in one line as q, r = divmod(A_i, M).

• Fast I/O: By using sys.stdin.read().split(), the entire input can be read very quickly. Additionally, instead of calling print multiple times, we accumulate results in a list out and output everything at once using '\n'.join(out) with a single print call, achieving a significant speedup. This is a standard technique for handling large amounts of I/O in competitive programming.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    out = []
    for i in range(2, 2 + N):
        A_i = int(input_data[i])
        q, r = divmod(A_i, M)
        out.append(f"{q} {r}")
        
    print('\n'.join(out))

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.