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 ≤ 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
slothsphereoj: 2024-03-25 05:23:13

Hi guys, it is possible to solve it using 0-1 trie. My code ran within 1 second, out of my suprise.

jopdhiwaala: 2020-07-18 13:31:51

Use long long unsigned int or you will get wa

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


Added by:Tadek Dul
Date:2011-11-23
Time limit:1s
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