trang chủ / đề bài / translit

Mất mát khi phiên âm

Đề bài

Mô tả

Khi viết tên bằng chữ cái Latin, có hai cách viết dễ gây nhầm lẫn:

  • âm u có thể viết là "u" hoặc "oo", ví dụ "ulyana" và "oolyana" là cùng một tên;
  • âm h có thể viết là "h" hoặc "kh", ví dụ "mihail" và "mikhail" là cùng một tên.

Một trang web có n người dùng, mỗi người khai báo một tên gồm các chữ cái Latin thường. Hai từ được coi là cùng một tên nếu bằng cách thay "u" ↔ "oo" và "h" ↔ "kh" (theo cả hai chiều, trong bất kỳ từ nào, bao nhiêu lần cũng được) có thể biến hai từ thành giống hệt nhau. Chữ cái sinh ra từ một phép thay trước vẫn có thể tham gia các phép thay sau.

Ví dụ, "koouper" và "kuooper" là cùng một tên vì cả hai đều biến được thành "kuuper". Tương tự, "khun" và "kkkhoon" là cùng một tên: "khun" → "khoon" và "kkkhoon" → "kkhoon" → "khoon".

Hãy chia danh sách từ thành ít nhóm nhất sao cho các từ trong mỗi nhóm là cùng một tên, và in ra số nhóm đó.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n, số từ trong danh sách.
  • n dòng tiếp theo, mỗi dòng chứa một từ gồm các chữ cái Latin thường.

Dữ liệu ra

In ra một số nguyên là số nhóm ít nhất.

Ràng buộc

  • 2≤n≤400
  • Độ dài mỗi từ từ 1 đến 20.

Ví dụ

Input Output Giải thích
10
mihail
oolyana
kooooper
hoon
ulyana
koouper
mikhail
khun
kuooper
kkkhoon
4 Các nhóm: {mihail, mikhail}, {oolyana, ulyana}, {kooooper, koouper, kuooper}, {hoon, khun, kkkhoon}.
9
hariton
hkariton
buoi
kkkhariton
boooi
bui
khariton
boui
boi
5 Các nhóm: {hariton, kkkhariton, khariton}, {hkariton}, {buoi, boooi, boui}, {bui}, {boi}. Chữ "k" đứng sau "h" trong "hkariton" không bỏ được.
2
alex
alex
1 Hai từ giống hệt nhau.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0