开始: 2026-10-08 00:00:00

【集训06】模拟赛

结束: 2026-10-10 00:00:00
当前  2026-11-04 11:35:10  类型: IOI  状态: 已经结束 

P1. 幸运数分堆lucky
描述

桌面上摆着 n 枚棋子,第 i 枚棋子上写着数字 s_i。现在要把这些棋子**全部分到 A、B 两个盒子里**(每枚棋子恰好进一个盒子,允许某个盒子为空)。

一个数字在某盒子里被称为**幸运数**,当且仅当它在该盒子里**恰好出现一次**。例如盒子中棋子数字为 \{3,3,5,7\} 时,5 和 7 是幸运数,3 不是。

问:是否存在一种分法,使得 **A 盒中幸运数的个数恰好等于 B 盒中幸运数的个数**?


输入

第一行一个整数 n。

第二行 n 个整数 s_1, s_2, \dots, s_n。


输出

如果存在满足要求的分法,输出一行 `YES`;否则输出一行 `NO`。

样例

输入

4
3 5 7 1

输出

YES

输入

3
3 5 1

输出

NO
提示

样例 1:把 3,5 放 A 盒、7,1 放 B 盒,两盒各有 2 个幸运数,方案存在,输出 `YES`。样例 2:三枚棋子数字互不相同,无论怎么分,某个盒子恰好包含 0、1、2 或 3 枚棋子,两盒幸运数个数分别是"放入的棋子数"(每枚棋子在自己盒中都恰好出现一次),两个非负整数之和为 3 时不可能相等,输出 `NO`。

对于全部数据,保证 1 \le n \le 100,1 \le s_i \le 100。

| 20% | 1~5 | 20 | n \le 8 | 

| 60% | 6~15 | 40(累计 60) | n \le 20 | 

| 100% | 16~25 | 40(累计 100) | n \le 100,s_i \le 100 | 

本题按照数据范围进行捆版测试


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交