Cod sursa(job #204859)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 27 august 2008 16:28:58
Problema Litere Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<stdio.h>
#define N 10007
char s[N];
int v[30];
long long z;
void rearenge(int x,int y){
	int k,r;
	char c=x+'a';
	for(k=y;s[k]!=c;++k);
	z+=k-y;
	for(r=k;r>y;--r)
		s[r]=s[r-1];
	s[y]=c;
}
int main(){
	int n,i,j,q,in='a'-'a',sf='z'-'a';
	freopen("litere.in","r",stdin);
	freopen("litere.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s);
	for(i=0;i<n;++i){
		++v[s[i]-'a'];
	}
	q=0;
	for(i=in;i<=sf;++i)
		if(v[i]){
			for(j=q;j<q+v[i];++j)
				if(s[j]!=i+'a')
					rearenge(i,j);
			q+=v[i];
		}
	printf("%lld\n",z);
	fclose(stdin);
	fclose(stdout);
	return 0;
}