### PROBLEM LINK:

**Author:** Pavel Sheftelevich

**Tester 1:** Minako Kojima

**Tester 2:** Shiplu Hawlader

**Editorialist:** Pawel Kacprzak

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Geometry, Binary search, Angles

### PROBLEM:

You are given an integer 0 < N < 360 denoting an angle. Your task is to decide if it is possible to divide this angle using only a straightedge and compass into N equal angles of size 1 degree. If it is possible, then you have to provide this contruction.

### BONUS

If you want to watch a very nice video about constructing using only a straightedge and compass, please look here.

### QUICK EXPLANATION:

First we want to decide if it is possible to do this construction. Using a well-known fact, we argue that it is only impossible to do this if N % 3 == 0. In order to prove that, we will show how to construct an angle of size 1 degree if N % 3 != 0. Moreover, knowing when it is possible can lead us to an easier construction based on dividing the original angle until we construct an angle of size 1 with sufficient precision.

### EXPLANATION:

Based on a well known result that trisecting an arbitrary angle is impossible we argue that the only case when the construction is impossible is when N % 3 == 0.

If N % 3 == 0, then construction is impossible because it implies that we can trisect the angle of size 3 - contradiction.

So we assume that N % 3 != 0. We will show that in that case we can construct an angle of size 1 which implies that we can divide the angle of size N into N equal angles of size 1.

First construct an angle of size 36.

Next, construct an angle of size 60 and bisect it in order to get an angle of size 30.

Using these two angles construct an angle of size 6 using subtraction 36 - 30 = 6.

Next, use bisection to divide an angle of size 6 into in order to get an angle of size 3.

Finally, since N % 3 != 0, we can construct an angle of size 1 using an angle of size N and an angle of size 3 - because you can construct an angle of size N - 1 if N % 3 == 2 or you can construct an angle of size N + 1 if N % 3 == 1. In any case, you can use subtraction to construct an angle of size 1.

It is clear that if you have an angle of size 1, you can “fill” the orginal angle of size N with N angles of size 1.

Ok, we proved that it is possible to construct an angle of size 1 if N % 3 != 0. We can implement this construction proof in order to output the exact steps, but it is quite complicated. The second method which was widely used by contestants is to bisect an angle of size N until you construct an angle of size 1 with sufficient precision, which is a lot easier to implement.

### AUTHOR’S AND TESTER’S SOLUTIONS:

To be uploaded soon.

### RELATED PROBLEMS:

To be uploaded soon.