codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1096C.md (1477B)


      1 Source: https://codeforces.com/problemset/problem/1096/C
      2 
      3 C. Polygon for the Angle
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an angle $\text{ang}$.
     22 
     23 The Jury asks You to find such regular $n$-gon (regular polygon with $n$ vertices) that it has three vertices $a$, $b$ and $c$ (they can be non-consecutive) with $\angle{abc} = \text{ang}$ or report that there is no such $n$-gon.
     24 
     25  ![](https://espresso.codeforces.com/620524eefc0e15b7466976d1c5958f32ab911a47.png) 
     26 
     27 If there are several answers, print the minimal one. It is guarantied that if answer exists then it doesn't exceed $998244353$.
     28 
     29 Input
     30 
     31 The first line contains single integer $T$ ($1 \le T \le 180$) — the number of queries.
     32 
     33 Each of the next $T$ lines contains one integer $\text{ang}$ ($1 \le \text{ang} \lt 180$) — the angle measured in degrees.
     34 
     35 Output
     36 
     37 For each query print single integer $n$ ($3 \le n \le 998244353$) — minimal possible number of vertices in the regular $n$-gon or $-1$ if there is no such $n$.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 54
     46 50
     47 2
     48 178
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 10
     55 18
     56 90
     57 180
     58 ```
     59 
     60 Note
     61 
     62 The answer for the first query is on the picture above.
     63 
     64 The answer for the second query is reached on a regular $18$-gon. For example, $\angle{v_2 v_1 v_6} = 50^{\circ}$.
     65 
     66 The example angle for the third query is $\angle{v_{11} v_{10} v_{12}} = 2^{\circ}$.
     67 
     68 In the fourth query, minimal possible $n$ is $180$ (not $90$).