Cod sursa(job #118262)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 24 decembrie 2007 00:21:49
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>
#include <string>

#define sigma 26
#define maxn 10010

int n,sol;
char a[maxn];
int b[maxn];
int st[sigma],v[sigma];

int main()
{
    freopen("litere.in","r",stdin);
    freopen("litere.out","w",stdout);
    
    scanf("%d ",&n);
    
    scanf("%s ",a);
    
    int i,j;
    
    for (i=n-1;i>=0;i--) 
    {
        v[a[i]-'a']++;
        for (j=0;j<a[i]-'a';j++) b[i]+=v[j];
    }
    
    for (i=1;i<sigma;i++) st[i] = st[i-1] + v[i-1];
    
    for (i=0;i<n;i++) 
    {
        sol+=i+b[i]-st[a[i]-'a'];
        st[a[i]-'a']++;
    }
    
    printf("%d\n",sol);
    
    return 0;
}