codeforces-scrape

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

820B.md (2329B)


      1 Source: https://codeforces.com/problemset/problem/820/B
      2 
      3 B. Mister B and Angle in Polygon
      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 On one quiet day all of sudden Mister B decided to draw angle *a* on his field. Aliens have already visited his field and left many different geometric figures on it. One of the figures is regular convex *n*-gon (regular convex polygon with *n* sides).
     22 
     23 That's why Mister B decided to use this polygon. Now Mister B must find three distinct vertices *v*1, *v*2, *v*3 such that the angle ![](https://espresso.codeforces.com/c96cdfe08c576797192f794d1c8f9c5948471c4e.png) (where *v*2 is the vertex of the angle, and *v*1 and *v*3 lie on its sides) is as close as possible to *a*. In other words, the value ![](https://espresso.codeforces.com/a065e60ada2155058fd60edbc54771fbad586d48.png) should be minimum possible.
     24 
     25 If there are many optimal solutions, Mister B should be satisfied with any of them.
     26 
     27 Input
     28 
     29 First and only line contains two space-separated integers *n* and *a* (3 ≤ *n* ≤ 105, 1 ≤ *a* ≤ 180) — the number of vertices in the polygon and the needed angle, in degrees.
     30 
     31 Output
     32 
     33 Print three space-separated integers: the vertices *v*1, *v*2, *v*3, which form ![](https://espresso.codeforces.com/c96cdfe08c576797192f794d1c8f9c5948471c4e.png). If there are multiple optimal solutions, print any of them. The vertices are numbered from 1 to *n* in clockwise order.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 3 15
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 1 2 3
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 4 67
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 2 1 3
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 4 68
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 4 1 2
     71 ```
     72 
     73 Note
     74 
     75 In first sample test vertices of regular triangle can create only angle of 60 degrees, that's why every possible angle is correct.
     76 
     77 Vertices of square can create 45 or 90 degrees angles only. That's why in second sample test the angle of 45 degrees was chosen, since |45 - 67| < |90 - 67|. Other correct answers are: "3 1 2", "3 2 4", "4 2 3", "4 3 1", "1 3 4", "1 4 2", "2 4 1", "4 1 3", "3 1 4", "3 4 2", "2 4 3", "2 3 1", "1 3 2", "1 2 4", "4 2 1".
     78 
     79 In third sample test, on the contrary, the angle of 90 degrees was chosen, since |90 - 68| < |45 - 68|. Other correct answers are: "2 1 4", "3 2 1", "1 2 3", "4 3 2", "2 3 4", "1 4 3", "3 4 1".