302232: CF429C. Guess the Tree

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Guess the Tree

题意翻译

## 题面描述 你被要求构建这样一棵有根树: - 此树除叶节点外的节点都至少有两个儿子。 - $i$ 号节点子树大小为 $c_i$ 。 ## 输入格式 第一行读入一个正整数 $n (1<=n<=24)$ ,表示树的大小 。 第二行读入 $n$ 个正整数 $c_i$ 表示 $i$ 号节点子树大小为 $c_i$ 。 ## 输出格式 如果能构建输出 YES ,否则输出 NO 。

题目描述

Iahub and Iahubina went to a picnic in a forest full of trees. Less than 5 minutes passed before Iahub remembered of trees from programming. Moreover, he invented a new problem and Iahubina has to solve it, otherwise Iahub won't give her the food. Iahub asks Iahubina: can you build a rooted tree, such that - each internal node (a node with at least one son) has at least two sons; - node $ i $ has $ c_{i} $ nodes in its subtree? Iahubina has to guess the tree. Being a smart girl, she realized that it's possible no tree can follow Iahub's restrictions. In this way, Iahub will eat all the food. You need to help Iahubina: determine if there's at least one tree following Iahub's restrictions. The required tree must contain $ n $ nodes.

输入输出格式

输入格式


The first line of the input contains integer $ n $ ( $ 1<=n<=24 $ ). Next line contains $ n $ positive integers: the $ i $ -th number represents $ c_{i} $ $ (1<=c_{i}<=n) $ .

输出格式


Output on the first line "YES" (without quotes) if there exist at least one tree following Iahub's restrictions, otherwise output "NO" (without quotes).

输入输出样例

输入样例 #1

4
1 1 1 4

输出样例 #1

YES

输入样例 #2

5
1 1 5 2 1

输出样例 #2

NO

Input

题意翻译

## 题面描述 你被要求构建这样一棵有根树: - 此树除叶节点外的节点都至少有两个儿子。 - $i$ 号节点子树大小为 $c_i$ 。 ## 输入格式 第一行读入一个正整数 $n (1<=n<=24)$ ,表示树的大小 。 第二行读入 $n$ 个正整数 $c_i$ 表示 $i$ 号节点子树大小为 $c_i$ 。 ## 输出格式 如果能构建输出 YES ,否则输出 NO 。

加入题单

上一题 下一题 算法标签: