Cod sursa(job #170848)

Utilizator gurneySachelarie Bogdan gurney Data 3 aprilie 2008 12:42:00
Problema PScPld Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.95 kb
program pscpld;
  const
    fin='pscpld.in';
    fout='pscpld.out';
    nmax=1000003;
var
  a:array[0..nmax] of char;
  lg:array[0..nmax*2] of longint;
  s,i,n,st,dr,p,drp,midp:longint;

function min(x,y:longint):longint;
  begin
    if x<y then
      min:=x
    else
      min:=y;
  end;

function det_lg:longint;
  begin
    if st=dr then
      det_lg:=(st-midp shr 1) shl 1-1
    else
      det_lg:=(st-midp shr 1) shl 1;
  end;

function det2_lg:longint;
  begin
    if st=dr then
      det2_lg:=(drp-st+1) shl 1-1
    else
      det2_lg:=(drp-dr+1) shl 1;
  end;

begin
  assign(input,fin);
    reset(input);
    a[0]:='#';
    while not(eof(input)) do
      begin
        inc(n);
        read(a[n]);
      end;
    a[n+1]:='$';
  close(input);
  assign(output,fout);
    rewrite(output);
    drp:=0;midp:=0;
    for i:=1 to (n shl 1)-1 do
      begin
        if i and 1=1 then
          begin
            st:=(i shr 1)+1;
            dr:=st;
          end
        else
          begin
            st:=i shr 1;
            dr:=st+1;
          end;
        if (a[st]=a[dr]) then
          begin
            if (drp>=dr) then
              begin
                p:=min(det_lg,det2_lg);
                p:=min(p,lg[midp shl 1-i]);
                dec(st,p shr 1);
                inc(dr,p shr 1);
                if (i and 1=0)and(dr-st>1) then
                  begin
                    inc(st);dec(dr);
                  end;
              end;
            while (a[st-1]=a[dr+1]) do
              begin
                dec(st);
                inc(dr);
              end;
            if dr>drp then
              begin
                drp:=dr;
                midp:=i;
              end;
            lg[i]:=dr-st+1;
            if i and 1=0 then
              inc(s,lg[i] shr 1)
            else
              inc(s,lg[i] shr 1+1);
          end;
      end;
    writeln(s);
  close(output);
end.