Cod sursa(job #98969)

Utilizator gurneySachelarie Bogdan gurney Data 10 noiembrie 2007 19:47:27
Problema Abc2 Scor 0
Compilator fpc Status done
Runda Happy Coding 2007 Marime 2.29 kb
program abc2;
  const
    fin='abc2.in';
    fout='abc2.out';
    lmax=20;
    nmax=100000;
    tr:array['a'..'c'] of byte=(0,1,2);
var
  d:array[1..nmax] of int64;
  a:array[1..10000000] of byte;
  cuv:array[1..20] of byte;
  lga,lg,i,j,k,n,x,y,logmax:longint;
  c,p3,pmax:int64;
  ch:char;
  num:longint;

procedure qsort(st,dr:longint);
  var
    i,j:longint;
    tmp,x:int64;
  begin
    i:=st;j:=dr;
    x:=d[(st+dr)shr 1];
    repeat
      while d[i]<x do
        inc(i);
      while d[j]>x do
        dec(j);
      if i<=j then
        begin
          tmp:=d[i];d[i]:=d[j];d[j]:=tmp;
          inc(i);dec(j);
        end;
    until i>j;
    if j>st then
      qsort(st,j);
    if i<dr then
      qsort(i,dr);
  end;

function query(x:int64):boolean;
  var
    i:longint;
    log:longint;
  begin
    log:=logmax;
    i:=0;
    while log>=0 do
      begin
        if i+1 shl log<=n then
        if x>=d[i+(1 shl log)] then
          inc(i,1 shl log);
        dec(log);
      end;
    query:=(x=d[i]);
  end;

begin
  assign(input,fin);
    reset(input);
    lga:=0;
    while not(seekeoln(input)) do
      begin
        read(ch);
        inc(lga);
        a[lga]:=tr[ch];
      end;
    readln;
    n:=1;lg:=0;pmax:=1;
    while not(seekeoln(input)) do
      begin
        read(ch);
        inc(lg);
        cuv[lg]:=tr[ch];
        pmax:=pmax*3;
      end;
    pmax:=pmax div 3;
    p3:=pmax;
    for i:=1 to lg do
      begin
        inc(d[1],p3*cuv[i]);
        p3:=p3 div 3;
      end;
    readln;
    while not(seekeof(input)) do
      begin
        inc(n);p3:=pmax;
        for i:=1 to lg do
          begin
            read(ch);
            inc(d[n],tr[ch]*p3);
            p3:=p3 div 3;
          end;
        readln;
      end;
  close(input);
  assign(output,fout);
    rewrite(output);
    qsort(1,n);
    logmax:=0;
    while 1 shl logmax<=n do
      inc(logmax);
    dec(logmax);
    c:=0;
    p3:=pmax;
    for i:=1 to lg do
      begin
        c:=c+a[i]*p3;
        p3:=p3 div 3;
      end;
    num:=0;
    for i:=lg+1 to lga do
      begin
        if query(c) then
          inc(num);
        dec(c,a[i-lg]*pmax);
        c:=c*3;
        inc(c,a[i]);
      end;
    writeln(num);
  close(output);
end.