e-olymp 145. Квадраты

Задача взята с сайта e-olymp

Задача

Заданы длины $n$ отрезков. Какое наибольшее количество квадратов можно из них составить? Сторона каждого квадрата должна состоять только из одного отрезка.

Входные данные

В первой строке находится количество отрезков $n \left(1 \leqslant n\leqslant 10^6\right)$. Во второй строке заданы $n$ натуральных чисел — длины отрезков, числовые значения которых не превышают $100$.

Выходные данные

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 9
2 2 4 2 3 2 1 2 4
1
2 11
2 2 4 2 2 4 2 2 1 2 2
2
3 5
8 9 8 9 11
0

Код программы

Решение

Пусть имеется $k$ отрезков одинаковой длины. Тогда из них можно составить $\frac{k}{4}$ квадрата. Длины отрезков изменяются от $1$  до $100$. Подсчитываем количество отрезков длины $i\left(1\leqslant i\leqslant 100\right)$ в массив $a\left[i\right]$. Тогда максимально возможное количество квадратов, которое можно составить из данных отрезков, равно $$\frac{a\left[1\right]+a\left[2\right]+\dots +a\left[100\right]}{4}.$$
Для этого совершим сортировку подсчетом. В ячейке a[i] подсчитываем количество отрезков длины i . В переменную res  подсчитываем количество квадратов, которое можно построить.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

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