7809. Утренняя зарядка

Утром многие школьники делают танцевальную зарядку. По сложившейся традиции, ученики танцуют в фирменных футболках. За первые три дня смены школьниками и преподавателями было замечено, что пара, которая танцует в одинаковых футболках, выглядит эстетичнее. Поэтому перед началом зарядки решили сначала поставить пары из детей в одинаковых футболках, а затем оставшихся. Отличнику Сереже захотелось узнать, какое наибольшее количество эстетических пар можно образовать из всех, кто пришел на зарядку.

Вход. Последовательность из n (n ≤ 10⁶) натуральных чисел, обозначающих цвет футболки (цвет является числом от 0 до 9).

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

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

РЕШЕНИЕ

сортировка подсчетом

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

Цвет футболки – число от 0 до 9. Подсчитаем количество футболок цвета i в ячейке m[i]. Тогда из школьников, одетых в футболку цвета i, можно составить m[i] / 2 эстетических пар. Тогда общее количество эстетических пар равно

m[0] / 2 + m[1] / 2 + … + m[9] / 2

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

Объявим массив для подсчета.

int m[10];

Читаем входные данные. Совершаем сортировку подсчетом. В ячейке m[i] подсчитываем количество футболок цвета i.

while (scanf("%d", &x) == 1)

m[x]++;

В переменной res подсчитываем количество эстетических пар.

res = 0;

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

res += m[i] / 2;

Выводим ответ – искомое количество эстетических пар.

printf("%lld\n", res);