100 Balls, etc.: The Exciting Conclusion!
Posted by Mr. ANSI Pants | Filed under Challenge of the Month
[When we last visited our intrepid hero, he was engaged in a battle of wits atop the tallest turret of Fallacy Fortress. The fate of the world is again in his hands. We join him now...]
Dr. Destructor: Wait till I get going! Where was I?
Capt. Constructor: Australia. Oh wait. I mean, you were just telling me about spheroids, buckets, and a scale.
Dr. Destructor: Right! I, like many non-virtual Destructors out there, suffer from occasional memory leaks. Don’t tell me you Constructors are immune. Australia? Ha!
Capt. Constructor: Memory and Australia are both quite entertaining topics. But if you’ll excuse me, the world is on the verge of collapse and I hear some spheroids calling my name.
Spheroids: O Captain! my Captain!
[Our hero dashes to the Table of Doom whereon are arranged the spheroid-filled buckets and the badly damaged scale. He buries himself in thought for a full 100 milliseconds, which is an eternity to a modern microprocessor.]
Capt. Constructor: Aha! The solution is simple. One can conceptually number the buckets 0 through 9. Once that is accomplished, the following algorithm should suffice:
void transferSpheroids(int howMany, Bucket& from, Bucket& to) { // The contents of this function are left as an exercise // for the reader. } const int numBuckets = 10; const float normalWeight = 1.0f; const float abnormalWeight = 1.01f; const float singleWeightDiff = abnormalWeight - normalWeight; // See http://en.wikipedia.org/wiki/Arithmetic_progression on why // this works. const float expectedWeight = numBuckets * (numBuckets - 1) * normalWeight / 2.0f; int findHeavyBucket(int buckets[]) { for (int whichBucket = 0; whichBucket < numBuckets; whichBucket++) { transferSpheroids(whichBucket, buckets[whichBucket], this.EmptyBucket); } float actualWeight = scale.Weigh(this.EmptyBucket); float totalWeightDiff = actualWeight - expectedWeight; return (int)(totalWeightDiff / singleWeightDiff); } int main() { // Set up the buckets, etc. // … int bucketContainingHeavies = findHeavyBucket(buckets); }
Capt. Constructor: Of course there may be a syntax error or two in there. You’ll forgive me for not bringing my pocket compiler.
Dr. Destructor: Arg! Foiled again! How were you able to solve it so quickly?
Capt. Constructor: You made the mistake of labeling each of the buckets 0 through 9. That was just the clue I needed. It otherwise might have taken me 300 milliseconds or more.
Dr. Destructor: Curses!
Capt. Constructor: Remember, Destructor, nefariosity does not pay.
Dr. Destructor: I believe you mean nefariousness.
Capt. Constructor: Whatever.
[?]
Tags: thought puzzles