2218. Монеты

На столе лежат n монет. Некоторые из них повернуты решкой вверх, другие –гербом. Определите минимальное количество монет, которые нужно перевернуть, чтобы все монеты оказались повернуты вверх одной и той же стороной.

Вход. В первой строке содержится количество монет n (1 ≤ n ≤ 100). В каждой из следующих n строк содержится одно целое число: 1, если монета лежит решкой вверх, и 0, если гербом.

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

Пример входа	Пример выхода
5 1 0 1 1 0	2

РЕШЕНИЕ

математика

Анализ алгоритма

Найдем сумму n чисел – она равна количеству монет, лежащих решкой вверх. Обозначим эту сумму через s. Чтобы все монеты лежали решкой вверх, необходимо перевернуть оставшиеся n – s монет. Чтобы все монеты лежали вверх гербом, нужно перевернуть s монет, которые лежат вверх решкой. Таким образом, ответ равен min(s, n – s).

Пример

Решкой вверх лежит s = 3 монеты.

Чтобы все монеты оказались решкой вверх, нужно перевернуть n – s = 5 – 3 = 2 монеты. Чтобы все монеты были гербом вверх, необходимо перевернуть s = 3 монеты. Ответом на задачу будет min(s, n – s) = min(3, 2) = 2 монеты.

Реализация алгоритма

Читаем входные данные. Вычисляем сумму n чисел в переменной s.

scanf("%d",&n);

for(i = 0; i < n; i++)

{

scanf("%d",&v);

s += v;

}

Вычисляем и выводим ответ – значение min(s, n – s).

if (s < n - s) printf("%d\n",s);

else printf("%d\n",n - s);