Problem
Description
You are
given N sticks of varying lengths. You need to determine whether it is possible
to form a polygon of positive area by arranging them in some order. For
example, if three sticks of lengths 1, 1, 1 are given we can easily see that we
can form a triangle by arranging them in order. On the other hand, if the
sticks have lengths 1, 2, 1, then we cannot form a polygon of non-zero area
with these.
Constraints
1 <= N
<= 100
Length of
any stick will be less than 100
Input Format
The first
line contains an integer N indicating number of sticks
The next
line contains N space separated positive integers giving the lengths of the
sticks
Output
Format
One line
containing the number of sides of the polygon of most sides (of at least 3
sides) that can be formed with some of the sticks. If no polygon can be formed,
the output should be 0.
Explanation
Example 1
Input
3
1 1 1
Output
3
Explanation
N=3, and
there are 3 sticks, each of length 1. With three sticks of length 1, we can
form a triangle
Example 2
Input
4
1 2 3 6
Output
0
Explanation
We cannot
form a 4 sided polygon using all four sticks. Similarly, a triangle cannot be
formed with any three sticks. Since no polygon can be formed, the result is 0.
No comments:
Post a Comment