ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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
a[i,j]:=b;
end;
?

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;

for i:=1 to n do begin
for j:=1 to 4 do begin
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 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