Преобразование массивов
У нас есть массив положительных чисел. Мы должны преобразовать этот массив повторяя одну и ту же операцию, пока не останется менее двух элементов в массиве:
выбрать два элемента, которые имеют минимальную абсолютную разницу. Если таких пар несколько, то выбрать пару, чья сумма элементов минимальна. Если все равно осталось несколько пар, то выбрать любую.
уменьшить значение элементов выбранной пары на 1.
удалить нулевые элементы массива.
Легко заметить, что процесс конечен за фиксированное количество шагов.
Например, имеем массив из 4 элементов {3, 2, 3, 2}. Процесс преобразования будет происходить следующим образом:
Шаг 1: {3, 2, 3, 2} => {3, 1, 3, 1} (уменьшаем элементы 2 и 2)
Шаг 2: {3, 1, 3, 1} => {3, 3} (очередное уменьшение значений элементов делает их равными 0 и 0, удаляем их)
Шаг 3: {3, 3} => {2, 2}
Шаг 4: {2, 2} => {1, 1}
Шаг 5: {1, 1} => { }
Получили пустой массив. Необходимо узнать количество шагов преобразования.
Входные данные
В одной строке записана последовательность чисел разделенных между собой запятой и пробелом. После последнего числа стоит точка. Размер массива от 1 до 50, каждый элемент может принимать значения от 1 до 1000.
Выходные данные
Количество шагов преобразования данного массива.