No.1823 Tricolor Dango
タグ : / 解いたユーザー数 184
作問者 :
Problem Statement
You have made a lot of dango. Each dango has exactly $1$ kind of color among color $1$, color $2$, $\dots$, color $N$, and $A_i$ dango of color $i$ $( 1 \leq i \leq N)$ were made.
Since you have a lot of dango skewers, you plan to use the dango you made to create $3$-color dango on skewers.
Each $1$ skewer of $3$-color dango is made as follows.
- Choose $3$ dango of different colors. Put the chosen $3$ dango on $1$ skewer.
The colors of the $3$ dango must all be different. Also, the same dango cannot be used to make multiple $3$-color dango.
Your goal is to make $3$-color dango without leaving even $1$ dango over.
You are given $T$ test cases. For each of them, determine whether the goal can be achieved.
Constraints
- All input values are integers.
- $1 \leq T \leq 10^4$
- $3 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- In $1$ input file, the sum of $N$ is at most $2 \times 10^5$.
Input
The input is given from standard input. Line $1$ is given in the following format.
$T$
Then, $T$ test cases follow, each given in the following format.
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print over $T$ lines. On line $i$ $(1 \leq i \leq T)$, for the $i$-th test case, print Yes if $3$-color dango can be made without leaving any dango over, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
5 5 2 2 2 3 3 3 3 3 3 9 3 1 4 1 5 9 2 6 5 6 1 1 1 1 1 2 4 2 7 1 8
Output
Yes Yes Yes No No
$5$ test cases are given.
In test case $1$, for example, with the color combinations $(1, 2, 3)$, $(1, 4, 5)$, $(2, 4, 5)$, $(3, 4, 5)$, you can make $4$ skewers of $3$-color dango without leaving any dango over.
In test case $2$, you can make $3$ skewers of $3$-color dango of $(1, 2, 3)$.
In test cases $4$ and $5$, no matter how you combine them, you cannot make $3$-color dango without leaving any dango over. Putting dango of the same color on the same skewer is not allowed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。