7012번 - Building Snowmen 다국어

You are trying to build an army of snowmen. To do so, you have gathered a bunch of snowballs of varying sizes. You want to build each snowman by stacking three snowballs on top of each other. You will do this by choosing a snowball to be the base. Then you will choose a smaller snowball to be the middle. Then an even smaller snowball will be the top. Each snowball has a diameter d. When evaluating a snowman, suppose the diameter of the bottom snowball is d_b, the diameter of the middle snowball is d_m, and of the top snowball d_t. Then you want the following inequalities to hold:

• 2d_b ≥ 3d_m
• 2d_m ≥ 3d_t

Calculate the maximum number of snowmen that can be built from the available snowballs and according to the criteria.

The first line is the number K of input data sets, followed by the K data sets, each of the following form:

The first line of each data set contains the number of snowballs N, where 3 ≤ N ≤ 1000. This followed by a line containing N integers each at least 1 and at most 1000. The ith integer is the diameter of the ith snowball.

For each data set, output “Data Set x:” on a line by itself, where x is its number. On the next line, output the maximum number of proper snowmen that can be completed. Each data set should be followed by a blank line.