codeforces-scrape

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

1846E1.md (1982B)


      1 Source: https://codeforces.com/problemset/problem/1846/E1
      2 
      3 E1. Rudolf and Snowflakes (simple version)
      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 This is a simple version of the problem. The only difference is that in this version $n \le 10^6$.
     22 
     23 One winter morning, Rudolf was looking thoughtfully out the window, watching the falling snowflakes. He quickly noticed a certain symmetry in the configuration of the snowflakes. And like a true mathematician, Rudolf came up with a mathematical model of a snowflake.
     24 
     25 He defined a snowflake as an undirected graph constructed according to the following rules:
     26 
     27 * Initially, the graph has only one vertex.
     28 * Then, more vertices are added to the graph. The initial vertex is connected by edges to $k$ new vertices ($k \gt 1$).
     29 * Each vertex that is connected to only one other vertex is connected by edges to $k$ more new vertices. This step should be done at least once.
     30 
     31 The smallest possible snowflake for $k = 4$ is shown in the figure.
     32 
     33  ![](https://espresso.codeforces.com/5b227744dd1e23e7aee9ec94b37dd375de424c86.png) 
     34 
     35 After some mathematical research, Rudolf realized that such snowflakes may not have any number of vertices. Help Rudolf check if a snowflake with $n$ vertices can exist.
     36 
     37 Input
     38 
     39 The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     40 
     41 Then follow the descriptions of the test cases.
     42 
     43 The first line of each test case contains an integer $n$ ($1 \le n \le 10^6$) — the number of vertices for which it is necessary to check the existence of a snowflake.
     44 
     45 Output
     46 
     47 Output $t$ lines, each of which is the answer to the corresponding test case — "YES" if there exists such $k \gt 1$ for which a snowflake with the given number of vertices can be constructed; "NO" otherwise.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 9
     55 
     56 1
     57 
     58 2
     59 
     60 3
     61 
     62 6
     63 
     64 13
     65 
     66 15
     67 
     68 255
     69 
     70 10101
     71 
     72 1000000
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 NO
     79 NO
     80 NO
     81 NO
     82 YES
     83 YES
     84 YES
     85 YES
     86 NO
     87 ```