Find coordinates (x,y,z) of corresponding values and find the manhattan distance between them. Do all in zero-based instead of one-based indices / numbers.

e.g. input: 6, 12 (1-bases) => 5, 11 (0-based)
value of 5 => (x,y,z) of (2,0,1)
value of 11 => (x,y,z) of (3,1,2)
manhattan dist = abs(2-3) + abs(0-1) + abs(1-2) = 3

more: input: 398 9999 (1-bases) => 397, 9998 (0-based)
(19, 18, 1)
(99, 98, 0)
ans = 161

c++ fragment:
    (v = 0-based value)
    int u = int(ceil(sqrt(v+1)));
    int x = u-1;

    int y = -1;
    if (v == (x+1)*(x+1)-1) y = x;
    ...
    else

Please, tell me how to solve this problem...
Not solution but an idea or a hint...
Thanks.

On every step you move one level down. You have three choices to go down-left, down-right and just down (it's not always possible). So, you check which side m is on. If on the right, then we go down-right, otherwise - down-lef, if it's right below us, then we just go down

Don't know, what else to test ...
Any ideas?

Please write the decision of a problem 1302 it is very necessary. Has got in the course I can not in any way help solve

New tests were added. 153 authors lost AC.

input:
1 1000000000
1 27
1 29
1 31
74 74747474
output:
63243
9
9
9
17275

GOOD LUCK!!!

Can anybody tell me what is a data for the fifth test of this problem ?

My program does every test in this forum right, but it doesn't pass test #2.... Please send test to mail: paezand@gmail.com. Any help would be greatly appreciated!


Edited by author 26.09.2010 22:17

I've solved this problem using this logic.

1. Definitions.

integer GetLineNumber(x) - returns a line number of the 'x' element in the triangle.

boolean IsTop(x, linex) - returns TRUE, if the 'x' element, which is situated on 'linex' line, has a common edge with a neighbour from 'linex - 1' line. [define IsTop(1, 1) = FALSE]

integer RightMove(x)
begin
  if (IsTop(x, GetLineNumber(x)) x = x + 1;
  return (x + 2 * GetLineNumber(x));
end;

integer LeftMove(x)
begin
  if (IsTop(x, GetLineNumber(x)) x = x - 1;
  return (x + 2 * GetLineNumber(x));
end;

2. Statement.
a) 'm' and 'n' ('n' > 'm') are situated on the lines 'linem' and 'linen'.
b) rightp = RightMove(RightMove(...RightMove(m)...)) [('linen' - 'linem') times repeated].
leftp = LeftMove(LeftMove(...LeftMove(m)...)) [('linen' - 'linem') times repeated].
c) If 'leftp' <= 'n' <= 'rightp' than the length of the path from 'm' to 'n' is equal to the length of the path from 'm' to any 'p' such, that 'leftp' <= 'p' <= 'rightp'.

All you need is to add some code which will count the edges while using RightMove and LeftMove functions and understand, what to do, if the condition 'leftp' <= 'n' <= 'rightp' is FALSE.

Pay attention, that first number may be greater than second :)

Can any body help me for test case #1

Normal coordinates has two num --(x,y). This problem we can establish new corrdinates with three num, because the cell is a triangle.

Then the answer can be calc by m's and n's corrdinates.

I overcame the trouble when replaced my
(int)sqrt(1.e9)
with
(int)sqrt(1.e9)+1

This was an upper bound to binary search when searching row number for N.

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

   var
   n, m, d, dn, dm, dns, dms, n1, m1, answer, x : integer;

   function teng(delta : integer) : integer;
   var
     ans : integer;

   begin
     ans := delta * 2;
     if odd(delta) and (odd(dn) or odd(dm)) then
       begin
         if odd(n1) then
           begin
             if odd(n) then dec(ans)
             else inc(ans)
           end
         else
           if odd(n) then inc(ans)
           else dec(ans);
       end;
     teng := ans;
   end;

