100 Day Summer Challenge

100 problems in 100 days. #100problems

Day 68

68 of 100: Desert Trek

Sara needs to trek from an oasis to a destination 10 miles away across a barren desert.

The facts:

  • Crossing one mile of desert requires using 1 gallon of water.
  • Sara can only carry 6 gallons of water at a time.
  • Sara can drop a water cache (of any amount of water from the supply she is carrying at that moment) at any of the nine stops along the route, and then pick up any part of the cache on a later trip.

What's the minimum number of times Sara must leave the oasis in order to cross the entire 10 mile span of desert?

Start by just trying to get Sara to her destination, then try to optimize!

×

Problem Loading...

Note Loading...

Set Loading...