atcoder#AGC016B. [AGC016B] Colorful Hats
[AGC016B] Colorful Hats
题目描述
匹の猫がいます。 猫には から まで番号が振られています。
各猫はある色の帽子を被っています。 猫 は「自分を除く 匹の猫が被っている帽子の色の種類数はちょうど である」と言っています。
すべての猫の発言と矛盾しないような帽子の色の組合せが存在するか判定してください。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
すべての猫の発言と矛盾しないような帽子の色の組合せが存在するならば、Yes
を出力せよ。 存在しないならば、No
を出力せよ。
题目大意
有$N$只猫,每只猫带着某种颜色的帽子,给出每只猫能看到(即其他$N-1$只猫)的颜色种数$a[i]$,问是否可以构造出合法序列。
有只猫,每只猫带着某种颜色的帽子,给出每只猫能看到(即其他只猫)的颜色种数,问是否可以构造出合法序列。
3
1 2 2
Yes
3
1 1 2
No
5
4 3 4 3 4
No
3
2 2 2
Yes
4
2 2 2 2
Yes
5
3 3 3 3 3
No
提示
制約
Sample Explanation 1
例えば、猫 , , の帽子の色がそれぞれ赤、青、青ならば、すべての猫の発言と矛盾しません。
Sample Explanation 2
猫 の発言から、猫 , の帽子の色は同一です。 また、猫 の発言から、猫 , の帽子の色は同一です。 よって、猫 , の帽子の色は同一ですが、これは猫 の発言に矛盾します。