COCI '11 Contest 5 #4 Razbibriga

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

Mirko has already solved all crosswords available in daily newspapers, and he is too intimidated by ACTA to download new ones from the Internet. Now he has asked Frane to challenge him with a programming problem. Frane has eagerly responded with a brand new task, and was kind enough not to lock the task under copyright protection, so you are allowed to attempt it too!

Four words with equal lengths can be put together in a square such that two words mark horizontal edges, while the other two mark vertical edges. Horizontal words are read left to right, and vertical ones from top to bottom. Corner letters are shared by the two neighbouring edges. The figure below shows one possible square created from words HLAD, NIVA, HSIN, DEDA.

\displaystyle \begin{array}{|c|c|c|c|}\hline
H&L&A&D\\\hline
S&&&E\\\hline
I&&&D\\\hline
N&I&V&A\\\hline
\end{array}

Your task is, given a list of equal-length words, to compute the number of different squares that can be put together from a subset of these words. You are not allowed to repeat a word in the same square. Two squares are different if they differ in at least one character.

Input Specification

The first line of input contains the positive integer N (4 \le N \le 100\,000), the number of words in the list.

Each of the next N lines contains a single word consisting only of uppercase English letters.

Each word contains at most 10 characters. All words will be distinct and have equal length.

Output Specification

The first and only line of output must contain the required number of distinct squares.

Note: Test data will ensure that the solution fits in a 64-bit integer data type (int64 in Pascal, long long in C/C++).

Sample Input 1

4
NIVA
HLAD
HSIN
DEDA

Sample Output 1

2

Sample Input 2

6
BAKA
BARA
BALC
CALC
ARHC
BLIC

Sample Output 2

8

Comments

There are no comments at the moment.