ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1318. Logarithm

Help me, it's TLE #5. And another question inside.
Question:
Why do I have to write
    for j:=1 to 4 do begin
      read(b);
      a[i,j]:=b;
    end;
instead of
    read(a[i,1],a[i,2],a[i,3],a[i,4]);
?


program ural1318;
const
  maxn=5000;
  base=4294967296;
  maxe=38;
type
  bignum=array[1..4]of int64;
var
  e:array[0..maxe]of bignum;
  a:array[1..maxn]of bignum;
  n,i,j:word;
  ans,b:cardinal;
function x(a,b:bignum):bignum;
  var
    i:byte;
  begin
    for i:=1 to 4 do
      x[i]:=a[i] xor b[i];
  end;
function smaller(a,b:bignum):boolean;
  var
    i:byte;
  begin
    for i:=1 to 4 do
      if a[i]<b[i] then begin
        smaller:=true;exit;
      end
      else if a[i]>b[i] then begin
        smaller:=false;exit;
      end;
    smaller:=false;
  end;
function f(a:bignum):byte;
  var
    l,r,m:byte;
  begin
    l:=0;r:=maxe;
    repeat
      m:=(l+r+1) div 2;
      if smaller(a,e[m]) then r:=m-1 else l:=m;
    until l=r;
    f:=l;
  end;
begin
  e[0,4]:=1;
  for i:=1 to maxe do
    for j:=4 downto 1 do begin
      inc(e[i,j],e[i-1,j]*10);
      if e[i,j]>=base then begin
        e[i,j-1]:=trunc(e[i,j]/base);
        dec(e[i,j],trunc(e[i,j-1]*base));
      end;
    end;
  e[0,4]:=0;

  read(n);
  for i:=1 to n do begin
    for j:=1 to 4 do begin
      read(b);
      a[i,j]:=b;
    end;
    for j:=1 to i-1 do
      inc(ans,f(x(a[i],a[j])));
  end;
  writeln(ans*2);
end.
Re: Help me, it's TLE #5. And another question inside.
Posted by Aleksey (BMSTU IU7) 3 Oct 2004 11:15
In first: it is not correct to show this your solution (even wrong), please clear it, it already too bad.

In second:
for I:=1 to N do readln(A[I][0],A[I][1],A[I][2],A[I][3]);
- is correct pascal-line, where
type TNum=array[0..3] of longword
var A:array[1..5000] of TNum;


In third: to get AC your are to ULTRA-STRICT optimization.
That meens some ASM-inline commands (bad way) or
usual Pascal high-optimized code (depresive way).

For example:
my AC program (0.703 461 КБ) use two usual cycles (two "repeat", o(n*n/2)), and a LOG calculation code (about 650 lines).

650 lines was generated by my special generation program. This code consists only "IF" operator, "XOR" and
":=" operator. Some path of this code here:
-----BEGIN LOG-FUNCTION----------------------
v:=A^[0]xor B^[0];
if v<1 then
  begin
    v:=A^[1]xor B^[1];
if v<5 then
    begin
      v:=A^[2]xor B^[2];
if v<2 then
      begin
        v:=A^[3]xor B^[3];
if v<1 then
        log:=0
else if v=1 then
          begin
           log:=0;
          end
        else
        begin
         if v<100000 then
--....---------------------
   if v<232830 then
        begin
         if v<232 then
          begin
           if v<23 then log:=10
            else if v>23 then log:=11
            else
            begin
            v:=A^[3]xor B^[3];
            if v>=1215752192 then log:=11 else log:=10;
            begin
            end;
            end
          end
          else if v>232 then
           begin
            if v<2328 then
             begin
              if v<2328 then log:=12
               else if v>2328 then log:=13
--....---------------------
then log:=log*2;
To generate this code I use several recurse functions and binary search of course.
Think better and get AC 1318(1/1) as my.



Edited by author 03.10.2004 11:23
As I've written before, there is nothing difficult at all (+)
Posted by Dmitry 'Diman_YES' Kovalioff 3 Oct 2004 14:47
No assembler, no data structure tricks. The problem can be easily solved via well-optimized precalc...
Re: As I've written before, there is nothing difficult at all (+)
Posted by Tolstobrov_Anatoliy[Ivanovo SPU] 21 Aug 2005 22:02

Yes, Dmitry 'Diman_YES' Kovalioff the rights.
0.687s 281kb