1895C.md (1329B)
1 Source: https://codeforces.com/problemset/problem/1895/C 2 3 C. Torn Lucky Ticket 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A ticket is a non-empty string of digits from $1$ to $9$. 22 23 A lucky ticket is such a ticket that: 24 25 * it has an even length; 26 * the sum of digits in the first half is equal to the sum of digits in the second half. 27 28 You are given $n$ ticket pieces $s_1, s_2, \dots, s_n$. How many pairs $(i, j)$ (for $1 \le i, j \le n$) are there such that $s_i + s_j$ is a lucky ticket? Note that it's possible that $i=j$. 29 30 Here, the + operator denotes the concatenation of the two strings. For example, if $s_i$ is 13, and $s_j$ is 37, then $s_i + s_j$ is 1337. 31 32 Input 33 34 The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of ticket pieces. 35 36 The second line contains $n$ non-empty strings $s_1, s_2, \dots, s_n$, each of length at most $5$ and consisting only of digits from $1$ to $9$. 37 38 Output 39 40 Print a single integer — the number of pairs $(i, j)$ (for $1 \le i, j \le n$) such that $s_i + s_j$ is a lucky ticket. 41 42 Examples 43 44 Input 45 46 ``` 47 10 48 49 5 93746 59 3746 593 746 5937 46 59374 6 50 ``` 51 52 Output 53 54 ``` 55 20 56 ``` 57 58 Input 59 60 ``` 61 5 62 63 2 22 222 2222 22222 64 ``` 65 66 Output 67 68 ``` 69 13 70 ``` 71 72 Input 73 74 ``` 75 3 76 77 1 1 1 78 ``` 79 80 Output 81 82 ``` 83 9 84 ```