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. You just have to understand the optimal algorithm for finding a shortest way from A to B on this object. I'm trying... Should I write a Function(n) wich returns the number of row in wich n shands? There is three kinds of "rows", so, what shall I do? Give me the way to think... Find optimal path from 1 to some small numbers. It will help you. Try to change direction in the optimal path as few times as possible. It must be formula, isn't it? Or there is an algo to find answer? There is a formula, but it's a bit easier to solve using algo. Convert input numbers into row/column. Row will not exceed ~33000, so you can iterate over row using algo and use math over column. Sorry, could you tell me the algorithm, otherwise I don’t understand it ... 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 ? 1 to 27, 29, 31, etc. is 9 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. Try to find other algoritm. On small test your program gives a right answers. But on this test: 119 751 answer is not true. Good luck! :) Can you write the output? Input: "500000 100000" (he-he) My answer is "571", but expected "573". :( 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 |
|