Vòng tay giấy
Đề bài
Mô tả
Alice làm vòng tay bằng giấy bằng cách dán hai đầu của một dải giấy dài lại với nhau. Trên dải giấy có hình vẽ (), mỗi hình vẽ là một ô vuông , các hình vẽ đặt liền nhau thành một hàng; mỗi ô của hình vẽ là ký tự o (được tô) hoặc . (để trống). Dải giấy được viền bằng ký tự #: khi đặt nằm ngang, dải giấy là một hình chữ nhật có hàng , hàng và các cột toàn là #, còn khối nằm giữa các cột đó là hình vẽ theo thứ tự từ trái sang phải. Ví dụ hai dải giấy có và hình vẽ:
#############
#.o.#...#...#
#.o.#...#...#
#.o.#...#...#
#############
#################
#ooo#ooo#ooo#ooo#
#...#...#...#...#
#ooo#ooo#ooo#ooo#
#################
Khi dán, mặt có hình vẽ luôn ở phía ngoài. Vòng tay là một vòng khép kín nên không có hình vẽ nào là "đầu tiên", và vòng tay có thể bị lật ngược khi so sánh. Cụ thể, hai vòng tay được coi là giống nhau nếu chúng có cùng số hình vẽ và dải giấy (nằm ngang) của vòng này biến được thành dải giấy của vòng kia bằng các thao tác:
- chuyển hình vẽ đầu tiên (bên trái) xuống cuối dải, làm bao nhiêu lần tùy ý;
- xoay cả dải giấy (tức là đảo thứ tự các hình vẽ và xoay mỗi hình vẽ ).
Ví dụ thứ hai có bốn dải giấy, mỗi dải hình vẽ. Dải thứ nhất có cột o ở mép trái hình vẽ đầu tiên, hai hình còn lại trống. Xoay dải này được dải có cột o ở mép phải hình vẽ cuối, rồi chuyển hình vẽ đầu xuống cuối hai lần thì được đúng dải thứ hai. Chuyển hình vẽ đầu của dải thứ nhất xuống cuối hai lần thì được dải thứ ba. Vậy ba dải đầu tạo ra ba vòng tay giống nhau, còn dải thứ tư (cột o ở giữa) tạo ra một loại khác.
Alice thiết kế nhiều dải giấy trên một tờ giấy lớn kích thước rồi cắt rời từng dải để dán. Mỗi dải giấy trên tờ giấy lớn được đặt nằm ngang (kích thước ) hoặc nằm dọc (kích thước , các hình vẽ xếp từ trên xuống dưới). Dải nằm dọc được xoay thành nằm ngang trước khi dán; xoay theo chiều nào cũng cho cùng một loại vòng tay vì hai cách xoay chỉ khác nhau một phép xoay . Dải chỉ có một hình vẽ (kích thước ) được dán nằm ngang, đúng như hình vẽ trên giấy. Các dải giấy không chồng lên nhau nhưng có thể nằm sát cạnh nhau.
Hãy đếm số loại vòng tay khác nhau, và với mỗi loại, đếm số vòng tay thuộc loại đó.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và ().
Mỗi dòng trong dòng tiếp theo chứa ký tự, mỗi ký tự là ., # hoặc o. Ký tự # và o chỉ dùng để vẽ các dải giấy; ký tự . nằm ngoài các dải giấy là ô trống.
Dữ liệu đảm bảo:
- tờ giấy chỉ gồm các dải giấy hoàn chỉnh, không có ký tự # hay o nào thừa, và có ít nhất một dải giấy;
- mỗi dải giấy có không quá hình vẽ;
- mọi khối không chứa ký tự # mà viền bao quanh nó toàn là # đều là một hình vẽ của một dải giấy.
Dữ liệu ra
Dòng đầu tiên in ra số loại vòng tay .
Dòng thứ hai in ra số nguyên là số vòng tay của từng loại, theo thứ tự tăng dần.
Ràng buộc
- .
- Mỗi dải giấy có từ đến hình vẽ.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 23 28 ............................ .#############.##########... .#o..#...#...#.#o.o##o.o#... .#o..#...#...#.#.o.##.o.#... .#o..#...#...#.#o.o##o.o#... .#############.##########... ....................#o.o#... .#################..#.o.#... .#ooo#ooo#ooo#ooo#..#o.o#... .#...#...#...#...#..#####... .#ooo#ooo#ooo#ooo#..#o.o#... .#################..#.o.#... .#############......#o.o#... .#..o#...#...#......#####... .#..o#...#...##############. .#..o#...#...##.o.#...#...#. .##############.o.#...#...#. .##############.o.#...#...#. .#...#o..#...##############. .#...#o..#...#.............. .#...#o..#...#.............. .#############.............. ............................ |
5 1 1 1 1 3 |
Có vòng tay. Ba dải có cột o ở mép trái hình đầu, mép phải hình đầu, hoặc mép trái hình thứ hai là cùng một loại; bốn dải còn lại (một hình chữ X, ba hình chữ X xếp dọc, bốn hình ooo, và dải có cột o ở giữa) mỗi dải một loại. |
| 5 55 #############.#############.#############.############# #o..#...#...#.#..o#...#...#.#...#o..#...#.#.o.#...#...# #o..#...#...#.#..o#...#...#.#...#o..#...#.#.o.#...#...# #o..#...#...#.#..o#...#...#.#...#o..#...#.#.o.#...#...# #############.#############.#############.############# |
2 1 3 |
Ba dải đầu giống nhau, dải thứ tư khác. |
Bình luận