ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural SU Championship 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Computer Security

Time limit: 1.0 second
Memory limit: 64 MB
There was an emergency at ZZZ Inc.—its secret developments became known to a competing company! Of course, the primary suspects were the employees of ZZZ Inc. System administrator Zhuchkov was asked to report who of the employees had downloaded secret information from the server during the week preceding the incident. Zhuchkov looked through the logs and found the personal number and the data access code of the person who had done that. The administrator gave this information to the company's management, and the same evening the guilty employee disappeared without a trace and Zhuchkov was given a bonus.
However, it soon turned out that Zhuchkov had mixed up some symbols both in the personal number and in the data access code and the sacked employee had in fact been innocent. To avoid such annoying mistakes in the future, Zhuchkov had decided to find all the pairs of employees with similar numbers and check how much their data access codes were similar.
Zhuckov considers two personal numbers similar if one of them can be obtained from the other by inserting, deleting, or replacing one digit. Personal numbers do not contain leading zeros. The employees of ZZZ Inc. are numbered by consecutive integers starting from 1, and their data access codes are lines consisting of four hexadecimal digits. For each pair of employees with similar personal numbers, Zhuchkov wants to calculate the number of positions in which their data access codes differ. Help Zhuchkov.


The first line contains the number n of employees in ZZZ Inc. (2 ≤ n ≤ 65536). The i-th of the following n lines contains the data access code of the employee whose personal number is i. The data access codes consist of digits and lowercase English letters; they are different for different employees.


Output four space-separated integers. The i-th integer should be the number of pairs of employees whose personal numbers are similar and whose data access codes differ in i positions.


0 0 2 1
Problem Author: Daniil Ayzenshteyn
Problem Source: XIV Open USU Championship
To submit the solution for this problem go to the Problem set: 1738. Computer Security