Из точки (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 иначе.

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!

My program writes 0.8561 and gets WA

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

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 :)))

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?:-(

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

Explain me answer for the sample  test case please!

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);

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?

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.

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.