COCI '16 Contest 4 #6 Osmosmjerka

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 4.0s
Memory limit: 256M

Problem type

We have created an infinite eight-directional crossword by taking a letter-filled block of dimensions M \times N and infinitely repeating it. For instance, if we are given the following block:

honi
hsin

then we create the following crossword:

...honihonihonihoni...
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...

that is infinite in all directions.

In the created crossword, we randomly choose a field and one of eight directions, then write down a word of length K obtained by reading the crossword starting from the initial field, in the chosen direction. If we executed this query twice (independently), we would obtain two words of length K. Calculate the probability that the two words are equal.

Input Specification

The first line of input contains integers M, N, K from the task (1 \le M, N \le 500, 2 \le K \le 10^9).

Each of the following M lines contains N lowercase letters of the English alphabet, and describes a block of the crossword. At least two distinct letters will exist in the block.

Output Specification

You must output the required probability in the form of a reduced fraction p/q, without spaces.

Scoring

In test cases worth 100 total points, it will hold M = N.

Sample Input 1

1 2 2
ab

Sample Output 1

5/16

Sample Input 2

2 4 3
honi
hsin

Sample Output 2

19/512

Sample Input 3

3 3 10
ban
ana
nab

Sample Output 3

2/27

Comments

There are no comments at the moment.