← 返回题目列表

Codeforces · 1895/C

C. 撕破的幸运券

中文机器翻译题面 查看原题

票证是从 $$$1$$$ 到 $$$9$$$ 的非空数字字符串。

幸运彩票是这样的彩票:

- 它的长度是偶数;
- 前半部分的数字之和等于后半部分的数字之和。

您将获得 $$$n$$$ 门票 $$$s_1, s_2, \dots, s_n$$$。有多少对 $$$(i, j)$$$($$$1 \le i, j \le n$$$)使得 $$$s_i + s_j$$$ 是一张幸运票?请注意,$$$i=j$$$ 是可能的。

这里,+ 运算符表示两个字符串的连接。例如,如果 $$$s_i$$$ 为 13,$$$s_j$$$ 为 37,则 $$$s_i + s_j$$$ 为 1337。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 票张数。

第二行包含$$$n$$$非空字符串$$$s_1、s_2、\dots、s_n$$$,每个字符串的长度最多为$$$5$$$,并且仅包含从$$$1$$$到$$$9$$$的数字。

输出

打印一个整数 - $$$(i, j)$$$ 对的数量(对于 $$$1 \le i, j \le n$$$),使得 $$$s_i + s_j$$$ 是一张幸运票。

示例

输入 #1

10
5 93746 59 3746 593 746 5937 46 59374 6

输出 #1

20

输入 #2

5
2 22 222 2222 22222

输出 #2

13

输入 #3

3
1 1 1

输出 #3

9