KOMPICI - Kompići
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, 1018], 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
|
rising_stark:
2024-11-18 19:33:04
The regular inclusion exclusion(IE) with a time complexity of (n * 2^10) will TLE. Think IE but a little better with some preprocess |
|
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
|
|
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.
|
|
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 |
| 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 |
RSS