7809. Morning exercises

 

In the morning, many students do their exercises. According to established tradition, the students dance in the branded T-shirts. During the first three days of the camp, schoolchildren and teachers noticed that a couple who dances in identical T-shirts looks more aesthetically better. Therefore, before the exercises, they decided first to put pairs of children in identical T-shirts, and then the remaining ones. The excellent student Seryozha wanted to know what the largest number of aesthetic pairs can be formed from everyone who came to morning exercises.

 

Input. Sequence of n (n ≤ 106) positive integers, giving the color of a T-shirt (the color is a number from 0 to 9).

 

Output. Print the number of aesthetic pairs that can be made up.

 

Sample input

Sample output

0 3 6 3 0 0 1

2

 

 

SOLUTION

counting sort

 

Algorithm analysis

T-shirt color is a number from 0 to 9. Let’s count the number of T-shirts of color i in m[i]. Then, out of schoolchildren wearing a T-shirt of color i, one can make m[i] / 2 aesthetic pairs. Then the total number of aesthetic pairs is

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

 

Algorithm realization

Declare the array for counting.

 

int m[10];

 

Read the input data. Perform the counting sort. In cell m[i] count the number of T-shirts of color i.

 

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

  m[x]++;

 

In the variable res count the number of aesthetic pairs.

 

res = 0;

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

  res += m[i] / 2;

 

Print the answer – the required number of aesthetic pairs.

 

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