|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
K - Shrinking Polygons
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
A polygon is said to be inscribed in a circle when all its vertices lie on that circle. In this problem you will be given a polygon inscribed in a circle, and you must determine the minimum number of vertices that should be removed to transform the given polygon into a regular polygon, i.e., a polygon that is equiangular (all angles are congruent) and equilateral (all edges have the same length).
When you remove a vertex v from a polygon you first remove the vertex and the edges connecting it to its adjacent vertices $w_1$ and $w_2$, and then create a new edge connecting $w_1$ and $w_2$. Figure (a) below illustrates a polygon inscribed in a circle, with ten vertices, and figure (b) shows a pentagon (regular polygon with five edges) formed by removing five vertices from the polygon in (a).
In this problem, we consider that any polygon must have at least three edges.
Input
The input contains several test cases. The first line of a test case contains one integer $N$ indicating the number of vertices of the inscribed polygon $(3 \leq N \leq 10^4)$. The second line contains $N$ integers $X_i$ separated by single spaces ($1 \leq X_i \leq 10^3$ , for $0 \leq i \leq N - 1$). Each $X_i$ represents the length of the arc defined in the inscribing circle, clockwise, by vertex $i$ and vertex $(i + 1) mod N$. Remember that an arc is a segment of the circumference of a circle; do not mistake it for a chord, which is a line segment whose endpoints both lie on a circle.
The end of input is indicated by a line containing only one zero.
The input must be read from standard input.
Output
For each test case in the input, your program must print a single line, containing the minimum number of vertices that must be removed from the given polygon to form a regular polygon. If it is not possible to form a regular polygon, the line must contain only the value $-1$.
The output must be written to standard output.
Sample test(s)
Input
3
1000 1000 1000
6
1 2 3 1 2 3
3
1 1 2
10
10 40 20 30 30 10 10 50 24 26
0
Output
0
2
-1
5