問題一覧 > 通常問題

No.1823 Tricolor Dango

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 150
作問者 : ShirotsumeShirotsume / テスター : koboshikoboshi
5 ProblemId : 7306 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-02 18:11:29

問題文

あなたは団子をたくさん作りました。団子はそれぞれ色 $1$ 、色 $2$、$\dots$ 、色 $N$ のうちいずれか $1$ 種類の色がついており、色 $i$ $( 1 \leq i \leq N)$ の団子は $A_i$ 個できました。

あなたは団子用の串をたくさん持っているので、できた団子を使って串にささった $3$ 色団子を作ろうと考えています。

$3$ 色団子 $1$ 本は以下のようにして作ります。

  • 異なる色の団子 $3$ 個を選ぶ。選んだ $3$ 個の団子を $1$ 本の串にさす。

$3$ つの団子の色はすべて異なっている必要があります。また、同じ団子を複数の $3$ 色団子を作るために使うことはできません。

あなたの目標は、$1$ つも団子を余らせずに $3$ 色団子を作ることです。

テストケースが $T$ 個与えられるので、それぞれについて目標が達成できるか判定してください。

制約

  • 入力は全て整数
  • $1 \leq T \leq 10^4$
  • $3 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$
  • $1$ つの入力ファイルにおいて、 $N$ の総和は $2 \times 10^5$ 以下である。

入力

入力は標準入力から与えられる。 $1$ 行目は以下の形式で与えられる。

$T$

以下、 $T$ 個のテストケースがそれぞれ以下の形式で与えられる。

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

$T$ 行にわたって出力せよ。$i$ $(1 \leq i \leq T)$ 行目には、 $i$ 番目のテストケースについて、団子を余らせずに $3$ 色団子を作ることができるならYes、できないならNoと出力せよ。

最後に改行すること。

サンプル

サンプル1
入力
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
出力
Yes
Yes
Yes
No
No

$5$ つのテストケースが与えられています。

$1$ つめのテストケースでは、例えば $(1, 2, 3)$、$(1, 4, 5)$、$(2, 4, 5)$、$(3, 4, 5)$ という色の組み合わせで、団子を余らせずに$4$ 本の $3$ 色団子が作れます。

$2$ つめのテストケースでは、$(1, 2, 3)$ の $3$ 色団子を $3$ 本作ることができます。

$4$ つめと $5$ つめのテストケースでは、どのように組み合わせても団子を余らせずに $3$ 色団子を作ることができません。同じ色の団子を同じ串にさすことは許されません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。