| ENG RUS | Timus Online Judge |
Обсуждение задачи 1359. Стройка__Andrewy__ Как получен ответ из примера? [1] // Задача 1359. Стройка 28 мар 2016 20:21 Из точки (2,2) мы можем попасть в (1,1),а потом в (0,0), сразу в (0,0), в (1,0),а потом в (0,0). В первом случае t=0.63246+0.23277=0.86522, во втором t=0.86522, в третьем t=0.70711+0.15811=0.86522. Я использую формулу для t=(-v+sqrt(v*v+2*g*len*sina))/(g*sina)),если наклонный отрезок и t=len/v иначе. Putin Re: Как получен ответ из примера? // Задача 1359. Стройка 3 ноя 2022 13:47 Попробуй вариант 2,2 -> 2,1 -> 0,0 (опускаемся на 1 вниз(по вертикали), потом проводим до конца(по диагонали)) Douglas Cardoso How to solve this one? // Задача 1359. Стройка 25 июн 2010 11:39 I really couldn't figure out how to solve it. The way I tried even gives the wrong output for the sample! I modelled like this: Each integer coordinates point represents a node of a graph. There is a edge form point (a, b) to (c, d) iff a >= c and b > d. The edge's weight is equal to the time to go from one point to another one adjacent to the first, which is calculated like this: if theta is the angle between the segment (a, b)-(c, d) and the x-axis, then due to the gravity there is a 10*cos(theta) acceleration in the x-axis direction. So the time needed to go from (a, b) to (c, d) is sqrt(2*(c-a)/(10*cos(theta))). Finally, what I do is to run a shortest-path algorithm in this graph. But for the sample my program answers 0.752121. Does any one knows if ignored any detail? Or maybe if my entire model is wrong? Thanks! Vasily Slesarev Please write answer for test "2 1" [3] // Задача 1359. Стройка 18 июн 2009 18:35 My program writes 0.8561 and gets WA Vasily Slesarev Re: Please write answer for test "2 1" [2] // Задача 1359. Стройка 20 июн 2009 11:30 Help... Vasily Slesarev Re: Please write answer for test "2 1" [1] // Задача 1359. Стройка 20 июн 2009 16:23 I`ve found stupid mistake and got AC! Doski ne mogut bit raspologeni gorizontalno! Sandello Re: Please write answer for test "2 1" // Задача 1359. Стройка 4 фев 2010 00:47 Thanks, i had this mistake too :) It was WA #3 Alexander Rybak Pay attention to the input!!! [1] // Задача 1359. Стройка 24 мар 2005 21:10 The input is not very usual!!! n goes BEFORE m. This permutation cost me 11 unsuccessfull submissions! :) Edited by author 24.03.2005 21:11 Yusheng Re: Pay attention to the input!!! // Задача 1359. Стройка 17 авг 2007 19:35 Thank for your hint Alexandrov Sergey How did I solved this problem :)) [3] // Задача 1359. Стройка 1 апр 2005 23:59 At first I had no ideas how to solve it )) Then I thought that it is a completely physical problem and started to write formulas.... When, after about an hour, I came to integrals I understood that........ I am not a physicist... but I am a PROGRAMER! And at the same moment a good idea came to me: "Oh my God, It is a kind of a labyrinth!" In 10 minutes source was done and I got AC. Now I am thinking... how easier to be a programmer, than physicist :))) Burunduk1 Re: How did I solved this problem :)) [1] // Задача 1359. Стройка 2 апр 2005 03:18 Oh, yes... I had like story. :))) But physical solution is very easy :) It's parabola, I don't remember formula but it is something like y = m*(x^2)/(n^2) So we can easly solve it O(n) using DP. Ilya Razenshteyn Re: How did I solved this problem :)) // Задача 1359. Стройка 12 апр 2005 22:26 I think, if you now some physics you can write simple DP, using energy saving rule. Yusheng Re: How did I solved this problem :)) // Задача 1359. Стройка 17 авг 2007 19:34 plz post your AC code or send it to me cpp_student@163.com Kirin Vladislav Why I have t=0.7691 on example test? [1] // Задача 1359. Стройка 2 окт 2006 12:23 I have calculate time by formula t=sqrt(2*s/g) there s - distance and g - changing speed (g=10m/c^2). Distance I have calculate by trapezium method. I have distance for this test s=2.9578. There is wrong?:-( Kirin Vladislav Re: Why I have t=0.7691 on example test? // Задача 1359. Стройка 4 окт 2006 16:41 I find where I made mistake - in idea of solution: traectory of moving barrel is not a parabola, it's a cycloid. But I have next problem - what is formula of cycloid? Edited by author 04.10.2006 16:43 Edited by author 04.10.2006 16:45 Victor Barinov (TNU) Hello everyboby! I found solution in O(n^4), what about others? (-) [5] // Задача 1359. Стройка 23 мар 2005 17:40 Dmitry 'Diman_YES' Kovalioff. Retired Mine is O(N^4) dp (-) [4] // Задача 1359. Стройка 23 мар 2005 18:09 Victor Barinov (TNU) But it is very slow! Is it possible to accelerate it without precalculation? (-) [3] // Задача 1359. Стройка 23 мар 2005 20:23 Dmitry 'Diman_YES' Kovalioff. Retired Of course... (+) [2] // Задача 1359. Стройка 23 мар 2005 20:46 The fastest solution is precalc (as usual :] ), but you can make your solution very fast without it. It is clear that there is some physical dependence in this problem - the line of optimal movement is some function (a parabola, I presume). So you can look for several nearest points with integer coordinates and use dp only for them. But it is much more difficult and unsafe, isn't it? Ilya Razenshteyn Re: Of course... (+) [1] // Задача 1359. Стройка 4 сен 2005 11:15 Not parabola, but cycloid! It's variational stuff :)! Kirin Vladislav Re: Of course... (+) // Задача 1359. Стройка 3 окт 2006 21:16 What is cycloid's formula? SPIRiT Why WA 9... [1] // Задача 1359. Стройка 29 авг 2006 14:44 I have a question. Can the barrel use the ground, I mean if it reached the ground,can it simply move till the destination point? Edited by author 30.08.2006 12:38 SPIRiT Re: Why WA 9... // Задача 1359. Стройка 19 сен 2006 19:03 To anyone who can't get AC on C++, just use Delphi. I am not kidding. The solution on C++ with double had WA at test 9. The analogical solution on Delphi with real got AC. Anton juver++ Postnikov Sample test // Задача 1359. Стройка 11 авг 2006 16:22 Explain me answer for the sample test case please! ACM.Krupko_Victor[Ivanovo SPU] hint formyla (+) [1] // Задача 1359. Стройка 19 июн 2005 23:11 o(n^4) algoritm cos:=(j-j1)/sqrt(sqr(i-i1)+sqr(j-j1)); f (a[i1,j1]>a[i,j]+abs(v[j]-v[j1])/(g*cos)) or (a[i1,j1]=0) then a[i1,j1]:=a[i,j]+abs(v[j]-v[j1])/(g*cos); exwRabbits_AlMag(VNTU) What does the massiv V mean here? (-) // Задача 1359. Стройка 12 июл 2006 14:19 Yuanming YU, Frank Although this problem isn't so hard,I like it very much. [3] // Задача 1359. Стройка 10 июн 2005 18:42 ACM.Krupko_Victor[Ivanovo SPU] little hint, please+++ [2] // Задача 1359. Стройка 11 июн 2005 02:41 Dmitry 'Diman_YES' Kovalioff. Retired O(N^4) dp (-) // Задача 1359. Стройка 11 июн 2005 12:17 Yuanming YU, Frank Re: little hint, please+++ // Задача 1359. Стройка 11 июн 2005 19:07 For O(n^4) algo, take care that: mv^2 / 2 = mgh mahbub Help PLZ [1] // Задача 1359. Стройка 29 мар 2005 13:50 Can any1 plz tell me what type of dp will be applied here? The initial velocity will be changed as soon as it appears at another point. So how the fastest time of that next point can help? Burunduk1 Re: Help PLZ // Задача 1359. Стройка 31 мар 2005 01:17 V = sqrt(2 * y * g) So for each point you know the speed in it... Now that you can find minimal time to reach it. Burunduk1 Give me answer for this test [2] // Задача 1359. Стройка 29 мар 2005 23:49 I have WA 2. This test is 1, 2 My program outputs 0.7092 and I think that it is true. Give me please right answer for this test and how we should move to reach minimal time. Dmitry 'Diman_YES' Kovalioff. Retired My AC program's output is 0.7071 (-) [1] // Задача 1359. Стройка 30 мар 2005 12:22 wwwwww Re: My AC program's output is 0.7071 (-) // Задача 1359. Стройка 30 мар 2005 21:03 Thank you! I've got AC! Dmitry 'Diman_YES' Kovalioff. Retired Problem definition seems to be incorrect (+) [1] // Задача 1359. Стройка 21 мар 2005 18:23 1) It is said: "Output should contain minimal time in seconds ... accurate within 10^-3". But sample output is 0.8614. 2) In the russian version file "output.txt" is mentioned, while the program shouldn't use any files. Problemset Maintainer Re: Problem definition seems to be incorrect (+) // Задача 1359. Стройка 21 мар 2005 22:18 1) You may output arbitrary number of digits after decimal point, but your number should not differ from correct answer more than 10^-3 2) output.txt: fixed.
|