You have an electric car that you want to use to transport some batteries 1,000 miles. You have 3,000 batteries, but your car can only carry 1,000 of them at once. In addition, for each mile that it travels, the car will need to use up one battery in order to power itself.

How many unspent batteries will you be able to transfer to your destination?

The best you can do is 533 batteries, with 1 unused battery left sitting on the road.

The key is to realize that any trips where you don't take 1000 batteries are wasted. So you want stopping points that allow 3000 (the start), 2000, and 1000 batteries.

To take 3000 batteries, it requires driving a distance 5 times (you take 1000 twice and return, then take 1000 once and stay). You'll use 1000 batteries, and 1000/5 is 200. So take 1000 batteries to 200, drop 600, return, and repeat. You'll have 2000 batteries there.

To take 2000 batteries, you drive a distance 3 times. 1000 batteries/3 is 333, so drive to 200+333 = 533. Drop 334 batteries, and then return, get the remaining 1000. You'll now have 1001 batteries at 533. Leave one, take 1000, and drive the remaining 467 miles, leaving you with 533 batteries, and one good battery sitting at 533 miles.

Posted by Ender on 2002-08-30 04:14:57