codeforces-scrape

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

2050C.md (1746B)


      1 Source: https://codeforces.com/problemset/problem/2050/C
      2 
      3 C. Uninteresting Number
      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 a number $n$ with a length of no more than $10^5$.
     22 
     23 You can perform the following operation any number of times: choose one of its digits, square it, and replace the original digit with the result. The result must be a digit (that is, if you choose the digit $x$, then the value of $x^2$ must be less than $10$).
     24 
     25 Is it possible to obtain a number that is divisible by $9$ through these operations?
     26 
     27 Input
     28 
     29 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     30 
     31 The only line of each test case contains the number $n$, without leading zeros. The length of the number does not exceed $10^5$.
     32 
     33 It is guaranteed that the sum of the lengths of the numbers across all test cases does not exceed $10^5$.
     34 
     35 Output
     36 
     37 For each test case, output "YES" if it is possible to obtain a number divisible by $9$ using the described operations, and "NO" otherwise.
     38 
     39 You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 9
     47 
     48 123
     49 
     50 322
     51 
     52 333333333333
     53 
     54 9997
     55 
     56 5472778912773
     57 
     58 1234567890
     59 
     60 23
     61 
     62 33
     63 
     64 52254522632
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 NO
     71 YES
     72 YES
     73 NO
     74 NO
     75 YES
     76 NO
     77 YES
     78 YES
     79 ```
     80 
     81 Note
     82 
     83 In the first example, from the integer $123$, it is possible to obtain only $123$, $143$, $129$, and $149$, none of which are divisible by $9$.
     84 
     85 In the second example, you need to replace the second digit with its square; then $n$ will equal $342 = 38 \cdot 9$.
     86 
     87 In the third example, the integer is already divisible by $9$.