codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

883F.md (3412B)


      1 Source: https://codeforces.com/problemset/problem/883/F
      2 
      3 F. Lost in Transliteration
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There are some ambiguities when one writes Berland names with the letters of the Latin alphabet.
     22 
     23 For example, the Berland sound u can be written in the Latin alphabet as "u", and can be written as "oo". For this reason, two words "ulyana" and "oolyana" denote the same name.
     24 
     25 The second ambiguity is about the Berland sound h: one can use both "h" and "kh" to write it. For example, the words "mihail" and "mikhail" denote the same name.
     26 
     27 There are *n* users registered on the Polycarp's website. Each of them indicated a name represented by the Latin letters. How many distinct names are there among them, if two ambiguities described above are taken into account?
     28 
     29 Formally, we assume that two words denote the same name, if using the replacements "u" ![](https://espresso.codeforces.com/8774ca35b6e628888a4670e4539d47857e5e5841.png) "oo" and "h" ![](https://espresso.codeforces.com/8774ca35b6e628888a4670e4539d47857e5e5841.png) "kh", you can make the words equal. One can make replacements in both directions, in any of the two words an arbitrary number of times. A letter that resulted from the previous replacement can participate in the next replacements.
     30 
     31 For example, the following pairs of words denote the same name:
     32 
     33 * "koouper" and "kuooper". Making the replacements described above, you can make both words to be equal: "koouper" ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) "kuuper" and "kuooper" ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) "kuuper".
     34 * "khun" and "kkkhoon". With the replacements described above you can make both words to be equal: "khun" ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) "khoon" and "kkkhoon" ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) "kkhoon" ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) "khoon".
     35 
     36 For a given list of words, find the minimal number of groups where the words in each group denote the same name.
     37 
     38 Input
     39 
     40 The first line contains integer number *n* (2 ≤ *n* ≤ 400) — number of the words in the list.
     41 
     42 The following *n* lines contain words, one word per line. Each word consists of only lowercase Latin letters. The length of each word is between 1 and 20 letters inclusive.
     43 
     44 Output
     45 
     46 Print the minimal number of groups where the words in each group denote the same name.
     47 
     48 Examples
     49 
     50 Input
     51 
     52 ```
     53 10  
     54 mihail  
     55 oolyana  
     56 kooooper  
     57 hoon  
     58 ulyana  
     59 koouper  
     60 mikhail  
     61 khun  
     62 kuooper  
     63 kkkhoon
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 4
     70 ```
     71 
     72 Input
     73 
     74 ```
     75 9  
     76 hariton  
     77 hkariton  
     78 buoi  
     79 kkkhariton  
     80 boooi  
     81 bui  
     82 khariton  
     83 boui  
     84 boi
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 5
     91 ```
     92 
     93 Input
     94 
     95 ```
     96 2  
     97 alex  
     98 alex
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 1
    105 ```
    106 
    107 Note
    108 
    109 There are four groups of words in the first example. Words in each group denote same name:
    110 
    111 1. "mihail", "mikhail"
    112 2. "oolyana", "ulyana"
    113 3. "kooooper", "koouper"
    114 4. "hoon", "khun", "kkkhoon"
    115 
    116 There are five groups of words in the second example. Words in each group denote same name:
    117 
    118 1. "hariton", "kkkhariton", "khariton"
    119 2. "hkariton"
    120 3. "buoi", "boooi", "boui"
    121 4. "bui"
    122 5. "boi"
    123 
    124 In the third example the words are equal, so they denote the same name.