Cod sursa(job #116470)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 18 decembrie 2007 17:51:49
Problema Litere Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <math.h>

long n, i, j, poz1, poz2, aux, k, q, sol, v[10010];
char st[10010];

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);
	}
	for (i = 26; i >= 1; --i) {
		for (j = 1; j < n; ++j) {
			if (v[j] == i) {
				poz1 = j;
				poz2 = j;
				for (k = j + 1; k <= n; ++k) {
					if (v[k] == i) {
						++poz2;
					} else {
						aux = v[k];
						for (q = poz2; q >= poz1; --q) {
							v[q + 1] = v[q];
						}
						v[poz1] = aux;
						++poz1;
						++poz2;
						sol += (poz2 -poz1 + 1);
					}
				}
				n = poz1 - 1;
				break;
			}
		}
	}
	printf("%ld", sol);
	return 0;
}