Cod sursa(job #114933)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 16 decembrie 2007 09:39:25
Problema Litere Scor 40
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasele 5-8 Marime 0.86 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

long n, v[10010], i, axc, last, a[10010], aux, z;
long long inter;
char st[10010];

int cmp (const void * a, const void * b) {
  return ( *(int*)a - *(int*)b );
}


int main() {
	freopen("litere.in", "r", stdin);
	freopen("litere.out", "w", stdout);
	scanf("%ld", &n);
	scanf("%s", st);
	for (i = 0; i < n; ++i) {
		v[i + 1] = (long)(st[i] - 'a' + 1);
		a[i + 1] = v[i + 1];
	//	printf("%ld ", v[i + 1]);
	}
	qsort(v + 1, n, sizeof(int), cmp);
/*	for (i = 1; i <= n; ++i) {
		printf("%ld ", v[i]);
	}*/
	aux = n + 1;
	while (aux > 1) {
		--aux;
		while (a[aux] != v[aux]) {
			axc = v[aux];
			last = aux - 1;
			while (a[last] != axc) {
				--last;
			}
			z = a[last];
			a[last] = a[last + 1];
			a[last + 1] = z;
			++inter;
		}
	}
	printf("%lld\n", inter);
	return 0;
}