No.120 Trends and Countermeasures: Kadomatsu Sequences (Part 1)
タグ : / 解いたユーザー数 231
作問者 :
LayCurse
Problem Statement
Problems about kadomatsu sequences have been appearing frequently over the past few days.
Here, let us deepen our understanding of kadomatsu sequences through practice, so that we can solve them when such problems are set.
As all of you taking this kadomatsu sequence preparation course may already know, a kadomatsu sequence is a sequence of $3$ elements $a,b,c$ that satisfies the following $2$ conditions.
・$a,b,c$ are all distinct
・Among the $3$ elements, $b$ is the largest, or $b$ is the smallest
Now, Yuki has $N$ bamboo stalks, and the length of the $k$-th stalk is $L_k$.
Using these stalks, Yuki wants to make as many kadomatsu as possible.
Of course, $1$ kadomatsu uses $3$ stalks, and the lengths of those stalks must form a kadomatsu sequence.
The $3$ stalks to use may be chosen freely, and they may be freely rearranged to form a kadomatsu sequence.
Write a program that finds the maximum number of kadomatsu Yuki can make.
Although bamboo is said to grow quickly, it is a treasure of nature, so Yuki does not cut or join the stalks and uses them as they are.
Input
The $1$st line of the input contains the number of test cases $T$.
It is followed by $T$ test cases, given in the following format.
$N$ $L_1$ $L_2$ $\cdots$ $L_N$
$1 \leq T \leq 1000$
$1 \leq N \leq 100$
$1 \leq L_k \leq 1000000000 = 10^9$
Output
For each test case, output the maximum number of kadomatsu that can be made on $1$ line.
Sample
Sample 1
Input
1 3 1 2 3
Output
1
A kadomatsu sequence can be made using all $3$ stalks.
For example, $1,3,2$ or $2,1,3$ can be made.
Sample 2
Input
1 7 7 3 4 7 1 3 9
Output
2
$2$ kadomatsu sequences can be made; for example, using the first $3$ stalks and the next $3$ stalks in their given order gives the kadomatsu sequences $7,3,4$ and $7,1,3$.
Sample 3
Input
3 2 1 1 1 3 2 10 20
Output
0 0 0
A kadomatsu cannot be made without at least $3$ stalks.
Sample 4
Input
4 8 2 2 5 8 7 3 8 8 3 1 1 1 6 1 1 2 2 2 3 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Output
2 0 1 5
Happy New Year.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。