Codeforces Round 490 (Div. 3) |
---|
Закончено |
Задан массив, состоящий из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$, и натуральное число $$$m$$$. Гарантируется, что $$$m$$$ делит $$$n$$$ без остатка.
За один ход можно выбрать произвольный индекс $$$i$$$ от $$$1$$$ до $$$n$$$ и увеличить элемент $$$a_i$$$ на $$$1$$$.
Пусть $$$c_r$$$ ($$$0 \le r \le m-1)$$$ — количество элементов, которые имеют остаток $$$r$$$ при делении на $$$m$$$. Иными словами, подсчитаем количество элементов массива $$$a$$$ для каждого остатка.
Ваша задача — изменить массив так, чтобы $$$c_0 = c_1 = \dots = c_{m-1} = \frac{n}{m}$$$.
Выведите минимальное количество ходов, которое необходимо чтобы удовлетворить требование выше.
В первой строке задано два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le m \le n$$$). Гарантируется, что $$$m$$$ делит $$$n$$$ без остатка.
Во второй строке задано $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива.
В первую строку выведите одно целое число — минимальное количество ходов, необходимое, чтобы для каждого остатка от $$$0$$$ до $$$m - 1$$$ количество элементов с таким остатком было равно $$$\frac{n}{m}$$$.
Во вторую строку выведите любой удовлетворяющий условию массив, получаемый из заданного минимальным количеством ходов. Значения элементов полученного массива не должны превышать $$$10^{18}$$$.
6 3
3 2 0 6 10 12
3
3 2 0 7 10 14
4 2
0 1 2 3
0
0 1 2 3
Название |
---|