Cute hamsters in programming and an interesting problem about them :)

Правка en1, от StopFuture, 2022-05-26 11:50:45

Cute hamsters and an interesting problem ...

Hello everyone, I know that my rating does not inspire much confidence, but I'm sure that this will not be a reason to miss this blog.

I was faced with a problem from The 2010 All-Ukrainian Programming Contest, at the link you can find the condition and test your decisions for "Flight of the Hamsters".

A little below I will try to give a more formal condition and funny illustration.

Given a plane in which a certain number of vertical segments is given. The point object must be thrown at a certain angle to the horizon, and then calculate the maximum possible number of points at which the parabola of the object movement intersects with the segments.

Please do not consider it elementary until the moment of Accepted. I managed to come up with only a partial solution (82/100) , because I approached the problem from a physical point of view :)

Everyone knows that there are two independent movements on each of the axes, let's write simple formulas for this :  $$$x = v_0 * t * \ cos(\alpha) ;$$$ $$$y = v_0 * t * sin(\alpha) - \dfrac{g * t ^{2}}{2}$$$

Now let's make a small substitution and receive :

$$$y = x * \ tg(\alpha) - g * {\dfrac{x^2}{2 * v_0^2 \cos(\alpha)^2}}$$$

So, the condition of the problem does not say anything about the accuracy of the calculation, but the examples of input data make it clear that you need at least 6 decimal places to get the correct answer. Now we need iterate for everyone $$$ \alpha \in (0, \dfrac {\pi}{2})$$$ with step $$$10^{-6}$$$ radian. Next, for each x in which there is a vertical segment, we see if the object on it and increase the result.

However, this logic, unfortunately, does not give the maximum score: (I spent a lot of time trying to optimize or come up with a different approach to the problem, but all in vain ....

I would like someone to be interested in this problem, because I am very eager to understand what the right approach should be to tasks of this type.

Many thanks to everyone who read up to this point,I expect a certain positive reaction with an explanation, I hope it was not a waste of your time :)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский StopFuture 2022-05-26 11:52:57 0 (published)
en1 Английский StopFuture 2022-05-26 11:50:45 2468 Initial revision (saved to drafts)