Controllers (Codeforces 1776L)
Tags: Math, binary search

You are at your grandparents' house and you are playing an old video game on a strange console. Your controller has only two buttons and each button has a number written on it.Initially, your score is $$$0$$$. The game is composed of $$$n$$$ rounds. For each $$$1\le i\le n$$$, the $$$i$$$-th round works as follows.On the screen, a symbol $$$s_i$$$ appears, which is either $$$\texttt{+}$$$ (plus) or $$$\texttt{-}$$$ (minus). Then you must press one of the two buttons on the controller once. Suppose you press a button with the number $$$x$$$ written on it: your score will increase by $$$x$$$ if the symbol was $$$\texttt{+}$$$ and will decrease by $$$x$$$ if the symbol was $$$\texttt{-}$$$. After you press the button, the round ends. After you have played all $$$n$$$ rounds, you win if your score is $$$0$$$.Over the years, your grandparents bought many different controllers, so you have $$$q$$$ of them. The two buttons on the $$$j$$$-th controller have the numbers $$$a_j$$$ and $$$b_j$$$ written on them. For each controller, you must compute whether you can win the game playing with that controller.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of rounds.The second line contains a string $$$s$$$ of length $$$n$$$ — where $$$s_i$$$ is the symbol that will appear on the screen in the $$$i$$$-th round. It is guaranteed that $$$s$$$ contains only the characters $$$\texttt{+}$$$ and $$$\texttt{-}$$$.The third line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of controllers.The following $$$q$$$ lines contain two integers $$$a_j$$$ and $$$b_j$$$ each ($$$1 \le a_j, b_j \le 10^9$$$) — the numbers on the buttons of controller $$$j$$$. 

Output: Output $$$q$$$ lines. On line $$$j$$$ print $$$\texttt{YES}$$$ if the game is winnable using controller $$$j$$$, otherwise print $$$\texttt{NO}$$$.

Note: In the first sample, one possible way to get score $$$0$$$ using the first controller is by pressing the button with numnber $$$1$$$ in rounds $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$ and $$$8$$$, and pressing the button with number $$$2$$$ in rounds $$$3$$$ and $$$7$$$. It is possible to show that there is no way to get a score of $$$0$$$ using the second controller.

Sample Inputs:
8
+-+---+-
5
2 1
10 3
7 9
10 10
5 3

6
+-++--
2
9 7
1 1

20
+-----+--+--------+-
2
1000000000 99999997
250000000 1000000000

Sample Outputs:
YES
NO
NO
NO
YES

YES
YES

NO
YES

Solution (Python):
num = input()
i = input()
m = i.count('+')
n = i.count('-')
queries = int(input())
out = []
for i in range(queries):
    number = 0.5
    (x, y) = input().split()
    x = int(x)
    y = int(y)
    temp = max(x, y)
    y = min(x, y)
    x = temp
    if not x == y:
        number = y * (n - m) / (x - y)
        if number % 1 == 0 and number <= m and (number >= -n):
            out.append('YES')
        else:
            out.append('NO')
    elif m == n:
        out.append('YES')
    else:
        out.append('NO')
for item in out:
    print(item)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
import bisect, sys
from collections import defaultdict
from itertools import accumulate
BUFSIZ = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'n' 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, BUFSIZ))
            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, BUFSIZ))
            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')
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
    return sys.stdin.readline().rstrip('\r\n')
n = int(input())
s = input()
pl = s.count('+')
mn = s.count('-')
m = int(input())
for __ in range(m):
    (a, b) = map(int, input().split())
    abmax = max(a, b)
    abmin = min(a, b)
    if pl == mn:
        print('YES')
        continue
    if pl < mn:
        smax = pl * abmax - mn * abmin
        diff_plus = abmax - abmin
        if not diff_plus:
            print('NO')
            continue
        if smax < 0:
            print('NO')
            continue
        if smax == 0:
            print('YES')
            continue
        if smax % diff_plus or smax < diff_plus:
            print('NO')
            continue
        if smax // diff_plus <= n:
            print('YES')
            continue
    else:
        smax = pl * abmin - mn * abmax
        diff_plus = abmin - abmax
        if not diff_plus:
            print('NO')
            continue
        if smax > 0:
            print('NO')
            continue
        if smax == 0:
            print('YES')
            continue
        smax = abs(smax)
        diff_plus = abs(diff_plus)
        if smax % diff_plus or smax < diff_plus:
            print('NO')
            continue
        if smax // diff_plus <= n:
            print('YES')
            continue

Solution (Python):
n = int(input())
s = str(input())
q = int(input())
nums = []
for i in range(q):
    entry = list(map(int, input().split()))
    nums.append(entry)
p = 0
m = 0
for i in range(n):
    if s[i] == '+':
        p += 1
    else:
        m += 1
if m == p:
    for i in range(q):
        print('YES')
else:
    for i in range(q):
        if nums[i][0] == nums[i][1]:
            print('NO')
        else:
            k = (m - p) * nums[i][1] / (nums[i][0] - nums[i][1])
            if k == int(k):
                if k >= -1 * m and k <= p:
                    print('YES')
                else:
                    print('NO')
            else:
                print('NO')