codeforces-scrape

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

1312C.md (1900B)


      1 Source: https://codeforces.com/problemset/problem/1312/C
      2 
      3 C. Adding Powers
      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 Suppose you are performing the following algorithm. There is an array $v_1, v_2, \dots, v_n$ filled with zeroes at start. The following operation is applied to the array several times — at $i$-th step ($0$-indexed) you can:
     22 
     23 * either choose position $pos$ ($1 \le pos \le n$) and increase $v_{pos}$ by $k^i$;
     24 * or not choose any position and skip this step.
     25 
     26 You can choose how the algorithm would behave on each step and when to stop it. The question is: can you make array $v$ equal to the given array $a$ ($v_j = a_j$ for each $j$) after some step?
     27 
     28 Input
     29 
     30 The first line contains one integer $T$ ($1 \le T \le 1000$) — the number of test cases. Next $2T$ lines contain test cases — two lines per test case.
     31 
     32 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 30$, $2 \le k \le 100$) — the size of arrays $v$ and $a$ and value $k$ used in the algorithm.
     33 
     34 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{16}$) — the array you'd like to achieve.
     35 
     36 Output
     37 
     38 For each test case print YES (case insensitive) if you can achieve the array $a$ after some step or NO (case insensitive) otherwise.
     39 
     40 Example
     41 
     42 Input
     43 
     44 ```
     45 5
     46 4 100
     47 0 0 0 0
     48 1 2
     49 1
     50 3 4
     51 1 4 1
     52 3 2
     53 0 1 3
     54 3 9
     55 0 59049 810
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 YES
     62 YES
     63 NO
     64 NO
     65 YES
     66 ```
     67 
     68 Note
     69 
     70 In the first test case, you can stop the algorithm before the $0$-th step, or don't choose any position several times and stop the algorithm.
     71 
     72 In the second test case, you can add $k^0$ to $v_1$ and stop the algorithm.
     73 
     74 In the third test case, you can't make two $1$ in the array $v$.
     75 
     76 In the fifth test case, you can skip $9^0$ and $9^1$, then add $9^2$ and $9^3$ to $v_3$, skip $9^4$ and finally, add $9^5$ to $v_2$.