Cod sursa(job #130348)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 31 ianuarie 2008 21:26:40
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#include <string.h>

const int N_MAX = 10010;

char s[N_MAX];
int frecv[32], mare[N_MAX];

int main()
{
	freopen("litere.in", "r", stdin);
#ifndef _SCREEN_
	freopen("litere.out", "w", stdout);
#endif

	int N, i, L;
	scanf("%d\n", &N);
	scanf("%s\n", s);
//	puts(s);
	L = strlen(s);

	int cate, j;
	for (i = 0; i < L; i ++) {

		cate = 0;
		for (j = s[i] + 1; j <= 'z'; j ++) {
	   	   cate += frecv[j - 'a'];
		}
		frecv[s[i] - 'a'] ++; 

		mare[i + 1] = cate;
	}

	int rez = 0, poz = L;
	for (i = 'z'; i >= 'a'; i --) {
		if (frecv[i - 'a']) {

			for (j = L; j > 0; j --) {
				if (s[j - 1] == i) {
//					printf("%c %d %d %d\n", i, poz, j, mare[j]);
					rez += poz - j + mare[j];
					poz --;
				}
			}
		}
	}

	printf("%d\n", rez);

	return 0;
}