codeforces-scrape

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

1829D.md (1866B)


      1 Source: https://codeforces.com/problemset/problem/1829/D
      2 
      3 D. Gold Rush
      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 Initially you have a single pile with $n$ gold nuggets. In an operation you can do the following:
     22 
     23 * Take any pile and split it into two piles, so that one of the resulting piles has exactly twice as many gold nuggets as the other. (All piles should have an integer number of nuggets.)
     24 
     25  ![](https://espresso.codeforces.com/89d0bd70b2b86d29bcf49af918569568ff949cf6.png)
     26 
     27 One possible move is to take a pile of size $6$ and split it into piles of sizes $2$ and $4$, which is valid since $4$ is twice as large as $2$.
     28 
     29  Can you make a pile with exactly $m$ gold nuggets using zero or more operations?
     30 
     31 Input
     32 
     33 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     34 
     35 The only line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^7$) — the starting and target pile sizes, respectively.
     36 
     37 Output
     38 
     39 For each test case, output "YES" if you can make a pile of size exactly $m$, and "NO" otherwise.
     40 
     41 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 11
     49 
     50 6 4
     51 
     52 9 4
     53 
     54 4 2
     55 
     56 18 27
     57 
     58 27 4
     59 
     60 27 2
     61 
     62 27 10
     63 
     64 1 1
     65 
     66 3 1
     67 
     68 5 1
     69 
     70 746001 2984004
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 YES
     77 YES
     78 NO
     79 NO
     80 YES
     81 YES
     82 NO
     83 YES
     84 YES
     85 NO
     86 NO
     87 ```
     88 
     89 Note
     90 
     91 The first test case is pictured in the statement. We can make a pile of size $4$.
     92 
     93 In the second test case, we can perform the following operations: $\{\color{red}{9}\} \to \{\color{red}{6},3\} \to \{4,2,3\}$. The pile that is split apart is colored red before each operation.
     94 
     95 In the third test case, we can't perform a single operation.
     96 
     97 In the fourth test case, we can't end up with a larger pile than we started with.