Codeforces Round 963 (Div. 2) |
---|
Закончено |
Дан массив $$$a$$$ из $$$n$$$ положительных целых чисел.
За одну операцию вы можете выбрать любую пару индексов $$$(i, j)$$$ такие, что $$$a_i$$$ и $$$a_j$$$ имеют различную четность, а затем заменить меньший из них на их сумму. Более формально:
Найдите минимальное количество операций, необходимых для того, чтобы все элементы массива имели одинаковую четность.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимое для достижения цели.
751 3 5 7 944 4 4 432 3 443 2 2 864 3 6 1 2 163 6 1 2 1 25999999996 999999997 999999998 999999999 1000000000
0 0 2 4 3 3 3
В первом наборе входных данных все числа уже имеют одинаковую четность, поэтому совершать операции не требуется.
В третьем наборе входных данных мы можем выполнить две операции $$$(1, 2)$$$ и $$$(1, 3)$$$. Массив $$$a$$$ преобразуется следующим образом: $$$a = [\color{red}2, \color{red}3, 4] \longrightarrow [\color{red}5, 3, \color{red}4] \longrightarrow [5, 3, 9]$$$.
В четвертом наборе входных данных примером оптимальной последовательности операций является $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$ и $$$(1, 4)$$$. Массив $$$a$$$ преобразуется следующим образом: $$$a = [\color{red}3, \color{red}2, 2, 8] \longrightarrow [\color{red}3, 5, \color{red}2, 8] \longrightarrow [\color{red}3, 5, 5, \color{red}8] \longrightarrow [\color{red}{11}, 5, 5, \color{red}8] \longrightarrow [11, 5, 5, 19]$$$.
Название |
---|