codeforces-scrape

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

71C.md (1709B)


      1 Source: https://codeforces.com/problemset/problem/71/C
      2 
      3 C. Round Table Knights
      4 
      5 time limit per test
      6 
      7 0.5 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 There are *n* knights sitting at the Round Table at an equal distance from each other. Each of them is either in a good or in a bad mood.
     22 
     23 Merlin, the wizard predicted to King Arthur that the next month will turn out to be particularly fortunate if the regular polygon can be found. On all vertices of the polygon knights in a good mood should be located. Otherwise, the next month will bring misfortunes.
     24 
     25 A convex polygon is regular if all its sides have same length and all his angles are equal. In this problem we consider only regular polygons with at least 3 vertices, i. e. only nondegenerated.
     26 
     27 On a picture below some examples of such polygons are present. Green points mean knights in a good mood. Red points mean ones in a bad mood.
     28 
     29  ![](https://espresso.codeforces.com/74f876ccab06b18381319757d775aafd5756bf26.png) 
     30 
     31 King Arthur knows the knights' moods. Help him find out if the next month will be fortunate or not.
     32 
     33 Input
     34 
     35 The first line contains number *n*, which is the number of knights at the round table (3 ≤ *n* ≤ 105). The second line contains space-separated moods of all the *n* knights in the order of passing them around the table. "1" means that the knight is in a good mood an "0" means that he is in a bad mood.
     36 
     37 Output
     38 
     39 Print "YES" without the quotes if the following month will turn out to be lucky. Otherwise, print "NO".
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3  
     47 1 1 1
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 YES
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 6  
     60 1 0 1 1 1 0
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 YES
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 6  
     73 1 0 0 1 0 1
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 NO
     80 ```