「CF509E」Pretty Song

2015年1月31日3,8830

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.

Sample test(s)
input

output

input

output

input

output

Note

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

题解

将序列看成01串，元音为1

要算∑ (sum(j)-sum(i+1))/(j-i+1)

发现枚举分母后，对于sum再维护前缀和sum2，就能每次O1时间计算对答案贡献

 

avatar
  Subscribe  
提醒