AtCoder Grand Contest 016
翻译中…
Problem Statement
翻译中…
There are $N$ cats. We number them from $1$ through $N$.
翻译中…
Each of the cats wears a hat. Cat $i$ says: "there are exactly $a_i$ different colors among the $N - 1$ hats worn by the cats except me."
翻译中…
Determine whether there exists a sequence of colors of the hats that is consistent with the remarks of the cats.
翻译中…
Constraints
翻译中…
$2 ≤ N ≤ 10^5$$1 ≤ a_i ≤ N-1$
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N
a_1 a_2 ... a_N翻译中…
Output
翻译中…
Print Yes if there exists a sequence of colors of the hats that is consistent with the remarks of the cats; print No otherwise.
翻译中…
样例
Input #1
3
1 2 2
Output #1
Yes
For example, if cat $1$, $2$ and $3$ wears red, blue and blue hats, respectively, it is consistent with the remarks of the cats.
Input #2
3
1 1 2
Output #2
No
From the remark of cat $1$, we can see that cat $2$ and $3$ wear hats of the same color. Also, from the remark of cat $2$, we can see that cat $1$ and $3$ wear hats of the same color. Therefore, cat $1$ and $2$ wear hats of the same color, which contradicts the remark of cat $3$.
Input #3
5
4 3 4 3 4
Output #3
No
Input #4
3
2 2 2
Output #4
Yes
Input #5
4
2 2 2 2
Output #5
Yes
Input #6
5
3 3 3 3 3
Output #6
No
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。