Cod sursa(job #99190)

Utilizator gurneySachelarie Bogdan gurney Data 10 noiembrie 2007 23:26:22
Problema Abc2 Scor 0
Compilator fpc Status done
Runda Happy Coding 2007 Marime 3.71 kb
program abc2;
  const
    fin='abc2.in';
    fout='abc2.out';
    lmax=25;
    nmax=50000;
    tr:array['a'..'c'] of integer=(0,1,2);
type
  pula=^boolean;
var
  f:text;
  d:array[0..nmax] of int64;
  a:array[0..10000000] of integer;
  cuv:array[0..20] of integer;
  lga,lg,i,j,k,n,x,y,logmax:longint;
  c,p3,pmax,aux:int64;
  ch:char;
  hash:array[0..100000,0..50] of longint;
  num:longint;
  r:longint;

function h(x:int64):int64;
  begin
    h:=x mod 100000;
  end;

procedure hashtable;
  var
    poz:int64;
    i:longint;
  begin
    for i:=1 to n do
      if d[i]<>d[i-1] then
        begin
          poz:=h(d[i]);
          inc(hash[poz,0]);
          hash[poz,hash[poz,0]]:=i;
        end;
  end;

function query2(x:int64):boolean;
  var
    poz:int64;
    found:boolean;
    i:longint;
  begin
    poz:=h(x);
    found:=false;
    for i:=1 to hash[poz,0] do
      if d[hash[poz,i]]=x then
        begin
          found:=true;
          break;
        end;
    query2:=found;
  end;

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;

procedure qsort2(poz,st,dr:longint);
  var
    i,j:longint;
    tmp,x:int64;
  begin
    i:=st;j:=dr;
    x:=d[hash[poz,(st+dr)shr 1]];
    repeat
      while d[hash[poz,i]]<x do
        inc(i);
      while d[hash[poz,j]]>x do
        dec(j);
      if i<=j then
        begin
          tmp:=hash[poz,i];hash[poz,i]:=hash[poz,j];hash[poz,j]:=tmp;
          inc(i);dec(j);
        end;
    until i>j;
    if j>st then
      qsort2(poz,st,j);
    if i<dr then
      qsort2(poz,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(f,fin);
    reset(f);
    randomize;
    r:=random(1000)+1;
    lga:=0;
    while not(seekeoln(f)) do
      begin
        read(f,ch);
        inc(lga);
        a[lga]:=tr[ch];
      end;
    readln(f);
    n:=1;lg:=0;pmax:=1;
    while not(seekeoln(f)) do
      begin
        read(f,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(f);
    while not(seekeof(f)) do
      begin
        inc(n);p3:=pmax;
        for i:=1 to lg do
          begin
            read(f,ch);
            inc(d[n],tr[ch]*p3);
            p3:=p3 div 3;
          end;
        readln(f);
      end;
  close(f);
  assign(f,fout);
    rewrite(f);
    qsort(1,n);
    logmax:=0;
    while 1 shl logmax<=n do
      inc(logmax);
    c:=0;
    hashtable;
    {for i:=0 to nmax do
      if hash[i,0]>1 then
        qsort2(i,1,hash[i,0]);}
    p3:=pmax;
    for i:=1 to lg do
      begin
        aux:=a[i];aux:=aux*p3;
        c:=c+aux;
        p3:=p3 div 3;
      end;
    num:=0;
    {for i:=lg+1 to lga do
      begin
        if query2(c) then
          inc(num);
        aux:=a[i-lg];
        aux:=aux*pmax;
        dec(c,aux);
        c:=c*3;
        inc(c,a[i]);
      end;
    if query2(c) then
      inc(num);
    writeln(f,num);  }
  close(f);
end.