Cod sursa(job #115235)

Utilizator CezarMocanCezar Mocan CezarMocan Data 16 decembrie 2007 11:46:43
Problema Litere Scor 40
Compilator fpc Status done
Runda preONI 2008, Runda 2, Clasa a 9-a Marime 1.22 kb
var v,x,w,poz:array[1..10010] of longint;
    p,t:array[1..28]  of longint;
    n,i,j,aux,rez,k:longint;
    c:char;

procedure qsort(ls,ld:longint);
var i,j,aux:longint;
begin
  i:=ls;j:=ld;
  while true do begin
    while (v[i]<=v[j])and(i<>j) do inc(i);
    if i=j then break;
    aux:=v[i];v[i]:=v[j];v[j]:=aux;dec(j);
    while (v[i]<=v[j])and(i<>j) do dec(j);
    if i=j then break;
    aux:=v[i];v[i]:=v[j];v[j]:=aux;inc(i);
  end;
  if j-1>ls then qsort(ls,j-1);
  if j+1<ld then qsort(j+1,ld);
end;


begin
assign(input,'litere.in');reset(input);
assign(output,'litere.out');rewrite(output);
readln(n);
for i:=1 to n do
        begin
        read(c);
        v[i]:=ord(c)-96;
        end;
x:=v;
qsort(1,n);
for i:=1 to n do
        if v[i]<>v[i-1] then
                p[v[i]]:=i;
for i:=1 to n do
        begin
        inc(t[x[i]]);
        w[i]:=p[x[i]]+t[x[i]]-1;
        end;
for i:=1 to n do
        poz[w[i]]:=i;
for i:=1 to n do
        begin
        j:=poz[i];
        inc(rez,j-i);
        poz[i]:=i;
        for k:=1 to n do
                if (poz[w[k]]>=i)and(poz[w[k]]<j) then
                        inc(poz[w[k]]);
        end;
writeln(rez);
close(input);close(output);
end.