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?

OK, I'm feeling lazy, so let's do this the simple way -- 334. If I load up and go 333 from Point A toward point B, then drop off 334 and return, I just make it back to my 2000. Then if I go to 333, and drop off the dead batteries, pick up 333 of the 334, then go 166 miles and drop off all but 449 of my batteries, i.e. 334, at the 500 mile marker. I can return to Point A, picking up my one remaining at mile 333. Then I can pick up my last 1000 batteries and head to 500 where I dump my 500 dead ones, pick up the 334 live, and go the rest of the way with 334 live left when I arrive at point B.

I never studied algorithms in school, so I dunno if that's the most efficient way, but I like it.

Posted by Lawrence on 2003-08-27 15:59:37