Pretty Song (Codeforces 509E)
Tags: Math, strings

When Sasha was studying in the seventh grade, he started listening to music a lot. In order to evaluate which songs he likes more, he introduced the notion of the song's prettiness. The title of the song is a word consisting of uppercase Latin letters. The prettiness of the song is the prettiness of its title.Let's define the simple prettiness of a word as the ratio of the number of vowels in the word to the number of all letters in the word.Let's define the prettiness of a word as the sum of simple prettiness of all the substrings of the word.More formally, let's define the function vowel(c) which is equal to 1, if c is a vowel, and to 0 otherwise. Let si be the i-th character of string s, and si..j be the substring of word s, staring at the i-th character and ending at the j-th character (sisi + 1... sj, i ≤ j).Then the simple prettiness of s is defined by the formula:The prettiness of s equals Find the prettiness of the given song title.We assume that the vowels are I, E, A, O, U, Y.

Input: The input contains a single string s (1 ≤ |s| ≤ 5·105) — the title of the song.

Output: Print the prettiness of the song with the absolute or relative error of at most 10 - 6.

Note: In the first sample all letters are vowels. The simple prettiness of each substring is 1. The word of length 7 has 28 substrings. So, the prettiness of the song equals to 28.

Sample Inputs:
IEAIAIO

BYOB

YISVOWEL

Sample Outputs:
28.0000000

5.8333333

17.0500000

Solution (Python):
(m, t) = (0, [q in 'IEAOUY' for q in input()])
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)

Solution (Python):
(m, t) = (0, [q in 'IEAOUY' for q in input()])
d = s = sum(t)
for k in range(len(t), 0, -1):
    m += d / k
    s -= t[k - 1] + t[-k]
    d += s
print(m)

Solution (Python):
from math import fsum

def main():
    (l, x) = ([0, 0], 0)
    for c in input():
        if c in ('I', 'E', 'A', 'O', 'U', 'Y'):
            x += 1
        l.append(x)
    n = l[-1]
    res = [float(n)]
    for m in range(2, len(l) - 1):
        n += l[-m] - l[m]
        res.append(n / m)
    print('{:.7f}'.format(fsum(res)))
if __name__ == '__main__':
    main()