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$.