Problem of July '21

This time I selected an easy problem to help almost beginners. This helps you learn the correct path to think on the problems. The problem is OptimalGolf.

It states that we are playing a golf game. The distance from tee to the hole is D. We have several clubs where by using i-th of them we can move the ball from its current position to anywhere within the range [clubLo[i] meters, clubHi[i] meters] from its current position.

Calculate the minimum number of storks needed to put the ball into the hole.

Let’s solve the problem case by case.

The simplest case is there exists a club that can straighly put the ball into the hole. Formally there exists i where clubLo[i] <= D <= clubHi[i]. The answer is 1 in this case.

Otherwise the answer is not 1.

Consider a club that can move the ball at most x meters. By using it two times, which positions can we move the ball to? For example, we can first move the ball x meters to the left and x meters to the right, the ball is in its initial position again. As you can simply imagine we can move that ball to every position with distance less than or equal to 2x.

So if we’re going to use clubs more than once, clubLo is no longer important. The point is just that the sum of clubHi of clubs we use must be equal or greater than D.

This says that we’re going to just use the club with the greatest clubHi value. Let ans be the answer, then: ans * max(clubHi) >= D so ans = ceil(D / max(clubHi).

You can read about ceil here.

Code by kazuyoshihayase:

1
2
3
4
5
6
7
8
9
10
11
12
class OptimalGolf:
  def minStrokes(self, D, clubLo, clubHi):
  dai = max(clubHi)
sho, amari = divmod(D, dai)
if amari == 0:
  return sho
if sho == 0:
  for (l, h) in zip(clubLo, clubHi):
    if l <= D and D <= h:
  return 1
return 2
return sho + 1