AIOC Banner

Problem: Castle Cavalry

Want to try solving this problem? You can submit your code online if you log in or register.

Castle Cavalry

Input File: cavalryin.txt
Output File: cavalryout.txt
Time Limit: 1 second
Memory Limit: 1 GB

As the Queen's chief technologist, you have been tasked with organising the army's newest cutting edge1 division: the cavalry.

Naturally, the Queen is sceptical, so to prove it's worth it you are going to conduct a quick field test. Firstly, you will need to group your knights into squads.

Unfortunately, the N knights in your division are very inexperienced, having only been training for two weeks! The ith knight (counting from 1) has told you that they would only be comfortable in a squad containing exactly ai knights.

You can make as many or as few squads as you like of any size, so long as every knight is comfortable.

After feeding your whining, whinnying horses their pheasant-based supper, you return to your lonely lodge to determine if it is possible to divide up your cavalry.


The first line of input will contain N, the number of knights in your division.

Then, N lines will follow. The ith line (counting from 1) will contain ai, the size of the squad the ith knight wants to join.


Print YES on a single line if it is possible to put the knights into squads such that they are all comfortable. If it is not possible, then print NO instead.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2



In the first case, you can put knights 1 and 3 in one squad, and knights 2, 4 and 5 into a second one. This makes them all comfortable, so the answer is YES.

In the second case, you can put knights 1 and 2 together in the same squad, but then knight 3 cannot form a squad by themselves (since knight 3 wants to be in a squad of size 2). No matter what you do, one of the knights is going to get left out, so the answer is NO.

Subtasks & Constraints

For all subtasks, 1 ≤ N ≤ 100,000, and 1 ≤ ai ≤ N.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 25 March 2023,  7:11pm AEDT