#C8883. Minimize Absolute Differences
Minimize Absolute Differences
Minimize Absolute Differences
You are given two integers \(n\) and \(S\). Your task is to construct a list of \(n\) integers that sum up to \(S\) and minimizes the sum of the absolute differences among its elements. In other words, you should produce a list \(A = [a_1, a_2, \dots, a_n]\) such that:
[ a_1 + a_2 + \cdots + a_n = S ]
and the list is as balanced as possible (i.e. the elements are nearly equal), which minimizes the quantity:
[ \sum_{i < j} |a_i - a_j| ]
The optimal solution is to distribute \(S\) as evenly as possible among the \(n\) numbers. Let \(\text{base} = \lfloor S/n \rfloor\) and \(\text{remainder} = S \bmod n\). Then, you can form the answer as:
[ [\underbrace{\text{base}+1, \dots, \text{base}+1}{\text{remainder times}}, \underbrace{\text{base}, \dots, \text{base}}{n - \text{remainder} \text{ times}}] ]
It does not matter in what order you print these numbers.
inputFormat
Input is given from stdin as a single line containing two space-separated integers \(n\) and \(S\), where \(n\) is the number of integers to construct and \(S\) is their required sum.
outputFormat
Print a sequence of \(n\) integers separated by a space in a single line. The integers must sum to \(S\) and be as nearly equal as possible so that the sum of absolute differences is minimized.
## sample2 4
2 2