Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Hint | So Sui Ming | 1302. Дельта-волна | 10 янв 2024 13:55 | 1 |
Hint So Sui Ming 10 янв 2024 13:55 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 |
Damn, I cann't solve it! | Alexey | 1302. Дельта-волна | 26 май 2022 17:45 | 7 |
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 ... |
How to not write many "if-elif-...." | andreyDagger | 1302. Дельта-волна | 13 ноя 2021 10:42 | 1 |
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 |
WA#11 | Anton | 1302. Дельта-волна | 22 ноя 2016 00:01 | 2 |
WA#11 Anton 16 авг 2012 07:09 Don't know, what else to test ... Any ideas? Re: WA#11 AGrigorii [Yaroslavl SU] 🔥 22 ноя 2016 00:01 |
Please help!!! | Rio | 1302. Дельта-волна | 25 май 2011 21:29 | 1 |
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 |
Problem 1302 "Delta-wave" has been rejudged (+) | Sandro (USU) | 1302. Дельта-волна | 2 янв 2011 01:27 | 1 |
New tests were added. 153 authors lost AC. |
some test | hoan | 1302. Дельта-волна | 1 дек 2010 23:47 | 1 |
input: 1 1000000000 1 27 1 29 1 31 74 74747474 output: 63243 9 9 9 17275 GOOD LUCK!!! |
what is 5-th test ? | goverla | 1302. Дельта-волна | 17 ноя 2010 16:46 | 2 |
Can anybody tell me what is a data for the fifth test of this problem ? 1 to 27, 29, 31, etc. is 9 |
WA 2 | Andres | 1302. Дельта-волна | 24 сен 2010 05:50 | 1 |
WA 2 Andres 24 сен 2010 05:50 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 |
Hint! | Leonid (SLenik) Andrievskiy | 1302. Дельта-волна | 20 июл 2009 16:01 | 1 |
Hint! Leonid (SLenik) Andrievskiy 20 июл 2009 16:01 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. |
If you have WA 1 =) | Oleg Strekalovsky [Vologda SPU] | 1302. Дельта-волна | 12 май 2009 23:56 | 1 |
Pay attention, that first number may be greater than second :) |
Help for test case #1 | Snigdha Chandan Khilar | 1302. Дельта-волна | 17 апр 2009 00:18 | 1 |
Can any body help me for test case #1 |
My idea about this problem, not solution | Megatron | 1302. Дельта-волна | 18 фев 2009 06:29 | 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. |
Perhaps this would help you with WA#7 | strider | 1302. Дельта-волна | 4 фев 2009 01:58 | 1 |
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. |
WA#6, please help me!! here my code | Bobur | 1302. Дельта-волна | 4 фев 2009 01:07 | 2 |
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! :) |
Solve this test, pls. | ILYMTL | 1302. Дельта-волна | 25 июл 2008 19:59 | 4 |
Can you write the output? Input: "500000 100000" (he-he) My answer is "571", but expected "573". :( |
Help me please with the test number 7 | Vladikavkaz SOGU (K.Ivanova, I.Bichkaeva) | 1302. Дельта-волна | 8 май 2008 19:58 | 4 |
|
TL on test 6 | Yevgeniy | 1302. Дельта-волна | 9 июл 2007 21:44 | 1 |
Please send me test 6 on it email: mikhalevskiy@mail.ru |
Why WA#7??? {Почему WA#7???} | SIAL_snipious_Pimenov(Пименов) | 1302. Дельта-волна | 13 окт 2005 14:02 | 1 |
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 |
Wht's my error? | Agent_TWX | 1302. Дельта-волна | 19 июл 2005 18:27 | 1 |
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 |