Cod sursa(job #331494)

Utilizator bugyBogdan Vlad bugy Data 14 iulie 2009 11:21:39
Problema Litere Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
using namespace std;
#define dim 10004
unsigned long v[dim],w[dim],a[dim],b[dim];   
void merge_sort(int li, int ls)      
{      
    int j,i,k,jum,m=0;      
    if(li==ls) return;      
    jum=(li+ls)/2;      
    merge_sort(li,jum);      
    merge_sort(jum+1,ls);      
    i=li;j=jum+1;k=li;      
          
    while((i<=jum)||(j<=ls))      
    {      
        if(j>ls || ( (i<=jum) && (v[i] < v[j])) )      
        {      
            w[k] = v[i];  m++;b[k]=a[i];    
            k++;      
            i++;      
        }      
        else     
        {      
            w[k] = v[j]; m++;b[k]=a[j];     
            k++;      
            j++;      
        }      
    }      
          
    for(i = ls; i >= li; i--)      
	{
		v[i] = w[i]; a[i]=b[i];
	}
}   



char s;
int main()
{FILE *f=fopen("litere.in","r"), *g=fopen("litere.out","w");
long i,n,m,ss=0,sss=0,schimb=0,j,man,k;
	fscanf(f,"%ld ",&n);
	m=n;
for(i=1;i<=n;i++)
	{fscanf(f,"%c",&s);
	v[++sss]=(int)s-96;
	a[i]=i;}
	
merge_sort(1,n);
	for(i=1;i<n;i++)
		for(j=i;j<=n;j++)
			if(v[i]!=v[j])
				if(a[i]>a[j])
					schimb++;
				
	fprintf(g,"%ld\n",schimb);
	

fclose(f);
fclose(g);

return 0;}