1182C.md (3273B)
1 Source: https://codeforces.com/problemset/problem/1182/C 2 3 C. Beautiful Lyrics 4 5 time limit per test 6 7 1 second 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 You are given $n$ words, each of which consists of lowercase alphabet letters. Each word contains at least one vowel. You are going to choose some of the given words and make as many beautiful lyrics as possible. 22 23 Each lyric consists of two lines. Each line consists of two words separated by whitespace. 24 25 A lyric is beautiful if and only if it satisfies all conditions below. 26 27 * The number of vowels in the first word of the first line is the same as the number of vowels in the first word of the second line. 28 * The number of vowels in the second word of the first line is the same as the number of vowels in the second word of the second line. 29 * The last vowel of the first line is the same as the last vowel of the second line. Note that there may be consonants after the vowel. 30 31 Also, letters "a", "e", "o", "i", and "u" are vowels. Note that "y" is never vowel. 32 33 For example of a beautiful lyric, 34 35 "hello hellooowww" 36 37 "whatsup yowowowow" 38 39 is a beautiful lyric because there are two vowels each in "hello" and "whatsup", four vowels each in "hellooowww" and "yowowowow" (keep in mind that "y" is not a vowel), and the last vowel of each line is "o". 40 41 For example of a not beautiful lyric, 42 43 "hey man" 44 45 "iam mcdic" 46 47 is not a beautiful lyric because "hey" and "iam" don't have same number of vowels and the last vowels of two lines are different ("a" in the first and "i" in the second). 48 49 How many beautiful lyrics can you write from given words? Note that you cannot use a word more times than it is given to you. For example, if a word is given three times, you can use it at most three times. 50 51 Input 52 53 The first line contains single integer $n$ ($1 \le n \le 10^{5}$) — the number of words. 54 55 The $i$-th of the next $n$ lines contains string $s_{i}$ consisting lowercase alphabet letters — the $i$-th word. It is guaranteed that the sum of the total word length is equal or less than $10^{6}$. Each word contains at least one vowel. 56 57 Output 58 59 In the first line, print $m$ — the number of maximum possible beautiful lyrics. 60 61 In next $2m$ lines, print $m$ beautiful lyrics (two lines per lyric). 62 63 If there are multiple answers, print any. 64 65 Examples 66 67 Input 68 69 ``` 70 14 71 wow 72 this 73 is 74 the 75 first 76 mcdics 77 codeforces 78 round 79 hooray 80 i 81 am 82 proud 83 about 84 that 85 ``` 86 87 Output 88 89 ``` 90 3 91 about proud 92 hooray round 93 wow first 94 this is 95 i that 96 mcdics am 97 ``` 98 99 Input 100 101 ``` 102 7 103 arsijo 104 suggested 105 the 106 idea 107 for 108 this 109 problem 110 ``` 111 112 Output 113 114 ``` 115 0 116 ``` 117 118 Input 119 120 ``` 121 4 122 same 123 same 124 same 125 differ 126 ``` 127 128 Output 129 130 ``` 131 1 132 same differ 133 same same 134 ``` 135 136 Note 137 138 In the first example, those beautiful lyrics are one of the possible answers. Let's look at the first lyric on the sample output of the first example. "about proud hooray round" forms a beautiful lyric because "about" and "hooray" have same number of vowels, "proud" and "round" have same number of vowels, and both lines have same last vowel. On the other hand, you cannot form any beautiful lyric with the word "codeforces". 139 140 In the second example, you cannot form any beautiful lyric from given words. 141 142 In the third example, you can use the word "same" up to three times.