LCC '18 Contest 4 J4 - Prefix Codes

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

In Wlmojstan, the telephone system runs on a prefix code system. This means that every phone number has a code at the beginning that identifies the location of the caller.

Prefix codes can be of variable length, so to prevent ambiguity, each prefix code cannot share a prefix with any other prefix code.

A prefix of a prefix code is defined as the first P digits in the code, with 2 \leq P \leq 19

Given a list of codes, can you identify the number of conflicting codes?

Input Specification

The first line will contain one integer, N, the number of prefix codes in the list. 1 \leq N \leq 10^{5}.

The next N lines will contain one integer, C, a prefix code. 0 \leq C \leq 10^{18}.

Output Specification

The number of prefix codes that conflict with another prefix code.

Sample Input

5
4141
41
5151
5551
51

Sample Output

4

Comments

There are no comments at the moment.