eolymp
bolt
Try our new interface for solving problems
Məsələlər

Преобразование массивов

Преобразование массивов

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

У нас есть массив положительных чисел. Мы должны преобразовать этот массив повторяя одну и ту же операцию, пока не останется менее двух элементов в массиве:

  1. выбрать два элемента, которые имеют минимальную абсолютную разницу. Если таких пар несколько, то выбрать пару, чья сумма элементов минимальна. Если все равно осталось несколько пар, то выбрать любую.

  2. уменьшить значение элементов выбранной пары на 1.

  3. удалить нулевые элементы массива.

Легко заметить, что процесс конечен за фиксированное количество шагов.

Например, имеем массив из 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} => { }

Получили пустой массив. Необходимо узнать количество шагов преобразования.

Giriş verilənləri

В одной строке записана последовательность чисел разделенных между собой запятой и пробелом. После последнего числа стоит точка. Размер массива от 1 до 50, каждый элемент может принимать значения от 1 до 1000.

Çıxış verilənləri

Количество шагов преобразования данного массива.

Nümunə

Giriş verilənləri #1
3, 2, 3, 2.
Çıxış verilənləri #1
5