PROBLEM STATEMENT
You've collected data in a vector dogs which describes how many dogs are present in each
neighborhood of your city, and you wish to represent this data in a pie chart. The total number
of dogs in your city is exactly 100, so if a neighborhood has 15 dogs, it will form a solid region
in the chart with an area equal to 15% of the whole pie chart.
Given a pie chart, a dividing line is a line that passes through the center of the chart and
doesn't pass through the interior of any solid region of the chart. For example, the chart on the
left has two dividing lines, while the chart on the right has only one dividing line (see examples
0 and 1 for the data that forms these two charts).
Note that there may be several ways to create a pie chart from the same data. Return the maximum
number of dividing lines in a pie chart that can be made from the data.
DEFINITION
Class:SymmetricPie
Method:getLines
Parameters:vector
Returns:int
Method signature:int getLines(vector dogs)
CONSTRAINTS
-dogs will contain between 1 and 8 elements, inclusive.
-Each element of dogs will be between 1 and 100, inclusive.
-The sum of all elements of dogs will be exactly 100.
EXAMPLES
0)
{10,40,10,40}
Returns: 2
This is the left pie chart in the problem statement's diagram.
1)
{10,50,40}
Returns: 1
This is the right pie chart in the problem statement's diagram.
2)
{50,50}
Returns: 1
The only line here divides the chart through the center.
3)
{1,48,1,1,48,1}
Returns: 3
The best solution here is to put the regions in the order (1,1,48,1,1,48), giving us 3 dividing
lines.
4)
{2,2,96}
Returns: 0
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.