Umka and a Long Flight (Codeforces 1811D)
Tags: Math, constructive algorithms

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 $$$F_n = \begin{cases} 1, & n = 0; \\ 1, & n = 1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{cases}$$$A checkered rectangle with a height of $$$F_n$$$ and a width of $$$F_{n+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$$$ squares in such way that  the painted cell was in a square with a side of $$$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 \le t \le 2 \cdot 10^5$$$) — number of test cases.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.

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).

Note:   The first, third and fourth test cases. 

Sample Inputs:
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

Sample Outputs:
YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO

Solution (Python):
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073]

def is_possible(n, x, y):
    if n == 1:
        return True
    if n < 1:
        return False
    if n == 2:
        if (x, y) == (1, 1) or (x, y) == (2, 1) or (x, y) == (1, 3) or ((x, y) == (2, 3)):
            return True
        else:
            return False
    current_width = fib[n + 1]
    current_height = fib[n]
    f1 = current_height
    f2 = current_width - current_height
    if x <= current_height - f2 and y <= current_width - f1:
        return is_possible(n - 2, x, y)
    if x <= current_height - f2 and y > f1:
        return is_possible(n - 2, x, y - f1)
    if x > f2 and y <= current_width - f1:
        return is_possible(n - 2, x - f2, y)
    if x > f2 and y > f1:
        return is_possible(n - 2, x - f2, y - f1)
    return False
ans = []
t = int(input())
for _ in range(t):
    (n, x, y) = map(int, input().split())
    ans.append('yes' if is_possible(n, x, y) else 'no')
print('\n'.join(ans))

Solution (Python):
import sys
E = lambda : map(int, sys.stdin.readline().split())
F = [1, 1]
while len(F) < 46:
    F.append(F[-1] + F[-2])

def f(s, c, y):
    if s == 1:
        return 1
    if y <= F[s - 1]:
        return f(s - 1, y, c)
    if F[s + 1] - y < F[s - 1]:
        return f(s - 1, F[s + 1] - y + 1, c)
    return 0
for _ in range(*E()):
    print(['NO', 'YES'][f(*E())])

Solution (Python):
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073]

def is_possible(n, x, y):
    if n == 1:
        return True
    if n < 1:
        return False
    if n == 2:
        if (x, y) == (1, 1) or (x, y) == (2, 1) or (x, y) == (1, 3) or ((x, y) == (2, 3)):
            return True
        else:
            return False
    current_width = fib[n + 1]
    current_height = fib[n]
    f1 = current_height
    f2 = current_width - current_height
    if x <= current_height - f2 and y <= current_width - f1:
        return is_possible(n - 2, x, y)
    if x <= current_height - f2 and y > f1:
        return is_possible(n - 2, x, y - f1)
    if x > f2 and y <= current_width - f1:
        return is_possible(n - 2, x - f2, y)
    if x > f2 and y > f1:
        return is_possible(n - 2, x - f2, y - f1)
    return False
ans = ''
t = int(input())
for _ in range(t):
    (n, x, y) = map(int, input().split())
    ans += 'yes' if is_possible(n, x, y) else 'no'
    ans += '\n'
print(ans)