310827: CF1895C. Torn Lucky Ticket
Description
A ticket is a non-empty string of digits from $1$ to $9$.
A lucky ticket is such a ticket that:
- it has an even length;
- the sum of digits in the first half is equal to the sum of digits in the second half.
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$.
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.
InputThe first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of ticket pieces.
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$.
OutputPrint 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.
ExamplesInput10 5 93746 59 3746 593 746 5937 46 59374 6Output
20Input
5 2 22 222 2222 22222Output
13Input
3 1 1 1Output
9
Output
一个幸运的车票是一个由数字1到9组成的非空字符串,且满足以下条件:它有偶数长度;第一半数字的和等于第二半数字的和。给定n个车票片段s1, s2, …, sn,问有多少对(i, j)(对于1 ≤ i, j ≤ n)存在,使得si + sj是一个幸运的车票。注意,可能存在i=j的情况。这里的+运算符表示两个字符串的连接。例如,如果si是13,sj是37,那么si + sj是1337。
输入数据格式:
第一行包含一个整数n(1 ≤ n ≤ 2 * 10^5)——车票片段的数量。
第二行包含n个非空字符串s1, s2, …, sn,每个字符串的长度最多为5,并且只由数字1到9组成。
输出数据格式:
打印一个整数——使得si + sj是一个幸运的车票的(i, j)对的数量。题目大意: 一个幸运的车票是一个由数字1到9组成的非空字符串,且满足以下条件:它有偶数长度;第一半数字的和等于第二半数字的和。给定n个车票片段s1, s2, …, sn,问有多少对(i, j)(对于1 ≤ i, j ≤ n)存在,使得si + sj是一个幸运的车票。注意,可能存在i=j的情况。这里的+运算符表示两个字符串的连接。例如,如果si是13,sj是37,那么si + sj是1337。 输入数据格式: 第一行包含一个整数n(1 ≤ n ≤ 2 * 10^5)——车票片段的数量。 第二行包含n个非空字符串s1, s2, …, sn,每个字符串的长度最多为5,并且只由数字1到9组成。 输出数据格式: 打印一个整数——使得si + sj是一个幸运的车票的(i, j)对的数量。