G. Мерлин

Имя входного файла:	merlin.in
Имя выходного файла:	merlin.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на все его сосуды с эликсиром мудрости.

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

Чтобы добиться этого, Мерлин решил действовать следующим образом. Он выбирает несколько сосудов и переливает весь эликсир из выбранных сосудов в оставшиеся. Он может распределить переливаемый эликсир между оставшимися сосудами произвольным образом. После того, как весь эликсир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся сосудам.

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

Формат входного файла

В первой строке входного файла находится число n (2 ≤ n ≤ 10⁵) – количество сосудов. Во второй строке содержатся n чисел a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁹) – количество литров эликсира мудрости в каждом сосуде.

Формат выходного файла

Выведите в выходной файл минимальное количество сосудов, которые Мерлину придется разбить.

Пример:

merlin.in	merlin.out
3 2 3 2	1
4 4 4 4 4	0
5 1 2 3 4 5	2

В первом примере можно, например, перелить 0.5 литра эликсира из первого сосуда во второй и 1.5 литра в третий, после чего разбить первый сосуд.

Во втором сосуды исходно содержат равное количество эликсира, можно ничего не переливать.

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

Источник: Командное школьное первенство Республики Карелия. Ноябрь 2014.

Обсудить       Отправить решение