Codeforces Round #289 (Div. 2, ACM ICPC Rules) E. Pretty Song 算贡献+前缀和

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:

$\text{[math]}$

The prettiness of s equals

$\text{[math]}$

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.

Examples
input
IEAIAIO
output
28.0000000
input
BYOB
output
5.8333333
input
YISVOWEL
output
17.0500000

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.

题目链接：http://codeforces.com/contest/509/problem/E

题意：给你一个字符串，求字串中I, E, A, O, U, Y.的比例和；

　　　例如：BYOB　　

　　　　　　B 0 BY 1/2 BYO 2/3 BYOB 1/2

　　　　　　Y 1 YO 1 YOB 2/3

　　　　　　O 1 OB 1/2

　　　　　　B 0

　　　　　　0+1+1/2+2/3+1/2+1+1+2/3+1+1/2+0=5.833333

思路:显然算贡献的题；

　　对于一个字符，左边有l个，右边有r个，包含其的字串总有（l+1）*（r+1）个；

　　其贡献会形成一个平行四边行

　　1 1/2 1/3 1/4

　　　1/2 1/3 1/4 1/5

　　用前缀和预处理即可；

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define mk make_pair
#define eps 1e-7
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=5e5+10,M=1e6+10,inf=2147483647;
const ll INF=1e18+10,mod=1000000007;

///   数组大小
char ch[10]={'I','E','A','O','U','Y'},s[N];
double sum1[N],sum2[N],sum3[N];
int check(char a)
{
    for(int i=0;i<6;i++)
        if(a==ch[i])return 1;
    return 0;
}
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
        sum1[i]=sum1[i-1]+(1.0*1/i);
    for(int i=1;i<=n;i++)
        sum2[i]=sum2[i-1]+sum1[i];
    for(int i=n,j=1;i>=1;i--,j++)
        sum3[j]=sum3[j-1]+sum1[n]-sum1[i-1];
    double ans=0.0;
    for(int i=1;i<=n;i++)
    {
        if(check(s[i]))
        {
            int l=i;
            int r=n-i+1;
            ans+=1.0*sum1[n]*l;
            ans-=sum2[l-1];
            ans-=sum3[l-1];
        }
        //cout<<ans<<endl;
    }
    printf("%f
",ans);
    return 0;
}

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.

Then the simple prettiness of s is defined by the formula:

$\text{[math]}$

The prettiness of s equals

$\text{[math]}$

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.

Examples
input
IEAIAIO
output
28.0000000
input
BYOB
output
5.8333333
input
YISVOWEL
output
17.0500000

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.