UVa 12786: Friendship Networks (Solution)

10:30:00 Multiple PC World 0 Comments

Friendship Networks
For a group of N people registered at a social network, a friendship network can be constructed with the N people as the nodes and a non-directed edge between every pair of friends. For such a network, it is usual to say that a node, i.e., a person, has degree d iff there are d nodes connected to it. Note that the degree of a node is exactly his/her number of friends. Since nobody is friends with himself / herself, the degree of each node is less than N.

A key property of a friendship network is the number of friends for each one of its members, i.e., its members’ degrees. However, given an intended number of network friends for each one of the members, such a network may or may not exist. For example, for a group of 4 people there is a friendship network in which the people have 3, 2, 2, and 3 friends. However, there is no friendship network corresponding to the enumeration 1, 3, 2, and 3 for a group of 4 people.

You are working at a company that researches friendship networks with the business idea of eventually developing applications on them. Your specific job is part of a test data validation. More precisely, you must write a program that given an enumeration of positive integers, decides if there exists a friendship network with such number of friends for each of its members.

Input

The input consists of several cases. Each test case is given in a single line by a blank-separated list of integers N, d1, d2, . . . , dN, with N (2 ≤ N ≤ 1000) the number of people in the social network and the d(i) (1 ≤ i ≤ N) an enumeration of a possible friendship network. You can assume that 0 < di < N for 1 ≤ i ≤ N.

The input must be read from standard input.

Output

Output a single line for each test case. If d1, d2, . . . , dN describes a friendship network with such number of friends for each of its members, then output 1; otherwise output 0.

The output must be written to standard output.

Sample Input