Yo, I have a question on the boogaboo https://usaco.org/index.php?page=viewproblem2&cpid=418. What does it mean for Bessie to take a step? In the problem statement it says that Bessie can only take exactly 1 unit in either north/south/east/west, but then it says that Bessie can “divide” the step into two components. Isn’t this contradictory?
Also, can Bessie move a distance less than 1 (statement says that non-integral distances are allowed)? e.g. Bessie moves from (0, 0) to (0, 0.9)?
Basically, Bessie can split her step into moving some x units horizontally and y units vertically as long as x+y = 1. So, from (0,0), she can also reach (0.5,0.5), (0.3, 0.7), (-0.9, 0.1), etc.
Your second question doesn’t really matter since the question asks for “within” k steps. So you can think of it like Bessie can stop whenever she likes.
Your second question doesn’t really matter since the question asks for “within”
k steps. So you can think of it like Bessie can stop whenever she likes.
Does this mean that Bessie can stop in the middle of a step?
I guess you can think about it that way. The problem saying within means that as long as Bessie walks past that point, we should count that point. So it’s the same as if Bessie can stop whenever she wants