codeforces-scrape

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

138A.md (2846B)


      1 Source: https://codeforces.com/problemset/problem/138/A
      2 
      3 A. Literature Lesson
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Vera adores poems. All the poems Vera knows are divided into quatrains (groups of four lines) and in each quatrain some lines contain rhymes.
     22 
     23 Let's consider that all lines in the poems consist of lowercase Latin letters (without spaces). Letters "a", "e", "i", "o", "u" are considered vowels.
     24 
     25 Two lines rhyme if their suffixes that start from the *k*-th vowels (counting from the end) match. If a line has less than *k* vowels, then such line can't rhyme with any other line. For example, if *k* = 1, lines *commit* and *hermit* rhyme (the corresponding suffixes equal *it*), and if *k* = 2, they do not rhyme (*ommit* ≠ *ermit*).
     26 
     27 Today on a literature lesson Vera learned that quatrains can contain four different schemes of rhymes, namely the following ones (the same letters stand for rhyming lines):
     28 
     29 * Clerihew (*aabb*);
     30 * Alternating (*abab*);
     31 * Enclosed (*abba*).
     32 
     33 If all lines of a quatrain pairwise rhyme, then the quatrain can belong to any rhyme scheme (this situation is represented by *aaaa*).
     34 
     35 If all quatrains of a poem belong to the same rhyme scheme, then we can assume that the whole poem belongs to this rhyme scheme. If in each quatrain all lines pairwise rhyme, then the rhyme scheme of the poem is *aaaa*. Let us note that it doesn't matter whether lines from different quatrains rhyme with each other or not. In other words, it is possible that different quatrains aren't connected by a rhyme.
     36 
     37 Vera got a long poem as a home task. The girl has to analyse it and find the poem rhyme scheme. Help Vera cope with the task.
     38 
     39 Input
     40 
     41 The first line contains two integers *n* and *k* (1 ≤ *n* ≤ 2500, 1 ≤ *k* ≤ 5) — the number of quatrains in the poem and the vowel's number, correspondingly. Next 4*n* lines contain the poem. Each line is not empty and only consists of small Latin letters. The total length of the lines does not exceed 104.
     42 
     43 If we assume that the lines are numbered starting from 1, then the first quatrain contains lines number 1, 2, 3, 4; the second one contains lines number 5, 6, 7, 8; and so on.
     44 
     45 Output
     46 
     47 Print the rhyme scheme of the poem as "aabb", "abab", "abba", "aaaa"; or "NO" if the poem does not belong to any of the above mentioned schemes.
     48 
     49 Examples
     50 
     51 Input
     52 
     53 ```
     54 1 1  
     55 day  
     56 may  
     57 sun  
     58 fun
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 aabb
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 1 1  
     71 day  
     72 may  
     73 gray  
     74 way
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 aaaa
     81 ```
     82 
     83 Input
     84 
     85 ```
     86 2 1  
     87 a  
     88 a  
     89 a  
     90 a  
     91 a  
     92 a  
     93 e  
     94 e
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 aabb
    101 ```
    102 
    103 Input
    104 
    105 ```
    106 2 1  
    107 day  
    108 may  
    109 sun  
    110 fun  
    111 test  
    112 hill  
    113 fest  
    114 thrill
    115 ```
    116 
    117 Output
    118 
    119 ```
    120 NO
    121 ```
    122 
    123 Note
    124 
    125 In the last sample both quatrains have rhymes but finding the common scheme is impossible, so the answer is "NO".