codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1776L.md (2539B)


      1 Source: https://codeforces.com/problemset/problem/1776/L
      2 
      3 L. Controllers
      4 
      5 time limit per test
      6 
      7 2 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 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.
     22 
     23 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.
     24 
     25 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.
     26 
     27 After you have played all $n$ rounds, you win if your score is $0$.
     28 
     29 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.
     30 
     31 Input
     32 
     33 The first line contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of rounds.
     34 
     35 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{-}$.
     36 
     37 The third line contains an integer $q$ ($1 \le q \le 10^5$) — the number of controllers.
     38 
     39 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$.
     40 
     41 Output
     42 
     43 Output $q$ lines. On line $j$ print $\texttt{YES}$ if the game is winnable using controller $j$, otherwise print $\texttt{NO}$.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 8
     51 +-+---+-
     52 5
     53 2 1
     54 10 3
     55 7 9
     56 10 10
     57 5 3
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 YES
     64 NO
     65 NO
     66 NO
     67 YES
     68 ```
     69 
     70 Input
     71 
     72 ```
     73 6
     74 +-++--
     75 2
     76 9 7
     77 1 1
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 YES
     84 YES
     85 ```
     86 
     87 Input
     88 
     89 ```
     90 20
     91 +-----+--+--------+-
     92 2
     93 1000000000 99999997
     94 250000000 1000000000
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 NO
    101 YES
    102 ```
    103 
    104 Note
    105 
    106 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.