Problem 863D : Umka and a Long Flight || Full Detailed Solution || Codeforces

 Question :

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.

Denote the n$�$-th Fibonacci number as Fn=⎧⎩⎨1,1,Fn−2+Fn−1,n=0;n=1;n≥2.${�}_{�}=\{\begin{array}{ll}1,& �=0;\\ 1,& �=1;\\ {�}_{�-2}+{�}_{�-1},& �\ge 2.\end{array}$

A checkered rectangle with a height of Fn${�}_{�}$ and a width of Fn+1${�}_{�+1}$ is called a Fibonacci rectangle of order n$�$.

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$�$.

It is necessary to cut this rectangle exactly into n+1$�+1$ squares in such way that

• the painted cell was in a square with a side of 1$1$;
• there was at most one pair of squares with equal sides;
• the side of each square was equal to a Fibonacci number.

Will Umka be able to cut this rectangle in that way?

Input

The first line contains an integer t$�$ (1≤t≤2⋅105$1\le �\le 2\cdot {10}^5$) — number of test cases.

For each test case the integers n$�$, x$�$, y$�$ are given (1≤n≤44$1\le �\le 44$, 1≤x≤Fn$1\le �\le {�}_{�}$, 1≤y≤Fn+1$1\le �\le {�}_{�+1}$) — the order of the Fibonacci rectangle and the coordinates of the colored cell.

Output

For each test case, print "YES" if the answer is positive, and "NO" otherwise.

You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive answer).

Example

input

Copy

12
1 1 1
2 1 2
3 1 4
3 3 2
4 4 6
4 3 3
5 6 5
5 4 12
5 2 12
4 2 1
1 1 2
44 758465880 1277583853

output

Copy

YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO

Explanation :

If n<=1 answer is true. Otherwise, let h=fib[n], w=fib[n+1], we must cut a h*h square from left or right. If we cut from left and (x, y) is remained in the right part, which is a fibonacci ractangle of order n-1, we can solve the problem recursively. Similar for we cut from right and and (x, y) is remained in the left part. If no matter we cut the square from left or right, (x, y) can not be remained then answer is false.

Solution :

#include <bits/stdc++.h>
using namespace std;
#define ll long long int

vector<ll> F;

bool solve(ll x, ll y, ll n){

  if(n==1) return true;

  if(min(y, F[n+1] - y + 1) > F[n+1] - F[n]){
    return false;
  }

  y = min(y, F[n+1] - y + 1);

  return solve(y,x,n-1);

}

int main(){
    ll t,n,x1,y1,x2,y2;
    cin>>t;

    F.push_back(1);
    F.push_back(1);
    for(int i = 0;i<46;i++){
      F.push_back(F[i] + F[i+1]);
    }

    while(t--){
      cin>>n>>x1>>y1;

      if(solve(x1,y1,n)){
        cout<<"YES\n";
      }else{
        cout<<"NO\n";
      }
    }

   
    return 0;

}

I Hope you liked it please tell me the suggestion in the comment below what shoud I change according to you.

And discuss the Approach in comment section if you want. share the solution with you frnds too.