COCI 2016/2017 - Contest 4 - Osmosmjerka

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 4.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 4
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Chúng ta có thể tạo ra một ô chữ vô tận 8-hướng bằng cách lặp lại một khối chữ kích thước ~M \times N~ vô số lần. Giả sử chúng ta có khối chữ sau:

honi
hsin

Với khối chữ trên, ta tạo ra ô chữ vô tận 8-hướng sau:

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

Với ô chữ đã tạo, ta sẽ chọn ngẫu nhiên một ô và một hướng bất kì trong 8 hướng. Sau đó, ta sẽ viết xuống một từ gồm ~K~ chữ cái bắt đầu từ ô được chọn và đi theo hướng được chọn. Nếu ta thực hiện thao tác trên hai lần một cách độc lập, ta sẽ thu được hai từ với độ dài ~K~. Hãy tính xác suất thu được hai từ giống nhau.

Input

Dòng đầu tiên chứa các số nguyên ~M~, ~N~, ~K~ ~(1 \leq M,N \leq 500, \: 2 \leq K \leq 10^9)~.

Mỗi dòng trong số ~M~ dòng tiếp theo chứa ~N~ chữ cái Tiếng Anh in thường, mô tả một khối chữ trong ô chữ. Khối chữ được đảm bảo sẽ có ít nhất hai chữ cái phân biệt.

Output

In ra xác suất cần tìm dưới dạng một phân số tối giản ~p/q~ (không chứa khoảng trắng).

Subtask

  • ~5~ test đầu tiên có ~M=N~.
  • ~3~ test còn lại không có ràng buộc gì thêm.

Sample 1

Input
1 2 2
ab
Output
5/16

Sample 2

Input
2 4 3
honi
hsin
Output
19/152

Sample 3

Input
3 3 10
ban
ana
nab
Output
2/27

Comments

Please read the guidelines before commenting.


There are no comments at the moment.