codeforces-scrape

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

1907E.md (1551B)


      1 Source: https://codeforces.com/problemset/problem/1907/E
      2 
      3 E. Good Triples
      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 Given a non-negative integer number $n$ ($n \ge 0$). Let's say a triple of non-negative integers $(a, b, c)$ is good if $a + b + c = n$, and $digsum(a) + digsum(b) + digsum(c) = digsum(n)$, where $digsum(x)$ is the sum of digits of number $x$.
     22 
     23 For example, if $n = 26$, then the pair $(4, 12, 10)$ is good, because $4 + 12 + 10 = 26$, and $(4) + (1 + 2) + (1 + 0) = (2 + 6)$.
     24 
     25 Your task is to find the number of good triples for the given number $n$. The order of the numbers in a triple matters. For example, the triples $(4, 12, 10)$ and $(10, 12, 4)$ are two different triples.
     26 
     27 Input
     28 
     29 The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Descriptions of test cases follow.
     30 
     31 The first and only line of the test case contains one integer $n$ ($0 \le n \le 10^7$).
     32 
     33 Output
     34 
     35 For each test case output one integer, the number of good triples for the given integer $n$. Order of integers in a triple matters.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 12
     43 
     44 11
     45 
     46 0
     47 
     48 1
     49 
     50 2
     51 
     52 3
     53 
     54 4
     55 
     56 5
     57 
     58 3141
     59 
     60 999
     61 
     62 2718
     63 
     64 9999999
     65 
     66 10000000
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 9
     73 1
     74 3
     75 6
     76 10
     77 15
     78 21
     79 1350
     80 166375
     81 29160
     82 1522435234375
     83 3
     84 ```
     85 
     86 Note
     87 
     88 In the first example, the good triples are $(0, 0, 11)$, $(0, 1, 10)$, $(0, 10, 1)$, $(0, 11, 0)$, $(1, 0, 10)$, $(1, 10, 0)$, $(10, 0, 1)$, $(10, 1, 0)$, $(11, 0, 0)$.
     89 
     90 In the second example, there is only one good triple $(0, 0, 0)$.