Cod sursa(job #401024)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 22 februarie 2010 12:14:57
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<iostream>
#include<string>

using namespace std;

char S[10005];

int cate[26],done[26],dep[10005],du[26];

int main()
{
    int n;
    
    freopen("litere.in","r",stdin);
    freopen("litere.out","w",stdout);
    
    scanf("%d\n",&n);
    
    scanf("%s",&S);
    
    //int n=strlen(S);
    
    for(int i=n-1;i>=0;--i)
    {
        ++cate[S[i]-'a'];
        for(int j=0;j<S[i]-'a';++j)
           dep[i]+=cate[j];    
    }
    
    int de_unde=0;
    
    for(int i=0;i<26;++i)
    {
        du[i]=de_unde;
        de_unde+=cate[i];
    }       
    
    int op_tot=0;
    
    for(int i=0;i<n;++i)
    {
        int op_cur=(i-(du[S[i]-'a']+done[S[i]-'a']))+dep[i];
        ++done[S[i]-'a'];
        op_tot+=op_cur;
    }
    
    printf("%d",op_tot);
    
    return 0;
}