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.