1692F.md (2188B)
1 Source: https://codeforces.com/problemset/problem/1692/F 2 3 F. 3SUM 4 5 time limit per test 6 7 1 second 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 Given an array $a$ of positive integers with length $n$, determine if there exist three distinct indices $i$, $j$, $k$ such that $a_i + a_j + a_k$ ends in the digit $3$. 22 23 Input 24 25 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. 26 27 The first line of each test case contains an integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the array. 28 29 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array. 30 31 The sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 32 33 Output 34 35 Output $t$ lines, each of which contains the answer to the corresponding test case. Output "YES" if there exist three distinct indices $i$, $j$, $k$ satisfying the constraints in the statement, and "NO" otherwise. 36 37 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer). 38 39 Example 40 41 Input 42 43 ``` 44 6 45 46 4 47 48 20 22 19 84 49 50 4 51 52 1 11 1 2022 53 54 4 55 56 1100 1100 1100 1111 57 58 5 59 60 12 34 56 78 90 61 62 4 63 64 1 9 8 4 65 66 6 67 68 16 38 94 25 18 99 69 ``` 70 71 Output 72 73 ``` 74 YES 75 YES 76 NO 77 NO 78 YES 79 YES 80 ``` 81 82 Note 83 84 In the first test case, you can select $i=1$, $j=4$, $k=3$. Then $a_1 + a_4 + a_3 = 20 + 84 + 19 = 123$, which ends in the digit $3$. 85 86 In the second test case, you can select $i=1$, $j=2$, $k=3$. Then $a_1 + a_2 + a_3 = 1 + 11 + 1 = 13$, which ends in the digit $3$. 87 88 In the third test case, it can be proven that no such $i$, $j$, $k$ exist. Note that $i=4$, $j=4$, $k=4$ is not a valid solution, since although $a_4 + a_4 + a_4 = 1111 + 1111 + 1111 = 3333$, which ends in the digit $3$, the indices need to be distinct. 89 90 In the fourth test case, it can be proven that no such $i$, $j$, $k$ exist. 91 92 In the fifth test case, you can select $i=4$, $j=3$, $k=1$. Then $a_4 + a_3 + a_1 = 4 + 8 + 1 = 13$, which ends in the digit $3$. 93 94 In the sixth test case, you can select $i=1$, $j=2$, $k=6$. Then $a_1 + a_2 + a_6 = 16 + 38 + 99 = 153$, which ends in the digit $3$.