begin
   read(m, n);
   if n < m then begin x := n;  n := m;  m := x;  end;
   n1 := TRUNC(sqrt(n));
   if sqr(n1)=n then dec(n1);
   m1 := TRUNC(sqrt(m));
   if sqr(m1)=m then dec(m1);
   d := n1-m1;
   dn := n - sqr(n1);
   dm := m - sqr(m1);
   dns := sqr(n1+1)-n;
   dms := sqr(m1+1)-m;
   if d = dn - dm then answer := teng(d)
   else
     begin
       if dm >= dn then begin writeLn(2*d+dm-dn);  exit  end;
       if dms >= dns then begin writeLn(2*d+dms-dns);  exit  end;
       if d > dn-dm then answer := (dn-dm)*2 + teng(d-dn+dm)
       else
         answer := (dns-dms)*2 + teng(d-dns+dms);
     end;
   writeLn(answer);
end.

Can you write the output?
Input:
"500000
100000"
(he-he)

Somebody! Help me!!
((((

Please send me test 6 on it email: mikhalevskiy@mail.ru

label a1;
var n, m, r, nn, mn, nm, mm: longint;
begin
     read(n, m);
     if m > n then begin
        r := m;
        m := n;
        n := r;
     end;
     nn := round(int(sqrt(n - 1)));
     mn := round(int(sqrt(m - 1)));
     if nn = mn then begin
        nm := n - nn * nn;
        mm := m - mn * mn;
        r := abs(mm - nm);
        goto a1;
     end;
     r := nn - mn;
     r := r * 2;
     r := r - 1;
     nm := n - nn * nn;
     mm := m - mn * mn;
     if m mod 2 - mn mod 2 = 0 then
        r := r + 1;
     if abs(n mod 2 - nn mod 2) = 1 then
        r := r + 1;
     if (nm - mm > nn - mn + 1) then
        r := r + ((abs(nm - mm) - 1) div 2) * 2;
     if (mm - nm + 1 > nn - mn) then
        r := r + ((abs(nm - mm) + 1) div 2) * 2;
a1:  writeln(r);
end.

Edited by author 14.10.2005 20:52

program t1320;


var
 u,v,t : int64;
 f,maxl,maxr : int64;
 il1,il2,jl1,jl2 : int64;

function GetLevel1 (i:integer):int64;
var t : int64;
begin
 t := (Trunc (sqrt ((i))));
 if sqr (t)<i then Result := t+1
 else Result := t;
end;

function GetLevel2 (i:int64):int64;
var
b : byte;
begin
f := GetLevel1 (i);
b := ((f and 1)*2) + (i and 1);
if (b=0) or (b=3) then Result := 2*F-1
else Result := 2*(F-1);
end;

function GetMaxOnLev (Level : int64):int64;
begin
Result := sqr (Level);
end;

function GetMinOnLev (Level : int64) : int64;
begin
Result := sqr (Level-1)+1;
end;

function ComputePath : int64;
begin
il1 := GetLevel1 (u); il2 := GetLevel2 (u);
jl1 := GetLevel1 (v); jl2 := GetLevel2 (v);
if (u=v) then begin REsult :=0; exit; end;
if (u=1) then begin Result := jl2-il2; exit; end;
if (il2=jl2) then begin Result := v-u; exit; end;
 if (il2 and 1)=1 then
 begin
  maxl := GetMinOnLev (jl1)-GetMinOnLev(il1)+u;
  maxr := GetMaxOnLev (jl1)-GetMaxOnLev(il1)+u;
 end
else
 begin
  maxl := GetMinOnLev (jl1)+(u-1)-GetMinOnLev(il1);
  maxr := GetMaxOnLev (jl1)-GetMaxOnLev(il1)+u+1;
 end;
if v < maxl then Result := jl2-il2+(maxl-v) else
if v > maxr then Result := jl2-il2-(v-maxr) else
Result := jl2-il2;
end;

begin
Read (u,v);
if (u>v) then begin t:=u; u:=v; u:=t; end;
WriteLn (ComputePath);
end.

Edited by author 19.07.2005 18:28