codeforces-scrape

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

911C.md (2140B)


      1 Source: https://codeforces.com/problemset/problem/911/C
      2 
      3 C. Three Garlands
      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 Mishka is decorating the Christmas tree. He has got three garlands, and all of them will be put on the tree. After that Mishka will switch these garlands on.
     22 
     23 When a garland is switched on, it periodically changes its state — sometimes it is lit, sometimes not. Formally, if *i*-th garland is switched on during *x*-th second, then it is lit only during seconds *x*, *x* + *k**i*, *x* + 2*k**i*, *x* + 3*k**i* and so on.
     24 
     25 Mishka wants to switch on the garlands in such a way that during each second after switching the garlands on there would be at least one lit garland. Formally, Mishka wants to choose three integers *x*1, *x*2 and *x*3 (not necessarily distinct) so that he will switch on the first garland during *x*1-th second, the second one — during *x*2-th second, and the third one — during *x*3-th second, respectively, and during each second starting from *max*(*x*1, *x*2, *x*3) at least one garland will be lit.
     26 
     27 Help Mishka by telling him if it is possible to do this!
     28 
     29 Input
     30 
     31 The first line contains three integers *k*1, *k*2 and *k*3 (1 ≤ *k**i* ≤ 1500) — time intervals of the garlands.
     32 
     33 Output
     34 
     35 If Mishka can choose moments of time to switch on the garlands in such a way that each second after switching the garlands on at least one garland will be lit, print YES.
     36 
     37 Otherwise, print NO.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 2 2 3
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 YES
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 4 2 3
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 NO
     63 ```
     64 
     65 Note
     66 
     67 In the first example Mishka can choose *x*1 = 1, *x*2 = 2, *x*3 = 1. The first garland will be lit during seconds 1, 3, 5, 7, ..., the second — 2, 4, 6, 8, ..., which already cover all the seconds after the 2-nd one. It doesn't even matter what *x*3 is chosen. Our choice will lead third to be lit during seconds 1, 4, 7, 10, ..., though.
     68 
     69 In the second example there is no way to choose such moments of time, there always be some seconds when no garland is lit.