KOMPICI - Kompići

no tags 

 

After successfully solving his math homework from the previous task, Mirko has become bored, so he 
has made a list of N large integers. On the list there are some pairs of numbers that he likes, and some 
pairs he doesn’t like. 
Mirko has named the pairs that he likes pals. Two numbers are pals if they have at least one digit in 
common (not necessarily in the same position). 
Help Mirko count how many pairs of numbers in his list are pals. 
INPUT 
The first line of input contains the positive integer N (1 ≤ N ≤ 1 000 000). 
Each of the next N lines contains a positive integer from the range [1, 10
18
], a number from Mirko’s 
list. No two numbers in the list will be equal. 
OUTPUT 
The first and only line of output must contain the number of pairs that are pals. 

After successfully solving his math homework from the previous task, Mirko has become bored, so he has made a list of N large integers. On the list there are some pairs of numbers that he likes, and some pairs he doesn’t like. Mirko has named the pairs that he likes pals. Two numbers are pals if they have at least one digit in common (not necessarily in the same position). 

Help Mirko count how many pairs of numbers in his list are pals

Input

The first line of input contains the positive integer N (1 ≤ N ≤ 500 000).Each of the next N lines contains a positive integer from the range [1, 10^18], a number from Mirko’s list. No two numbers in the list will be equal.

Output

The first and only line of output must contain the number of pairs that are pals.

Example

Input:
3
4
20
44

Output:
1

hide comments
smso: 2018-07-30 13:59:27

Hint: represent each string as bit mask of size 10 and count.

charlles: 2017-12-11 14:28:32

just threat the input as an char array and the problem is easy

kingfran1907: 2017-11-07 21:15:59

Ez did it in O(69) in Brainf**k. Hint: Try not to input n. Numbers are acctualy -69 < x < 1e69
ez euler tour with bipartite matching. Of course , you need binary search. My friend getting TLE in whitespace. He is gay. If you want to merry him (username: markomafko95), solve this problem.

Last edit: 2017-11-07 21:18:16
vineetjai: 2017-09-29 21:26:20

getting time limit exceed in C++. Storing numbers in the string and then using a 2-d array to store the count 0-9 of the string. Then checking if two string 2-D array has the count greater than 0.
Which gives O(n^2) complexity. Can I improve my code?

Last edit: 2017-09-29 21:26:36
madhur4127: 2017-08-12 12:19:58

nondescript is right: 4, 2, 45, 5, 41. two possible answers(first pair 4&45 next pair 4&41 with 5&45), this question is ambiguous.

madhur4127: 2017-08-12 12:13:13

Getting wa on test case 8, help!

Shubham Jadhav: 2017-06-28 08:46:09

really nice problem

kass_97: 2017-01-13 23:43:08

Good one....O(n) for reading

Shrish Lal Bhatnagar: 2016-06-18 12:22:17

@ Erik Lonèarek
answer to 4 34 3 3 4 is "6" not "4"
pairs are (4, 34); (4, 4); (34, 3); (34, 3); (34, 4); (3, 3)

Rishul Aggarwal: 2014-02-28 11:18:54

Nice question! Those getting TLE, try to optimise EACH step of your algorithm.


Added by:Tadek Dul
Date:2011-11-23
Time limit:0.177s-0.740s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP HASK JAVA PAS-FPC PYTHON
Resource:COCI 2011/2012 2nd round