Conveyor (Codeforces 1733E)
Tags: Math, dp

There is a conveyor with $$$120$$$ rows and $$$120$$$ columns. Each row and column is numbered from $$$0$$$ to $$$119$$$, and the cell in $$$i$$$-th row and $$$j$$$-th column is denoted as $$$(i, j)$$$. The top leftmost cell is $$$(0, 0)$$$. Each cell has a belt, and all belts are initially facing to the right.Initially, a slime ball is on the belt of $$$(0, 0)$$$, and other belts are empty. Every second, the state of the conveyor changes as follows:   All slime balls on the conveyor move one cell in the direction of the belt at the same time. If there is no cell in the moved position, the slime gets out of the conveyor, and if two slime balls move to the same cell, they merge into one.  All belts with slime ball in the previous second change direction at the same time: belts facing to the right become facing to the down, and vice versa.  A new slime ball is placed on cell $$$(0, 0)$$$. There are $$$q$$$ queries, each being three integers $$$t$$$, $$$x$$$, and $$$y$$$. You have to find out if there is a slime at the cell $$$(x, y)$$$ after $$$t$$$ seconds from the start. Can you do it?

Input: The first line contains one integer $$$q$$$ ($$$1 \le q \le 10^4$$$) — the number of queries.The only line of each query contains three integers $$$t$$$, $$$x$$$, and $$$y$$$ ($$$0 \le t \le 10^{18}$$$, $$$0 \le x, y < 120$$$).

Output: Print the answer for each test case, one per line. If there is a slime ball in the cell $$$(x, y)$$$ after $$$t$$$ seconds from the initial state, print "YES". Otherwise, print "NO".

Note: The state of conveyor with $$$t = 0$$$. Red arrow represents the direction of each belt, and blue figure represents slime.The state of conveyor with $$$t = 1$$$.The state of conveyor with $$$t = 2$$$.

Sample Inputs:
6
1 1 0
5 1 3
0 0 0
2 4 5
2 0 2
1547748756 100 111

Sample Outputs:
NO
YES
YES
NO
YES
YES

Solution (Python):
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisect
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
test_cases = II()
for _ in range(test_cases):
    (t, x, y) = MI()
    if t < x + y:
        print('NO')
        continue
    (a, b) = ([0] * 240, [0] * 240)
    a[0] = t - x - y
    b[0] = a[0] + 1
    for i in range(x + y):
        for j in range(i, -1, -1):
            a[j + 1] += a[j] // 2
            a[j] -= a[j] // 2
            b[j + 1] += b[j] // 2
            b[j] -= b[j] // 2
    (px, py) = (-1, -1)
    for i in range(240):
        if a[i] != b[i]:
            px = i
            py = x + y - i
    if (x, y) == (px, py):
        print('YES')
    else:
        print('NO')

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
    (t, x, y) = map(int, input().split())
    d = x + y
    if d > t:
        print('NO')
        return
    t -= d
    cnt = [[0] * 120 for _ in range(120)]
    cnt[0][0] = t
    for i in range(120):
        for j in range(120):
            if i != 119:
                cnt[i + 1][j] += cnt[i][j] // 2
            if j != 119:
                cnt[i][j + 1] += (cnt[i][j] + 1) // 2
    i = j = 0
    for _ in range(d):
        if cnt[i][j] & 1:
            i += 1
        else:
            j += 1
        if i == 120 or j == 120:
            print('NO')
            return
    if i == x and j == y:
        print('YES')
    else:
        print('NO')
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = lambda : sys.stdin.readline()[:-1]
get_int = lambda : int(input())
get_int_iter = lambda : map(int, input().split())
get_int_list = lambda : list(get_int_iter())
flush = lambda : sys.stdout.flush()
DEBUG = False

def debug(*args):
    if DEBUG:
        print(*args)

def solve_case():
    (t, x, y) = get_int_iter()
    field = [[0] * 122 for _ in range(122)]
    field[0][0] = t - x - y
    if t - x - y < 0:
        return 'NO'
    debug(x, y)
    for i in range(x + 1):
        for j in range(y + 1):
            field[i][j + 1] += (field[i][j] >> 1) + (field[i][j] & 1)
            field[i + 1][j] += field[i][j] >> 1
    (i, j) = (0, 0)
    while (i < x or j < y) and (not (i > x or j > y)):
        debug(i, j, field[i][j])
        if field[i][j] & 1:
            i += 1
        else:
            j += 1
    return 'YES' if i == x and j == y else 'NO'
for _ in range(get_int()):
    print(solve_case())