codeforces-scrape

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

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.