codeforces-scrape

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

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