ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. How to Become Star?

Time limit: 1.0 second
Memory limit: 64 MB
The people think about this problem for several centuries. The programmer Vasechkin’s front office decided to find it out. But the front office is the front office, so the task to find out the answer to the question "How to become a star?" was given to its subordinate Vasechkin.
It’s often happens that account’s and programmer’s notion of the problem much differ. So this time it came off not exactly how the front office has thought. Vasechkin formalized the problem as follows.
Definition. A star is the closed broken line built by the final amount of steps of the following algorithm:
  1. Fix and arbitrary angle α (0 < α < π).
  2. The first link is (0, 0) — (1, 0).
  3. The second link is the resultant of the turn by the angle α counter-clockwise with respect to the point (1, 0) of the first one.
  4. The (i + 2)-nd link is the resultant of the turn by the angle α counter-clockwise of the (i + 1)-st one with respect to the free end (the opposite to the one that is connected to the i-th link) of the (i + 1)-st link.
  5. The algorithm stops immediately when the broken line is closed.
Problem illustrationProblem illustration
Definition. A number of the vertices of the star is the number of the broken line’s links.


The only integer N (3 ≤ N ≤ 100000).


Output an amount of different stars with N vertices.


Problem Author: Pavel Egorov
Problem Source: Open collegiate programming contest for high school children of the Sverdlovsk region, October 11, 2003
To submit the solution for this problem go to the Problem set: 1259. How to Become Star?