codeforces-scrape

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

1714E.md (2846B)


      1 Source: https://codeforces.com/problemset/problem/1714/E
      2 
      3 E. Add Modulo 10
      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 given an array of $n$ integers $a_1, a_2, \dots, a_n$
     22 
     23 You can apply the following operation an arbitrary number of times:
     24 
     25 * select an index $i$ ($1 \le i \le n$) and replace the value of the element $a_i$ with the value $a_i + (a_i \bmod 10)$, where $a_i \bmod 10$ is the remainder of the integer dividing $a_i$ by $10$.
     26 
     27 For a single index (value $i$), this operation can be applied multiple times. If the operation is applied repeatedly to the same index, then the current value of $a_i$ is taken into account each time. For example, if $a_i=47$ then after the first operation we get $a_i=47+7=54$, and after the second operation we get $a_i=54+4=58$.
     28 
     29 Check if it is possible to make all array elements equal by applying multiple (possibly zero) operations.
     30 
     31 For example, you have an array $[6, 11]$.
     32 
     33 * Let's apply this operation to the first element of the array. Let's replace $a_1 = 6$ with $a_1 + (a_1 \bmod 10) = 6 + (6 \bmod 10) = 6 + 6 = 12$. We get the array $[12, 11]$.
     34 * Then apply this operation to the second element of the array. Let's replace $a_2 = 11$ with $a_2 + (a_2 \bmod 10) = 11 + (11 \bmod 10) = 11 + 1 = 12$. We get the array $[12, 12]$.
     35 
     36 Thus, by applying $2$ operations, you can make all elements of an array equal.
     37 
     38 Input
     39 
     40 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. What follows is a description of each test case.
     41 
     42 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array.
     43 
     44 The second line of each test case contains $n$ integers $a_i$ ($0 \le a_i \le 10^9$) — array elements.
     45 
     46 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     47 
     48 Output
     49 
     50 For each test case print:
     51 
     52 * YES if it is possible to make all array elements equal;
     53 * NO otherwise.
     54 
     55 You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer) .
     56 
     57 Example
     58 
     59 Input
     60 
     61 ```
     62 10
     63 
     64 2
     65 
     66 6 11
     67 
     68 3
     69 
     70 2 18 22
     71 
     72 5
     73 
     74 5 10 5 10 5
     75 
     76 4
     77 
     78 1 2 4 8
     79 
     80 2
     81 
     82 4 5
     83 
     84 3
     85 
     86 93 96 102
     87 
     88 2
     89 
     90 40 6
     91 
     92 2
     93 
     94 50 30
     95 
     96 2
     97 
     98 22 44
     99 
    100 2
    101 
    102 1 5
    103 ```
    104 
    105 Output
    106 
    107 ```
    108 Yes
    109 No
    110 Yes
    111 Yes
    112 No
    113 Yes
    114 No
    115 No
    116 Yes
    117 No
    118 ```
    119 
    120 Note
    121 
    122 The first test case is clarified above.
    123 
    124 In the second test case, it is impossible to make all array elements equal.
    125 
    126 In the third test case, you need to apply this operation once to all elements equal to $5$.
    127 
    128 In the fourth test case, you need to apply this operation to all elements until they become equal to $8$.
    129 
    130 In the fifth test case, it is impossible to make all array elements equal.
    131 
    132 In the sixth test case, you need to apply this operation to all elements until they become equal to $102$.