201363: [AtCoder]ARC136 D - Without Carry

Memory Limit:1024 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

You are given an integer sequence of length $N$: $A=(A_1,A_2,\cdots,A_N)$.

Find the number of pairs of integers $(i,j)$ ($1 \leq i < j \leq N$) such that calculation of $A_i+A_j$ by column addition does not involve carrying.

Constraints

  • $2 \leq N \leq 10^6$
  • $0 \leq A_i \leq 10^6-1$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Print the answer.


Sample Input 1

4
4 8 12 90

Sample Output 1

3

The pairs $(i,j)$ that count are $(1,3),(1,4),(2,4)$.

For example, calculation of $A_1+A_3=4+12$ does not involve carrying, so $(i,j)=(1,3)$ counts. On the other hand, calculation of $A_3+A_4=12+90$ involves carrying, so $(i,j)=(3,4)$ does not count.


Sample Input 2

20
313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908

Sample Output 2

6

Sample Input 3

5
1 1 1 1 1

Sample Output 3

10

Input

题意翻译

给定一个长度为 $n$ 的数列 $S$,设 $A_{i,j}$ 代表 $S_i$ 十进制表示法中从右往左数第 $j$ 位的数,如果字符串长度 $<j$ 则 $A_{i,j} = 0$。 求满足 $\forall k \in [1, 7], A_{i, k} + A_{j, k} < 10$ 的二元数对 $(i, j)$ 的个数。

加入题单

上一题 下一题 算法标签: