codeforces-scrape

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

1811D.md (1879B)


      1 Source: https://codeforces.com/problemset/problem/1811/D
      2 
      3 D. Umka and a Long Flight
      4 
      5 time limit per test
      6 
      7 3 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 The girl Umka loves to travel and participate in math olympiads. One day she was flying by plane to the next olympiad and out of boredom explored a huge checkered sheet of paper.
     22 
     23 Denote the $n$-th Fibonacci number as $F_n = \begin{cases} 1, & n = 0; \\ 1, & n = 1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{cases}$
     24 
     25 A checkered rectangle with a height of $F_n$ and a width of $F_{n+1}$ is called a Fibonacci rectangle of order $n$.
     26 
     27 Umka has a Fibonacci rectangle of order $n$. Someone colored a cell in it at the intersection of the row $x$ and the column $y$.
     28 
     29 It is necessary to cut this rectangle exactly into $n+1$ squares in such way that
     30 
     31 * the painted cell was in a square with a side of $1$;
     32 * there was at most one pair of squares with equal sides;
     33 * the side of each square was equal to a Fibonacci number.
     34 
     35 Will Umka be able to cut this rectangle in that way?
     36 
     37 Input
     38 
     39 The first line contains an integer $t$ ($1 \le t \le 2 \cdot 10^5$) — number of test cases.
     40 
     41 For each test case the integers $n$, $x$, $y$ are given ($1 \le n \le 44$, $1 \le x \le F_n$, $1 \le y \le F_{n+1}$) — the order of the Fibonacci rectangle and the coordinates of the colored cell.
     42 
     43 Output
     44 
     45 For each test case, print "YES" if the answer is positive, and "NO" otherwise.
     46 
     47 You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive answer).
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 12
     55 
     56 1 1 1
     57 
     58 2 1 2
     59 
     60 3 1 4
     61 
     62 3 3 2
     63 
     64 4 4 6
     65 
     66 4 3 3
     67 
     68 5 6 5
     69 
     70 5 4 12
     71 
     72 5 2 12
     73 
     74 4 2 1
     75 
     76 1 1 2
     77 
     78 44 758465880 1277583853
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 YES
     85 NO
     86 YES
     87 YES
     88 YES
     89 NO
     90 YES
     91 NO
     92 NO
     93 YES
     94 YES
     95 NO
     96 ```
     97 
     98 Note
     99 
    100 |  |  |  |
    101 | --- | --- | --- |
    102 |  |  |  |
    103 
    104 The first, third and fourth test cases.