Editorial for TLE '16 Contest 6 (Mock CCC) J3 - Two Kangaroos


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

When we consider each time the Kangaroos hop, we must then calculate the total change in distance between them. For example, if Papa Kangaroo hops 5 units towards Little Kangaroo, and Little Kangaroo hops 2 units in the same direction, then overall, Papa Kangaroo ends up 5 - 2 = 3 units closer to Little Kangaroo. So, we can use division and the ceiling method to find out how many times they should hop these distances to get close enough to each other.

Also, there is an option for Papa Kangaroo to hop away from Little Kangaroo. This could actually be useful. For example, suppose K = 10 and L = 9. Papa Kangaroo has the option to hop 10 units towards Little Kangaroo, who would hop 9 units away. Then they would be 10 - 9 = 1 unit closer to each other. Alternatively, Papa Kangaroo can hop 1 unit away from Little Kangaroo, who would hop 9 units towards him. This would mean that they would be 9 - 1 = 8 units closer afterwards, which clearly is a better option.

Time Complexity: \mathcal{O}(1)


Comments

There are no comments at the moment.